Now if you were interested in the first puzzle, i'll propose you one that is even harder, and even more impressive. Feel free to ask questions if the problem is not stated clearly enough.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ You are playing a game. In this game there is an infinite (countable) number of boxes, and in each box a number. The host is free to place any number inside a box (and he can place the same numbers into different boxes).
You can open as many boxes as you want (even infinitely many), as long as you leave at least one box closed. You then state the number you think there is inside a closed box. You win if you guessed the right number.
How do you play? What i pretend is that for every n>0, you have a strategy so that your probability of success is greater than 1-1/n! In other word you can't always win (duh!) but you have a strategy that gives you 999 999/ 1 000 000 chances to win! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Yes it's confusing, and counter-intuitive, but it's because we are dealing with an infinite number of boxes, hence our "intuition" does not apply. It's not like it could happen in real life I agree that if the number of boxes were finite, there is no way you could win.
So the host puts all the numbers in the boxes *before* you open them. He is not allowed to change them afterwards. He does not know which box you will choose to leave closed, and remember that you can open all the boxes except one.
My friend wants to clarify what you mean by any number: integers, real numbers, etc. He's saying that the set determines whether the numbers are countable-infinite or not.
By number i mean an integer, that is an element in the set {0,1,2,3,...}. so if you count, the ways the host can set up the boxes is N^N, which is not countable.
(that is, if you number the boxes, you have a sequence that to the box number n associates the integer inside it. Then every sequence is possible, and you have no information about how the host will choose is sequence).
This question is very ill-defined. What do you mean by probability? There is no random probability distribution for assigning (non-negative) integers to boxes. Also, if we leave two boxes closed and guess a number in one of them, do we have to state which of the two boxes we think that number is inside of?
On May 12 2009 23:42 Muirhead wrote: This question is very ill-defined. What do you mean by probability? There is no random probability distribution for assigning (non-negative) integers to boxes.
Yes i know. But i did not want to be too formal.
The correct way is this: for any n>0, you can devise n strategies, such that n-1 of them will succeed (but you don't know which may not succeed of course). (since n is finite, you can speak about the probability you will choose a winning strategy).
Also, if we leave two boxes closed and guess a number in one of them, do we have to state which of the two boxes we think that number is inside of?
Basically I realize I dont understand anything about the problem. Questions: 1- That about opening and closing box does something in the game? 2- You meant to solve the problem in terms of n. What is n? 3- Numbers in boxes are integers? rational? real? complex?
I honestly don't remember my combinatorics well enough to tell you if N ^ N for a countably infinite N is uncountable or countable, but I'll take the OP's word that N ^ N is uncountable...
On May 13 2009 00:07 Mogwai wrote: please define n
is that how many boxes you are opening?
Ok i can explain a bit more how the strategy works (it is an insanely hard problem anyway), but it would be nice if some peoples would give strategies, even if they don't work.
Let n be an integer > 1. You split the boxes in n column. You select a special column x, were you will leave a box closed. You open the boxes in every other column, and use that information to know what box you will leave closed in the column you have chosen.
What i pretend is that there is a way to choose the closed box and the number you announce in thus a way that for any column x you have chosen at the beginning *except one*, you will win.
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.
The total number of functions I suppose, are 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?
Suppose we could answer yes to all of the above questions, then we let g_1, g_2, g_3 ... to be our basis Project our function vector, f_something, onto those g_1, g_2, g_3 ... See if we get it to converge to something fancy... O_o
On May 13 2009 00:30 Malongo wrote: Basically I realize I dont understand anything about the problem. Questions:
Yeah it is quite a hard problem to state correctly, without being too formal. I don't want to scare everyone :/
1- That about opening and closing box does something in the game?
When a box is closed, you don't see the number inside it. You have to open it if you want to know which number there was. You can open as many boxes you want, in the order you want, you just have to leave at least one closed. Then you pick a closed box, announce the number in it, and you win if you were right.
2- You meant to solve the problem in terms of n. What is n?
You choose it yourself. For any n you can construct n strategies. All of them will work except one. If you choose the strategy at random, you have 1/n chances of picking the bad strategy. So say you want to win with probability 999999/1000000, you take n=1000000, you construct your n strategies, pick one at random, and voila.
3- Numbers in boxes are integers? rational? real? complex?
Don't read this, this is more confusing than anything.
Since the rationnal are countable, you can play with rationnals too. In fact you could even play with reals or complex, but the problem is that you would have to speak infinitely long to define the real entirely (ok in real life there won't be infinitely many boxes, and you would take infinitely long to open them all minus one anyway...)
My intuition is failing me on this one. She says that this is not possible. Let me try spelling out what my problem is, and perhaps someone can tell me where I am erring:
I can conceive of being able to make an "educated guess" in some circumstances. For instance, suppose that you open all boxes but one, and each contains a 9. Then it seems likely that the remaining one contains a 9 as well. (This would certainly be true for very large finite numbers, although infinities are harder to reason about intuitively.)
However, suppose the host uses a strategy designed to prevent any box from shedding light on any of the others. I suppose that the host is capable of picking truly random numbers (i.e. effective probability 0 of picking any given number). Then let him select the numbers as follows.
1) Number the boxes (since they are countable). 2) Select a random number and place it in the first box. 2) Select a random number that has not been used yet and place it in the second box. 3) and so on until all boxes are filled (obviously it's not really an iterative process). 4) Throw out the even boxes.
Now, even if you know the contents of all boxes but one, all you know is an infinite set of numbers that cannot be in the last box. But by step 4, there is guaranteed to be an infinite set of numbers that you have not seen: one of them must be in the box and any of them can be in the box, since the selection was truly random. How can your knowledge of the other boxes help you in any way with this problem, which is essentially to guess a single number from an infinite set?
(I suspect that you may take issue with my assumption of "true randomness". If so, could you be as specific as you can about the host's ability to choose numbers?)
On May 13 2009 01:24 qrs wrote: My intuition is failing me on this one. She says that this is not possible. Let me try spelling out what my problem is, and perhaps someone can tell me where I am erring:
Yes, it is quite counter intuitive, because we are dealing with infinites.
I can conceive of being able to make an "educated guess" in some circumstances. For instance, suppose that you open all boxes but one, and each contains a 9. Then it seems likely that the remaining one contains a 9 as well. (This would certainly be true for very large finite numbers, although infinities are harder to reason about intuitively.)
Well it depends. If you select uniformly a number in [0, 10^n[, then even if (n-1) digits are equals to 9, the remaining one is uniform in [0,9].
(I suspect that you may take issue with my assumption of "true randomness". If so, could you be as specific as you can about the host's ability to choose numbers?)
Well, yes there is no true probability on the whole N, but the true problem is that there is an infinite number of boxes, and the player can choose the box he will guess according to what he sees. What the host choose is a sequence of integers, and he can choose any sequence (even a non calculable one).
Suppose to simplify that the numbers are restricted to be {0,1}. Now say that your strategy is "whatever i see, i pick the box 42 and announce 0". You can't really know your probability of success because it depends how the host chose the sequence. Let's say you identify the sequences with value on {0,1} with the set [0,1] (by taking the diadic decimal reprensentation of a number, ignore the fact that 1=0.111111111). If the host take is number x in [0,1] uniformly with respect to the lebesgue measure, then your strategy has 1/2 chance to win. But here you chose in advance what box you would leave closed, and it's value is independant from the values of the other boxes. So you can't do better like this.
What is worse is that you don't know how the host choose is number. The probability of success i am speaking about does not depend on the way the host choose the number, but on what strategies you decide to use. For instance, suppose that you are sure that number 17, 42 and 54 are 0, except maybe one of them. Then you choose one of them at random, and you have 2/3 chances of winning. This proba does not depend on the original sequence, it's just the losing number that will depend of it.
Of course in practice there is no way you will be sure that 17,42 and 54 are 0, but you can use the fact that you can chose which box you will guess, depending on what you have seen. In the finite case, this would change nothing, but here it is completely different! Hence why the intuition fails.
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
I agree that if the number of boxes were finite, there is no way you could win.
![[image loading]](http://img152.imageshack.us/my.php?image=31397418.jpg)
