Math puzzles

[robinz]

and a reply to cyclops about the other problem:

A basis certainly exists, if we assume the axiom of choice, as fl0vermind says. In fact, as he says, the argument seems to prove the existence of a countable basis. But I don't think it matters even if the basis turns out to be uncountable - all that is required is that one exists; then we take any two different elements of it and proceed as before.

Incidentally, the same argument can be used to produce any finite number of periodic functions whose sum is the identity function

EDIT: fl0vermind's post is a little confused in one respect - we don't need the axiom of choice to prove that the reals are a rational vector space; one simply checks that the axioms are true (which is trivial). The AC only comes in when actually constructing a basis. It is indeed one of the most useful consequences of the AC (it's probably even equivalent, although I'm not sure about this) that every vector space has a basis

[cyclops]

...........
B is countably infinite by construction. The elements are linearly independent by construction. And seen as vector space over the rationals, the reals must be countably-infinite-dimensional because R and Q^N are the same size. Therefore, B is a basis.
.........

Nice! I'm almost convinced. But from R and Q^N are the same size I wouldn't dare to conclude that R and L(B) are equal. After all the set of integers and the set of rationals are also the same size but unequal. Also I'm not sure the uniqueness of the representation survives the limit.

[Redundant]

In a two dimensional vectorspace the solution is easy.

In any vectorspace with more than one dimension, the solution is easy

It seems the real problem is for which fields the first problem cannot be solved.
I think it can't be solved in the reals. But the problem would be nice if I'm wrong. Please flovermind, give us a hint.

Edit: Well, Robinz thought about these lines before. But I doubt intuitively that there exists such ( countable ) basis for the reals as he assumes. But maybe the axiom of choice comes in here. And maybe the concept of an overcountable basis makes sense.

Robinz already found the correct solution:
http://www.lifein19x19.com/forum/viewto ... 820#p39820

Further elaboration:

Since we already know it's easy for each more-than-one-dimenisonal vector space, we just need to show that the reals are a vector space . For that, you need the axiom of choice.

Using the axiom of choice, you can construct a basis for the reals over the rationals iteratively:
Let's start with an empty basis B_0 := ()
Now we construct B_i+1 := B_i + s(R L(B_i))
+ means adding an element to the basis
is set difference
L(b_1, ..., b_n) is the linear span, that is: { sum{b_i * x_i | i = 1..n} | x_i in Q }
s is a selector function that selects an arbitrary element of a set (that function exists according to the axiom of choice)

Intuitively speaking, this construction takes an element of the reals that is not yet reachable as linear combination of the basis, and adds it to the basis.
Now we just need to iterate this construction infinitely often, giving us a basis B := limit(i->inf) B_i.

B is countably infinite by construction. The elements are linearly independent by construction. And seen as vector space over the rationals, the reals must be countably-infinite-dimensional because R and Q^N are the same size. Therefore, B is a basis.

We know that given a basis, each vector in a vector space has a unique representation x = x1*b1 + x2*b2 + ...
Now, we can just take the first two elements of the basis (let's say for convenience that they are 1 and e), and construct the functions:
f(x := x1*1 + xe*e + ...) = x1
g(x := x1*1 + xe*e + ...) = x - f(x)

f is e-periodic: f(x + e) = f(x1*1 + xe*e + ... + 1*e) = f(x1*1 + (xe+1)*e + ...) = x1 = f(x)
(same for g being 1-periodic)

This is very much not true that the basis is countable. Then we'd have R, an uncountable set, written as linear combinations of a countable set with coefficients from a countable set. Since linear combinations are finite, the set of all linear combinations is countable.

The flaw here is that you cannot get a basis just by taking the limit of independent sets as the number of elements goes to infinity. You need the full strength of Zorn's Lemma here. It turns out that every vector space having a basis is equivalent to the axiom of choice.

[flOvermind]

This is very much not true that the basis is countable. Then we'd have R, an uncountable set, written as linear combinations of a countable set with coefficients from a countable set. Since linear combinations are finite, the set of all linear combinations is countable.

I'm not sure if my proof is without flaws, but I am pretty sure that the basis R/Q is countable.

The linear combinations are not finite. You have a linear combination of countably-infinite elements, and each element can be choosen from a countably-infinite set. That's aleph0^aleph0 combinations, and that turns out to be the equal to c, the cardinality of the reals.

Another example: Q^N is a countably-infinite-dimensional vector space. But the cardinality of Q^N is certainly not countable.
Or the other way round: If the R/Q would be uncountably-dimensional, it would have to have the same cardinality than Q^R, the functions from the reals to the rationals...

The flaw here is that you cannot get a basis just by taking the limit of independent sets as the number of elements goes to infinity. You need the full strength of Zorn's Lemma here.

I'm not taking the limit of sets, I'm constructing an infinite sequence. Perhaps my notation is a bit misleading. In my notation, B is a sequence, and B_i is a prefix of the sequence (a vector). Turning that around, the sequence is the limit of the prefix vectors. If you prefer, you can forget about the limit and just read the whole thing as a recursive definition of a sequence, where each element depends on all elements before it.

What I did with that was construct a base of a sub-space. That follows directly from the construction. The remaining question is whether it is a proper sub-space, or if this sub-space is identical to the whole vector space. And that is easily shown using the dimension...

I honestly don't see a flaw in that argument...

It turns out that every vector space having a basis is equivalent to the axiom of choice.

Yes, and that's certainly a lot harder to proove. But that's more than we need for the task at hand

[Redundant]

Linear combinations are taken of finitely many elements. If there is a countable basis of R over Q, then the set of all linear combinations of these basis elements is countable.

Let B be a countable basis of R over Q. Let C^n be the set of all linear combinations of n basis elements and n elements of Q. This is countable as we can biject it to B x Q x B x Q ... n times. The finite cartesian product of countable sets is countable.

Then the set of all linear combinations of basis elements with coefficients from Q is the union of C^n over all natural n. This is the countable union of countable sets, and thus countable.

There is a surjection from the union of all C^n to R by just evaluating the linear combinations. Thus R is countable. Contradiction.

[cyclops]

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]

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

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]

13 coins. Group them A1 .. A4, B1..B4, C1..C5.
1 Balance the A's against the B's:
If equal: A's and B's are genuine.
1.1 Balance C1 + A1 against C2 + C3.
If neutral : C1 .. C3 are genuine
1.1.1 Balance C4 against A1.
If equal C4 is genuine hence C5 is false
Else C4 is false.
Else 1.1.1 balance C1 + C2 against A1 + A2
If neutral C3 is false
Elsif same as 1.1: C1 is false
Elsif opposite to 1.1: C2 is false
Else C's are genuine
1.2 Balance A1 + A2 + B2 + B3 against A3 + B1 + C1 + C2
If balance 1.2 tilts the same way as in 1 then B2, B3, B4, A4 and A3 are genuine
1.2.1 Balance A1 against A2
If again balance tilts the same way A1 is false
Elsif balance tilts the other way A2 is false
Else B1 is false
Elsif balance 1.2 tilts the opposite way as in 1 then A1, A2, B1, B4 and A4 are genuine
1.2.2 Balance B2 against B3
If balance tilts the same way as 1.2 B2 is false
elsif tilts the other way B3 is false
else A3 is false
Else balance 1.2 gives neutral then A1..A3 and B1..B3 are equal
1.2.3 Balance A4 against C1
If neutral B4 is false
Else A4 is false

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

[cyclops]

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]

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]

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]

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]

13 coins. Group them A1 .. A4, B1..B4, C1..C5.
1 Balance the A's against the B's:
If equal: A's and B's are genuine.
1.1 Balance C1 + A1 against C2 + C3.
If neutral : C1 .. C3 are genuine
1.1.1 Balance C4 against A1.
If equal C4 is genuine hence C5 is false
Else C4 is false.
Else 1.1.1 balance C1 + C2 against A1 + A2
If neutral C3 is false
Elsif same as 1.1: C1 is false
Elsif opposite to 1.1: C2 is false
Else C's are genuine
1.2 Balance A1 + A2 + B2 + B3 against A3 + B1 + C1 + C2
If balance 1.2 tilts the same way as in 1 then B2, B3, B4, A4 and A3 are genuine
1.2.1 Balance A1 against A2
If again balance tilts the same way A1 is false
Elsif balance tilts the other way A2 is false
Else B1 is false
Elsif balance 1.2 tilts the opposite way as in 1 then A1, A2, B1, B4 and A4 are genuine
1.2.2 Balance B2 against B3
If balance tilts the same way as 1.2 B2 is false
elsif tilts the other way B3 is false
else A3 is false
Else balance 1.2 gives neutral then A1..A3 and B1..B3 are equal
1.2.3 Balance A4 against C1
If neutral B4 is false
Else A4 is false

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:

As was already mentioned, it can't work for more than 3^3 = 27 coins, since that's the amount of information we get from using the scale 3 times.

Assuming we wanted to know which coin is false, plus the information whether the false coin is heavier or lighter, that would be one bit more information. The information we now need is log2(n)+1 bits, and we get 3*log2(3) bits out of the scale. That works for n=13 coins, but not for n=14. In that sense, the solution is optimal.

But the original question does not ask for the weight of the false coin. Actually the presented solution (and also mine) does not give the weight of the false coin in every variation.

So in order to improve the solution, we have to prevent finding out whether the false coin is heavier or lighter

[cyclops]

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]

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.