|
Hello everyone, and welcome to my first blog.
This blog is meant to be the following of a blog post by driftOut:
http://www.teamliquid.net/blogs/viewblog.php?topic_id=93007
about a very nice puzzle.
The solution uses equivalence choice, and evanthebouncy! made an excellent didactic course about it here:
http://www.teamliquid.net/blogs/viewblog.php?topic_id=93015
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!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tell me what you think about it!
|
Umm, if the host is free to put any number in a box, and repeat at will, what does it matter what was in the other boxes?
Seems like all the events are independent and your chance to win is unaffected by how many boxes you open before.
I guess I'm missing something =/
|
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?
Yes. Sorry if that wasn't clear.
|
please define n
is that how many boxes you are opening?
|
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?
|
it's N ^ N not N x N
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...
|
Damn edit slow. Anyways im almost sure but now im doubting. 
|
yeah just remembered NxNxN..xN is countable for any number of ns but N^N doesnt.
|
|
|
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.
|
Err let's seee...
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?
Integers.
+ Show Spoiler +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?)
|
this shit is actually answerable?
if there are infinite numbers and infinite boxes I don't see how this is answerable
hell, shouldn't this be unanswerable just given there are infinite numbers?
I don't understand how this could be answerable -.-
|
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.
|
|
|
|
|
|
EPT![[image loading]](http://img152.imageshack.us/my.php?image=31397418.jpg)
