Math puzzles

[Redundant]

Ok. Then take the integers modulo 6.

Then let f(0) = f(2) = f(4) = 0 and f(1) = f(3) = f(5) = 3

and g(0) = g(3) = 0 g(1) = g(4) = 4 g(2) = g(5) = 2

then f(0) + g(0)=0

f(1) + g(1) =3 + 4=1

f(2) + g(2) = 0 + 2 = 2

f(3) + g(3) = 3 + 0 = 3

f(4) + g(4) = 0 + 4 = 4

f(5) + g(5) = 3 + 2 = 5

This works, but is much easier than the case from R to R. That's why you'd want to specify the domain and codomain.

[jts]

problem 2:

Take the equivalence on infinite sequences of 0s and 1s that two sequences are equal iff they differ in finitely many places. Each person knows all of the equivalence classes and they agree on a specific sequence for each equivalence class. By the axiom of choice, they can do this. When the hats are distributed, the people line up and this is one of the equivalence classes - (since each person is only one person, it will not change the finiteness of how the sequence differs from the others in the class) so each person recites whether there is a 0 or 1 in that place in the memorized sequence. This differs in at most finitely many places from the memorized sequence, so only finitely many people can get it wrong.

Shaddy, will you say a little bit more about your solution? It seems to me that a lot is riding on an ambiguity in "This" in the last sentence. You would agree, right, that when the Nth person recites his number, the maximum number of people who could have gotten their number wrong is "N", and that the number of people who have gotten their number right will be a binomial around N/2?

Looking at the other people, each person will know which equivalence class they are in (as they only fail to know the state of their own hat). Thus everyone will guess based on the same representative of that equivalence class, which differs from the true distribution in only finitely many places.

The actual sequence and the pre-selected member of that sequence's equivalence class differ in only finitely many places, by definition. But the ex ante probability that the first fellow will correctly state the color of his hat is fifty percent. (That is, if he's not in the shared portion of the sequence he's guessing, and the chance that he is in the shared portion is infinitesimally small.) And if the probability that the nth fellow will correctly state the color of his hat is fifty percent, than the probability that the n+1* fellow will correctly state the color of his hat is fifty percent. So by induction there's no limit to the number of people who are just guessing. Which is, under most interpretations of infinity I've seen, the same as saying an infinite number of people are guessing.

Think about an equivalent problem. Take a countably infinite sequence of 0's and 1's; you look at all the elements of the set except for one. If you choose any countably infinite sequence in the same equivalence class as the previous sequence, is the probability that (the hidden element in the first sequence is the same as the element in the same spot in the second sequence) equal to 1?

[Shaddy]

actually, the chance that the first guy is in the shared portion is 1, as the shared portion is infinite and the unshared portion finite. same for everyone else.

[jts]

actually, the chance that the first guy is in the shared portion is 1, as the shared portion is infinite and the unshared portion finite. same for everyone else.

Hmm, I don't think so. Knowing that a={a_1, a_2, ..., a_n, ...} and b are in the same equivalence class tells us that, for any n, there are are infinitely many i>n s.t. a_i=b_i, but it doesn't tell us anything for i<n. And we can ask, out of the entire equivalence class, what are the odds that we have chosen a sequence b s.t. for all i>1, b_i=a+i? For all i>10? For all i>1x10^100? For any n you choose, knowing b_i and aRb gives you no information about a_i for all i<n.

I'm sure you understand the problem better than I can and could explain it to me, but you're quite wrong to think that the probability that the first guy is in the shared portion of the sequences is 1.

[Shaddy]

I'm tired. I apologize- I don't understand the argument you gave in your second post very well. But I think I can prove (or at least sketch a proof) that the probability that the first person's hat matches the hat in the memorized sequence is 1 as follows:

Choose a finite subset of N. The members of this set will be the indices which differ between our sequence of black and white hats and the memorized sequence. The probability that this subset contains any given natural number is 0, since we choose some number of numbers without replacement and the probability that any given number will be chosen is 0. Therefore the probability that the first hat will be different from the memorized sequence is 0.

I think this works, anyway..

edit: is the shared portion you are talking about the set of n such that for any i > n, a_i = b_i, or the set of all n such that a_n = b_n?

[jts]

What I meant by "shared portion of the set" is aa' where a'={a_1, a_2, ... a_k} s.t. for all i>k, a_i=b_i (that is to say, aa'=bb'). If a and b are in the same equivalence class, such a subset exists by construction.

Consider a restricted subset of one of the equivalence classes to see which of our arguments you like better. Define A as the set of infinite sequences a={a_1, ..., a_n,... } s.t. for all i, a_i = {0, 1} and for all i>0, a_i = 0. Now, randomly choose two sequences, a and b contained in A. By construction, aRb. What is the probability that a_1=b_1?

The way I would do it is accept that for any i<100, exactly half of the elements of the set A have 0 as the i-th element, and half have 1. Therefore, for all i<100, aRb gives us no information about whether a_i=b_i.

By your suggested proof, we choose a finite subset of N (in this case, a finite subset of [1, 100]). Let's call it FS. The probability that this subset contains any given natural number is 0, obviously. (I think the most obviously way to formalize this statement is to say "consider the sequence {|FS|/i | i in N}. This sequence approaches zero.") Therefore, the probability that a_1=b_1 is one.

That last step of your proof is an obvious non sequitur. (Specifically, it's called the ecological fallacy.)

But of course, the chance that the sets a and b that our prisoners choose have a_i=b_i for all i>100 is infinitesimally small, because the actual equivalence classes they are dealing with are sets like A=V{A_i | i in n}, where A_i is defined s.t. the set in my example would be A_100. A_100 is only an infinitesimal subset of A.

[Shaddy]

What I meant by "shared portion of the set" is aa' where a'={a_1, a_2, ... a_k} s.t. for all i>k, a_i=b_i (that is to say, aa'=bb'). If a and b are in the same equivalence class, such a subset exists by construction.

Consider a restricted subset of one of the equivalence classes to see which of our arguments you like better. Define A as the set of infinite sequences a={a_1, ..., a_n,... } s.t. for all i, a_i = {0, 1} and for all i>0, a_i = 0. Now, randomly choose two sequences, a and b contained in A. By construction, aRb. What is the probability that a_1=b_1?

The way I would do it is accept that for any i<100, exactly half of the elements of the set A have 0 as the i-th element, and half have 1. Therefore, for all i<100, aRb gives us no information about whether a_i=b_i.

By your suggested proof, we choose a finite subset of N (in this case, a finite subset of [1, 100]). Let's call it FS. The probability that this subset contains any given natural number is 0, obviously. (I think the most obviously way to formalize this statement is to say "consider the sequence {|FS|/i | i in N}. This sequence approaches zero.") Therefore, the probability that a_1=b_1 is one.

That last step of your proof is an obvious non sequitur. (Specifically, it's called the ecological fallacy.)

But of course, the chance that the sets a and b that our prisoners choose have a_i=b_i for all i>100 is infinitesimally small, because the actual equivalence classes they are dealing with are sets like A=V{A_i | i in n}, where A_i is defined s.t. the set in my example would be A_100. A_100 is only an infinitesimal subset of A.

ah, you're right. it should be 1/2.

[cyclops]

Gocat, introducing clocks, is hot. I believe the simplest solution is:
f(x) = x and g(x) = 0 with as domain and range the integers modulo 2, that is the group { 0 , 1} in which x + y = 0 for x = y and 1 otherwise.

[flOvermind]

I think it's time for another puzzle
This one is a bit simpler, it doesn't really need advanced math, just a bit of logic thinking...

Puzzle 3
There is a set of at least 3 coins. One of them is false and has a slightly different weight. All the others weigh exactly the same. It is not known whether the false coin it is heavier or lighter.
You have a simple scale available. With it you can compare the weight of two sets of coins and determine which one is heavier.

You may use the scale at most 3 times. You have to find the false coin.

The question is: How many coins can there be for the task to have a solution, and what's the corresponding strategy?
(For example, there is obviously a solution for 3 coins. Find the two coins that weigh the same, the other one is the false one. That can be done using 3 comparisons. That means the answer is at least 3 ).

This is more or less an open puzzle. In the original version, there was a number of coins given, but my solution can do slightly better than that number. I have no guarantee that there isn't an even better solution available.

[robinz]

Quick thoughts on puzzle 3:

I'm not sure how to attack this one in general, but quickly found a solution for 4 coins. Simply take an arbitrary coin - call it coin A - and weigh it individually against each of the 3 remaining coins (B, C and D). Then either you get A being heavier or lighter than each of the other 3 (when A is the fake), or being the same weight as 2 of the others and different from the third (when this third coin is the fake).

I'd be surprised if it were possible to do this for much more coins with only 3 weighs available. (5 wouldn't surprise me, perhaps even 6, but I'd be surprised if it was more than that - but I've not tried yet.) I guess the most general problem here would be to find a formula for the minimum necessary weighs for any given number of coins. I might be able to think about this some more later, but not right now.

[cyclops]

The original problem I posted before in GoDiscussion.
The problem was solved there for n =

12

.
It will surprise me if there is a solution for any bigger n.

[cyclops]

In a two dimensional vectorspace the solution is easy.
Assume two indepent directions. The first (vector) function gives the component of any vector x along one direction. The other does likewise along the other direction.
Both functions are constant along their opposite direction and hence trivially periodic.
This is easily generalized to any multi-dimensional vectorspace.

Solution for an ordered field.
Let v be the square root of 2 and w the square root of 3, and F the field of all numbers a + bv + cw +dvw with a, b, c and d rational.
a, b, c and d are unique for any number in F.
Now from F to F define f(a +bv + cw + dvw) = a + bv and g(a +bv + cw + dvw) = cw + dvw.
f and g are easily seen to solve the problem.

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.

[flOvermind]

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)

[flOvermind]

The original problem I posted before in GoDiscussion.
The problem was solved there for n =

12

.
It will surprise me if there is a solution for any bigger n.

My solution is very similar to the solution of the original problem, and it works for one more coin.
(EDIT: I don't remember the problem on GD, so I don't know what your solution looks like. But I doubt there are that many different solutions for the original problem ).

[robinz]

Further thoughts:

OK, I've come up with solutions for 5,6 and 7 coins. What is pleasing is that they are essentially the same

So, take n=5 first. As before I'll label the coins alphabetically. First, I shall weigh A and B against C and D. If the two sides balance, we know E is the fake. If not, we weigh B and C against D and E - if both sides of this balance then A is the fake. Note, for future reference in the n=6 and n=7 cases, that it is impossible for them both to balance, as we know one (and only one) of the coins is fake.

So, assume neither weighing balanced. Then there are 4 possibilities, which I list in notation which I have just made up, but is hopefully easy-to-understand:
1) AB<CD, BC<DE
2) AB<CD, BC>DE
3) AB>CD, BC<DE
4) AB>CD, BC>DE

Now, if B were the fake, then we would get either scenario 1 or scenario 4, depending on whether B was lighter or heaver than the rest. The same if D were. If C were the fake, we would be in scenario 2 or 3. Thus, if 2 or 3 occurs, we already know C is the fake. And if 1 or 4 does, then we know the fake is one of B or D. So, for our third weighing, we simply take one of these and weigh it against one of the three known non-fakes - if it fails to balance, we've picked the fake, and if it balances then the fake must be the other one.

OK, that's n=5. But for n=6 we can simply ignore coin F for the time being, and do exactly the same thing. The thing to note is that, if F is the fake, then both of the first two weighings will balance, and this is only possible if F is the fake. Thus we know in only two weighings if the fake is F, and if it isn't we simply reason as for n=5.

For n=7, the only difference is that, if the first two weighings balance, the fake might be either F or G. But again we can figure out which by simply weighing one of them against any of A to E.

I can't be bothered to try to figure out how to do n=8 or higher for now - I suspect it'll be something similar to the above, but now involving sets of 3.

It's also worth pointing out that the problem certainly isn't soluble for n>27, as 27 (=3^3) is the maximum number of different possible outcomes of 3 weighings. Of course, this doesn't mean that it's possible for all n<28, just that it's certainly impossible for n>27.