Math puzzles

cyclops · **#81**

Redundant wrote:

Linear combinations are taken of finitely many elements.

No, countable many. See infinite dimensional Hilbert spaces on wikipedia for an example.
It is easy to construct a countable dimensional basis for R over {0,1}. ( Over the rationals should be "easier" )
If b_k = 2^k ( k integer ) then every real number can be expressed binary and hence as a countable linear combination ( over {0,1} ) of basisvectors b_k.
This far I trust the given solution in that there is such countable base for R. The fact that 1 = 0.11111111.... ( binary ) makes me believe that the decomposition of a real number into such base is not garanteed unique. But uniqueness is necessary for a correct definition of f in the proof.

@rubinz: You are right: uncountable basis might do the trick also. Uniqueness as above worries me: how can you prove your pi is not expressible as a infinite linear combination of other basiselements. For finite bases I know the proof.
Next, why do you need to seperate two basiselements? I think you need only one basiselement and decompose along this basiselement and its complement.

Redundant · **#82**

http://en.wikipedia.org/wiki/Basis_(linear_algebra)

Quote:

The sums in the above definition are all finite because without additional structure the axioms of a vector space do not permit us to meaningfully speak about an infinite sum of vectors.

There are other notions of basis that allow for countable sums, but not the usual definition. In fact, most of the nice properties of bases come entirely from the fact that the linear combinations are finite.

cyclops · **#83**

edit: above was nicely formatted with spaces. 19*19 removed them. Sorry.

cyclops · **#84**

Redundant wrote:

There are other notions of basis that allow for countable sums, but not the usual definition. In fact, most of the nice properties of bases come entirely from the fact that the linear combinations are finite.

Ok, granted.
In that case the given solution is even more doubtfull as the base is clearly constructed in a countable way. I would like to see a paper with some more rigorous proof.

Redundant · **#85**

cyclops wrote:

Redundant wrote:

There are other notions of basis that allow for countable sums, but not the usual definition. In fact, most of the nice properties of bases come entirely from the fact that the linear combinations are finite.

Ok, granted.
In that case the given solution is even more doubtfull as the base is clearly constructed in a countable way. I would like to see a paper with some more rigorous proof.

flOvermind's construction works if, instead of indexing by the naturals, he indexes by the ordinals. This is where the full force of the axiom of choice is, as we're picking arbitrary elements from outside the span of our B_alpha (using the same notation as flOvermind, but letting alpha be an ordinal) and we must make uncountably many choices. This should be a "construction" of a basis for R over Q ... assuming I've done transfinite induction correctly here.

flOvermind · **#86**

Redundant wrote:

Linear combinations are taken of finitely many elements.

I agree with everything in your post, assuming the quoted part is true. But it's not clear to me why this should be the case. Of course, that's a matter of definition, so it can't really be proven or disproven...
I'm pretty sure I have already seen cases where a basis for a vector space was constructed with the assumption that infinite sums are allowed. Usually that was in the context of Hilbert spaces, perhaps a basis is defined differently there?

EDIT: After searching Wikipedia a bit, I really have found that both definitions of a basis exist: Yours is called Hamel basis, and mine is called Schauder basis, and it also seems that the Hamel basis is the "usual" definition when talking about normal (non-Hilbert) vector spaces. That's where my confusion seems to come from...

EDIT2: Whoops, I seem to have missed quite a few posts before answering

flOvermind · **#87**

Redundant wrote:

flOvermind's construction works if, instead of indexing by the naturals, he indexes by the ordinals. This is where the full force of the axiom of choice is, as we're picking arbitrary elements from outside the span of our B_alpha (using the same notation as flOvermind, but letting alpha be an ordinal) and we must make uncountably many choices. This should be a "construction" of a basis for R over Q ... assuming I've done transfinite induction correctly here.

Yes that would certainly work. Since the construction just uses all previous elements, not a single predecessor, there is nothing special to do at the limit step, so I don't see a problem with transfinite induction.

Now it would be interesting if my construction of f and g still works with a countable Schauder basis

EDIT: A more straight-forward way to construct f and g is just invoke the theorem that a basis exists, invoke the axiom of choice twice to pick out two basis elements, and define f as the projection function on one of the two basis elements. That way, not even an ordered basis is needed

flOvermind · **#88**

cyclops wrote:

edit: above was nicely formatted with spaces. 19*19 removed them. Sorry.

Seems to be correct. It's slightly different than my solution, but with the same number of coins.
Now the interesting question: Is it optimal? How to prove that? Or can anyone do better?

Some information theoretical observations:

cyclops · **#89**

robinz wrote:

So you basically choose a basis for the reals over the rationals - this bit requires the axiom of choice.

So lets find such basis:
B0 = {1}
B1 = {1, pi }
B2 = { 1, pi , pi^2 }

Bn = Bn-1 + pi^n

B = union of all B's
L(B) = set of all rational, possibly infinite but converging, linear combinations from B.

Assume pi^-1 is in L(B) then
p^-1 = a_0 + a_1 * pi + a_2 * pi^2 ...... possibly ad infinitum. MULTIPLY by pi:

1 = a_0*pi + a_1 * pi^2 + .... possibly ad infinitum

So we have that either L(B) < R either numbers are not uniquely expressible over B.
Both are fatal for the construction of f.

You might reply I stopped too early adding vectors to the base. Also adding the negative powers of pi? Why are we ready then? Or does your enumerable base not exist?

Another approach: define two non zero reals as dependent if their quotient is rational. Dependency is a equivalence relation giving rise to equivalence classes. From each equivalence class choose a representative ( axiom of choice ). E, the set of all such representatives, might be the sought base for R. At least L(E) = R.
But how to prove the lineair representation of reals in E is unique?

cyclops · **#90**

flOvermind wrote:

Now the interesting question: Is it optimal? How to prove that? Or can anyone do better?

Yes it is optimal.
First we observe that it only makes sense to balance two equal number of coins against each other.
Next we observe that as long as the scale didn't tilt yet a next scaling gives only two discrimating results neutral or tilting. Whether it tilts to the left or right doesn't help us to eliminate suspects. ( N , T )
After the scale has tilted for the first time a next scaling can give three discriminating results neutral, equal tilting or opposite tilting. ( N, E, O )

We can start sensibly only with two equal piles A and B balancing against each other leaving out a pile C.
If this balance result is neutral and C has more than 5 coins we are stuck.
Why? If the next balancing act again gives neutral the final one has only two outcomes. But if the next balancing act tilts the scale the third one has three outcomes. So together only 5 outcomes possible after a first neutral scaling. We can discrimate between 5 suspects at most.

If the scale tilts from the start the second and third scaling gives three outcomes each so at most 9 outcomes. A and B has the same number of coins but together not more than 9. So 4 coins each at most. That gives 4 + 4 + 5 at most.

The next question: can we decide between 14 suspects given a 15th that is genuine.

flOvermind · **#91**

cyclops wrote:

flOvermind wrote:

Now the interesting question: Is it optimal? How to prove that? Or can anyone do better?

Yes it is optimal.
First we observe that it only makes sense to balance two equal number of coins against each other.
Next we observe that as long as the scale didn't tilt yet a next scaling gives only two discrimating results neutral or tilting. Whether it tilts to the left or right doesn't help us to eliminate suspects. ( N , T )
After the scale has tilted for the first time a next scaling can give three discriminating results neutral, equal tilting or opposite tilting. ( N, E, O )

We can start sensibly only with two equal piles A and B balancing against each other leaving out a pile C.
If this balance result is neutral and C has more than 5 coins we are stuck.
Why? If the next balancing act again gives neutral the final one has only two outcomes. But if the next balancing act tilts the scale the third one has three outcomes. So together only 5 outcomes possible after a first neutral scaling. We can discrimate between 5 suspects at most.

If the scale tilts from the start the second and third scaling gives three outcomes each so at most 9 outcomes. A and B has the same number of coins but together not more than 9. So 4 coins each at most. That gives 4 + 4 + 5 at most.

Nice.

cyclops wrote:

The next question: can we decide between 14 suspects given a 15th that is genuine.

Or perhaps more? Because once you introduce a genuine coin, you have three possible outcomes on every trial involving the genuine coin, even if it is the first one: Balanced, and tilted with the genuine coin down or up. The question is: can we extract useful information from that? I haven't found a way yet, but also no argument why that isn't possible

Redundant · **#92**

This thread demands additional problems!

This one's from a Putnam from a couple years ago. Given an empty 2010 by 2010 matrix, Alice and Bob alternate filling entries with real numbers. After all entries are filled, Alice wins if the determinant is nonzero, while Bob wins if the determinant is zero. Who has a winning strategy?

cyclops · **#93**

Redundant wrote:

This thread demands additional problems!

This one's from a Putnam from a couple years ago. Given an empty 2010 by 2010 matrix, Alice and Bob alternate filling entries with real numbers. After all entries are filled, Alice wins if the determinant is nonzero, while Bob wins if the determinant is zero. Who has a winning strategy?

Bob wins on a 2X2 matrix. If he starts he enters a zero anywhere and next makes a row or a column of zeros. If he is second he enters a zero diagonally opposite Alice's entry and next makes a row or a column of zeros.

So my guess is: Bob.

Solomon · **#94**

Bah these problems are too complicated, so here's a simple one: abcd = a^a + b^b + c^c + d^d. What are the values of a, b, c, and d? (note: abcd is not a*b*c*d, but a 4-digit number where a is in the thousands' place, b is in the hundreds' place, etc.; e.g: if abcd = 4819, then a = 4, b = 8, c = 1, d = 9).

Redundant · **#95**

Araban's problem

Harleqin · **#96**

abcd

cyclops · **#97**

Redundant wrote:

This one's from a Putnam from a couple years ago. Given an empty 2010 by 2010 matrix, Alice and Bob alternate filling entries with real numbers. After all entries are filled, Alice wins if the determinant is nonzero, while Bob wins if the determinant is zero. Who has a winning strategy?

Pls. Solve it, redundant.

Redundant · **#98**

Solution:

CSamurai · **#99**

Redundant wrote:

Solution:

cyclops · **#100**

CSamurai wrote:

Can you prove that?

Math puzzles

Who is online