On May 13 2009 02:06 travis wrote: this shit is actually answerable?
Yup it is. But it's completely counter-intuitive.
hell, shouldn't this be unanswerable just given there are infinite numbers?
If you had a finite number of boxes, there is no way you could win. But you have an infinite number of boxes.
or can number values not exceed total boxes?
No they can be anything.
If you prefer, i can restate the problem like this (i should have done so at the beginning, because i was not clear that the probability of success does not depend on how the host chose the numbers):
construct n strategies, such that all of them win, except one.
For instance, suppose that you know that in box 42 there is a 0 or a 1. Then you have 2 strategies: i announce a 0 in box 42, and i announce a 1 in box 42. If you choose the strategy you use at random, you have 1/2 chance of winning (it does not depend on how the host chose the number he put in box 42). In practice your strategies will be more complicated, like "i open this infinite number of boxes, then from what i see i open this other infinite number, then from what i see, i chose a closed box and announce this number.
On May 13 2009 01:02 evanthebouncy! wrote: I suppose we make functions again, let's call them f_1, f_2, f_3... f_1(1) = number in box 1 f_1(2) = number in box 2 f_1(3) = number in box 3 and so on.
Yes, that's the idea
I suppose that f_i is the sequence associated to column i? So that if you split your boxes in n column, you have n sequences?
The total number of functions I suppose, are N^N.
Yes, the f_i can be anything in N^N.
I guess we can ask these questions, if u guys want to help me answer them: Take all these functions, put them into a set, call it F. is F complete? if we think of each element in F as a vector of size NxN, can we find a "basis" of some sort for F? is there a "standard" basis for F? how do we "project" in F?
- Here i am not following anymore. What is F? - You just need to use set theory for this puzzle, you don't need to use the structure of vector spaces, or convergent sequences. Anyway N^N is not a vector space. Now R^N is, but a basis of this space would be uncountable. - What you can do is define equivalence relations ~ on N^N, then use CHOICE to get a section of N^N -> N^N/~, like was needed for problem 1. (that is to every equivalence class associate a representative).
On May 13 2009 02:39 travis wrote: well then given that u have an infinite number of boxes, why does it matter what number u answer for them
hell, just answer the same number for every box
maybe im still not understanding this though
why does it matter what numbers you saw in previous boxes?
No no, you only give *one* answer. But before you give your answer, you can see as many boxes as you wish. Then you choose a closed box, and give an answer.
so here's another easier puzzle which seams related, i don't know how to solve gondolin's one:
3 of you are at a dinner party and the host has black and white hats again (i love 'em). He gives them to the three guests at random so that you can't see which colour you have on.
Now you have the option to guess the colour you have on, if you or your mates are right, you win, if any of you guess wrong, you lose. If you say nothing, the hats are taken off and new ones are put on.
you can't ever be sure of wining but here's a strat that gets you about 3/4
if you see black black, you guess white, if you see white white, guess black. if you see a mix, pass.
the odds of 3 the same colour is 1/4, hence if you see two the same there's a 3/4 chance you're a different colour.
apparently there's a strat that will give you better than 50% winning even if the host knows what you're doing and tries to counter it. I can't remember the exact statement, maybe he has to not know you know he knows... or something, if not it's sounds really promising.
I may be misunderstanding the problem, but that doesn't seem right. Even if you see two white hats, the probability of your hat being black is still 1/2 (I'm assuming each hat is chosen by coinflip)... http://en.wikipedia.org/wiki/Conditional_probability
--
I am unconvinced that a (correct) solution to this thread's problem exists (I was unconvinced by the solution to the original problem by drift0ut for a similar reason).
If the host picks the numbers in the boxes by rolling a die, the number in any one box is independent of the numbers in any of the other boxes. So the laws of probability tell us that you have 1/6 probability of getting the answer correct (assuming you pick a number in {1,2,3,4,5,6}) no matter how much prior information you have (from opening other boxes). I don't see how infinities change any of this? An infinite amount of useless information is still useless?
Here's a writeup for the case n=2. The general case is quite similar but much more annoying to writeup. Solved by a computer science grad student on my hall. + Show Spoiler +
Call two infinite integer sequences equivalent if they differ in finitely many places. We use choice to select a special element from each equivalence class.
Divide the boxes into two infinite columns of boxes, column 1 and column 2. For each finite subset of boxes in column 1, associate a unique box in column 2. We describe two strategies.
Strategy 1: Open all the boxes in column 1. Mark all boxes in column 1 which differ from the special element of column 1's equivalence class. Set aside the box in column 2 associated with the finite collection of marked boxes. Open the rest of the boxes in column 2, and guess that the unopened box has the same number as the special element of the equivalence class of column 2 does in that position.
Strategy 2: Open all boxes in column 2. Mark all boxes which differ from the equivalence class of column 2. For each marked box in column 2, mark the finite set of boxes in column 1 which correspond to that box. Set aside an unmarked box in column 1. Open the rest of the boxes in column 1, and guess that the unopened box has the same number as the special element of the equivalence class of column 1 does in that position.
Flip a coin to select your strategy. If one fails, the other must succeed.
On May 14 2009 14:41 Muirhead wrote: Here's a writeup for the case n=2. The general case is quite similar but much more annoying to writeup. Solved by a computer science grad student on my hall. + Show Spoiler +
Call two infinite integer sequences equivalent if they differ in finitely many places. We use choice to select a special element from each equivalence class.
Divide the boxes into two infinite columns of boxes, column 1 and column 2. For each finite subset of boxes in column 1, associate a unique box in column 2. We describe two strategies.
Strategy 1: Open all the boxes in column 1. Mark all boxes in column 1 which differ from the special element of column 1's equivalence class. Set aside the box in column 2 associated with the finite collection of marked boxes. Open the rest of the boxes in column 2, and guess that the unopened box has the same number as the special element of the equivalence class of column 2 does in that position.
Strategy 2: Open all boxes in column 2. Mark all boxes which differ from the equivalence class of column 2. For each marked box in column 2, mark the finite set of boxes in column 1 which correspond to that box. Set aside an unmarked box in column 1. Open the rest of the boxes in column 1, and guess that the unopened box has the same number as the special element of the equivalence class of column 1 does in that position.
Flip a coin to select your strategy. If one fails, the other must succeed.
Congrats Muirhead! (by the way since your in MIT, do you know someone called Denis Auroux? I think he is a teaching assistant there, and he comes from the same school as me... I have heard he was quite popular there)
So you choose a choice function s on the sequences modulo cofinite equivalence like you did (the same function as for the hats problem). You split the boxes into n sequences u1, u2, ..., un.
Now s(u1) is a sequence that is equal to u1 on a cofinite set. This mean there exist A1 such that s(u1)_n = u1_n if n >= A1. Define in the same way the numbers A2, ..., An.
Now you open all the boxes for u1, u2, ..., u(n-1). This allow you to find the numbers A1, ..., A(n-1). You take A=Max(A1, ..., A(n-1)), and you open all the boxes in the sequence un except (un)_A. Now you give s(un)_A as your answer, you win if An<=Max(A1,...,An-1).
So you have n strategies (depending on the column you don't open at the beginning), and only one may fail.
EPT
