Two Numbers

So, about a year ago, I posted a puzzle based on the two envelope paradox. I had intended to finish that one off with another puzzle, but then I guess I forgot to. Now I have learned about a follow up to that puzzle, but I can't exactly post i until I have posted the original. Anyway, here we go:

Alice writes down two distinct real numbers and puts them into two separate envelopes. Bob then selects one of the envelopes to open randomly (50-50 chance) and looks at the number. Bob must then guess whether the number he is looking at is the larger of the two or the smaller of the two. Find a strategy for Bob that is guaranteed to succeed more than 50% of the time, no matter what numbers Alice chooses.

Its very similar to the final problem I posted a year ago, so I'll give the solution out in the next few days so we can move on to the real problem. Its trivial for Bob to do 50% simply by flipping a coin to decide his answer, but doing better just seems crazy. If you need, feel free to assume Alice is choosing her numbers from an unknown but well defined distribution over the reals.

Two Answers

The puzzle of the three princesses has been up far too long for how simple it is, I suppose its time for the solution.

Its actually quite easy, first number the princesses 1, 2, and 3 and then ask princess number 1:

Is princess 2 older than princess 3?

Then, based on the answer you get

yes: marry princess 3
no: marry princess 2

Easy enough, if princess 1 was the truth teller, then you aim to marry the younger one. If princess 1 was the liar, you aim to marry the older one. If princess 1 was the middle sister, then it does not matter who you marry, as long as it is not her.

I suppose that it was a bit of a lie when I said this is not a meta-question, since asking about the "truthiness" of other sisters is something of a meta-question, and asking about their ages is equivalent to asking about how much they tell the truth in this problem. I don't know though, the answer seems elegant enough, and its hardly going to count as a trick or "communicating badly" to have an answer involve their ages when it is said so clearly in the problem.

Anyway, yea, thats the answer as I know it, if you have any other possible answers feel free to say them in the comments.

Three Princesses

New puzzle time, I found this one some time ago on the forums at xkcd, but I wasn't sure if it was the style of puzzle I like to have here. Upon further consideration, and a lack of new puzzles to put up, I have decided that this is a good puzzle after all.

You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and answers questions with either yes or no, however she pleases, ignoring the question asked.

As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them.

The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you a single yes or no question which you may only address to one of the sisters. After your question, you must select a princess to marry. What yes or no question can you ask which will ensure you do not marry the middle sister?

Its mostly a standard "knights and knaves" scenario, and I typically dislike these sorts of puzzles because the answer is invariably some bizzare meta-question (that is, a question of the form "If I were to ask that person '(insert question here)', what would their answer be?"). However, the 'intended solution' to this problem has no meta-questions involved, actually it is quite elegant. Given the nature of the question, it probably has a bunch of other solutions too, so it could also be interesting to see if anybody posts an answer I haven't seen.

They'll Get There Eventually

Alright, the Sending Scouts Into The Desert problem has been up there with no solution for far too long, I suppose its time to post the solution. I'm going to proceed assuming that you have not already read the solution over at cut the knot and basically steal their derivation.

We will do the solution case by case first. For N=1, it clearly takes two pieces, one on the first line and one on the second line. For N=2 it takes 4 pieces, 3 on the first line and 1 on the second line. N=3 is a bit less trivial, but it won't take long to find that you need 8 pieces. So, so far the pattern goes 2,4,8, so it looks like N=4 should take 16. This is actually not the case, if you try it you won't be able to get to N=4 with less than 21 pieces (cut the knot says you only need 20, but I am reasonably certain that they have made some error, I cannot find anything better than 5 on the first line + 5 on the second line + 5 on the third line + 5 on the fourth line + 1 on the fifth line).

For N=5 the situation is even more interesting though, you cannot get to the fifth line with any finite number of pieces. To see this, let us consider a function that maps board configurations onto integers. We will later arrange the function so that legal moves do not increase the value of the function, so you cannot reach a higher-valued configuration from a lower-valued one, and use this to prove that we cannot reach the fifth line.

Let us assign a number to each square of the checkerboard, and the function will simply add up the numbers at the locations where we have pieces. We will arrange the numbers so that legal moves never increase the value of the function. Let us assume that somebody claims to have reached a particular square on the N=5 line of the board. We will assign that square a value 1. The four squares that neighbor it will be assigned a value x (we will fix x later). The next 8 neighboring squares will be assigned value x². The next 12 neighboring squares will have value x³ and so on out to infinity. More concisely put, we have the "master square" of value 1 and a square that is K spaces away (taxicab metric) from the master square has value x^K.

Let us consider a generic legal move, where piece A jumps piece B. There are three types of things that could have happened from this. First, A could have landed closer to the master square than it was before. In this case, A started on x^m, while B started on x^m-1, then A ended on x^m-2. To ensure that the function is nonincreasing, we need

x^m-2 ≤ x^m-1+x^m

The second type of move has piece A moving further away from the master square. In this case, A started on x^m and B on x^m+1, with A ending on x^m+2. For a nonincreasing function, we need to have

x^m+2 ≤ x^m+1+x^m

The third type of move has piece A staying the same distance from the master square. In this case, A started on x^m and B started on x^m-1, with A ending on x^m. So we need to satisfy

x^m ≤ x^m-1+x^m

This condition is satisfied easily if x is a nonnegative number.

Let us assume that the first condition is an equality (this means that moves toward the master square will conserve the value of the function, rather than decrease it). Dividing out x^m-2, this equation solves to 1-x-x²=0, meaning that

x=(√5 - 1)/2

There is another root, but it was discarded because x must not be negative. This x is actually the inverse of the golden mean. The last equation remaining is also satisfied by this choice of x, as you can confirm easily.

Now, supposing as before that the master square is on the fifth line, it is the place on the fifth line that somebody claims that they can reach using some path of legal moves. This configuration has value 1 (or more, if they had extra pieces lying around), so their initial configuration must also have value 1 or more. What is the maximum value you can get with a configuration of pieces in your base to start? You have at most 1 piece on x⁵, at most 3 pieces on x⁶, at most 5 pieces on x⁷, at most 7 pieces on x⁸, and at most 2n+1 pieces on xⁿ⁺⁵. Thus, the most value of pieces you can have is

Σ (2n+1) xⁿ⁺⁵

the sum running from 0 to infinity (actually this isn't really the most you can have, its actually more than you can have with any finite number of pieces, but its how much you could have with an infinite number of pieces).

We can simplify the sum to

2x⁶Σ nx^n-1 + x⁵Σ xⁿ
= 2x⁶ d/dx Σ xⁿ+x⁵Σ xⁿ

Of course, the sum &Sigma xⁿ is 1/(1-x) (since x is between -1 and 1) so we have

2x⁶/(1-x)²+x⁵/(1-x)

Now we use 1-x=x² (the quadratic that x solved) to simplify this to

2x²+x³
=x²(2+x)
=(1-x)(2+x)
=2-x-x²
=1

Therefore, no finite number of pieces can have total value 1, so no finite number of pieces can make a series of legal moves that ends with a piece five lines deep.

I suppose one can still imagine an infinite number of pieces doing it, but it will also take them an infinite number of moves, so its not clear that it really makes any sense to talk about such a thing.

Sending Scouts Into The Desert

The problem I have this time is a bit of a weird one, I mostly only show it because it has an amazing solution and proof. I first found this puzzle at Cut The Knot, which is something of a math puzzle page.

Consider an infinite 2-dimensional checkerboard. The upper half of the board is called the "desert" and the lower half of the board is called the "base", and there is a line across the middle that divides the two (just to be clear, there are no squares between the desert and the base, every square is either in the desert or the base).

You will be playing a one player game on this board. First you set up as many checkers anywhere you want in the base (each square may only be occupied by one checker). Then you begin making your moves. A move consists of a checker jumping another single checker that is orthogonally adjacent to it and landing on the space on the other side (which was unoccupied before). The checker that is jumped over gets removed.

The goal is to get one of your pieces as far into the desert as possible. Find how many pieces it takes to get N spaces into the desert.

That may have been a bit awkward to read, however there is a nice applet at Cut The Knot that will allow you to play this game. That page also has the solution to this problem, so don't scroll too far down unless you are ready to see the solution. The solution that is there is quite well written though, and when I post the solution to this next time I'm basically just going to be following his derivation.

The Value Of One Bit

I was looking over my "solution" threats, and it seems that about 90% of them begin with "time to post the solution to", so I figure I'm about sick of that. Sick of it this week anyway, next time I'll be back to it. Anyway, now that I have actually began the post with something different, time to post the solution to the bit in a bottle problem.

First I will give my formulation of the solution, and then I will show that it is optimal in a sense (a pretty convincing sense as well, not just some esoteric one). First, consider what happens if you just bet heads all the time. Your total money will simply preform a random walk on the integers starting with N, and will terminate if it ever hits zero. With probability 1, it will hit zero in finite time.

Now, I will construct two strategies, first define the following strategy

Strategy H: Every game, bet heads until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Similarly, define a strategy for tails

Strategy T: Every game, bet tails until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Now, we can show that one of these strategies will hit $0 and the other will hit $2N (this should be pretty intuitive, but lets prove it anyway). For a particular sequence of flips, let M(S,k) be the amount of money that strategy S will have after k flips. Then I claim that

M(H,k)+M(T,k)=$2N

This is easy to prove by induction, as it is true when k=0 and every time strategy H gains $1, strategy T loses $1 and vice-versa. The strategies also terminate at the same time, as failing to do so would violate the equality. It is theoretically possible that the strategies do not ever terminate, but that has zero probability of happening.

Now, the question we ask the genie is simple. First define strategy H for the genie, then ask:

If I follow strategy H, will I end with $0?

If the answer is yes follow strategy T, if the answer is no follow strategy H. This guarantees that you will end with $2N (where "guarantees" means "with probability one"). You can also change strategy H to any specific betting sequence rather than all heads if you like, as long as strategy T is the compliment of that sequence, this will still work.

Next I want to prove that this solution is optimal. It might seem surprising that we can optimize over the space of all possible questions, since math usually is not very good at handling human language. To deal with this, first consider C to be the set of all the possible coin flip results, so C contains things like HHTHH..., THTTH.., TTTHT..., and so on. Next consider a possible yes or no question, denoted Q, that for every element of C the question must answer exactly "yes" or "no". Thus Q partitions C into two disjoint subsets, called Y and N. Really, any Q is equivalent to selecting the sets Y and N and asking the genie "is the coming sequence of coin flips in Y?" So, to optimize over all questions Q, we really just need to optimize over choice of sets Y and N, and it is less surprising that math can handle that.

Before moving on, I must state an obvious but important fact of probability theory. Consider we have two disjoint events, X and Y (that is to say, exactly one of them must happen (thats not actually what disjoint means, but I don't know the correct term)), and a third event called A. Let P(x) is the probability that event x happens, and P(x|y) is the probability that event x happens given that event y happened. Then, the probability that event A happens can be written as:

P(A)=P(A|X)P(X)+P(A|Y)P(Y)

That is, A must happen with X or Y, so we calculate the chance it happens with X plus the chance it happens with Y. We need not subtract the chance it happens with both, as X and Y are disjoint. It is easy to generalize this to more disjoint events X,Y,Z,... We can also make a similar statement about expectation values, let E(A) be the expectation value of some variable A and E(A|x) is the expectation value of A given that event x is true. Then for disjoint events X and Y we have:

E(A)=E(A|X)P(X)+E(A|Y)P(Y)

An intuitive result, to be sure, but an important one anyway.

OK, now that that is out of the way, the next important step in the proof is to consider what will happen with no genie. Suppose you have some strategy S, and after k flips the strategy has an expected value E(S,k). The expected value will be determined by the chance that you went up a dollar on that flip (call that P(+)) and that chance that you went down a dollar on that flip (call that P(-)), and the chance that your strategy had told you to stop (call that P(O)). Specifically:

E(S,k+1)=(E(S,k)+1)P(+)+(E(S,k)-1)P(-)+E(S,k)P(O)

It is clear that P(+)+P(-)+P(O)=1 (since every round you either gain a dollar or lose a dollar or stop), and also P(+)=P(-) since without access to a genie we have no knowledge about the coin flips. This means that:

E(S,k+1)=E(S,k)

So, E(S,k) is a constant, and that value must equal $N, since E(S,0) is $N. This proves that with no genie, all strategies have the same expectation value after a fixed number of flips. Note that something funny happens if you just let k=∞ since strategies such as "play until I run out of money" are guaranteed to have zero money at the end, even though after a finite number of flips there is a chance of the player having a large amount of money for the time being (this is known as the "gamblers ruin").

Alright, now let us find what is the best we can do given our genie scenario. First let x represent the coming sequence of coin flips, the genie knows the value of x. Consider that we have a strategy specified by a question Q (which simply selects the sets Y and N), a strategy S(Y) (which is what we will do if the genie tells us x is in Y), and a strategy S(N) (which is what we will do if the genie tells us x is in N). We want to find E(S,k), the expectation value of our strategy S (=(Q,S(Y),S(N))) after k flips. Letting Y represent the event "x is in Y" and N represent the event "x is in N", we see that Y and N are disjoint events, so that:

E(S)=E(S|Y)P(Y)+E(S|N)P(N)

I really should have some k's in there also, but they are going to get cumbersome so I am just going to drop them for now. Now, E(S|Y) is just E(S(Y)|Y), since S says to play S(Y) when Y is true, also E(S|N)=E(S(N)|N) for the same reason. That is to say

E(S)=E(S(Y)|Y)P(Y)+E(S(N)|N)P(N)

To get any more information out of this, consider again what would happen to us with no genie. We could just play S(Y) anyway, but we already know that E(S(Y))=$N (one would expect that E(S(Y)|Y) would be higher, since then we also know that x is in Y, but if we just play S(Y) with no other information then its expectation value is $N) (I must say this is only true after k flips, if the number of flips is infinite weird things might happen). How else could we calculate E(S(Y))? we could just consider if x is in Y or N, specficially

E(S(Y))=E(S(Y)|Y)P(Y)+E(S(Y)|N)P(N)

That is the value of strategy S(Y) when Y is true plus the value of strategy S(Y) when N is true (remember, we have no genie right now). Now since E(S(Y)|N) cannot be negative, and P(N) cannot be negative, that second term cannot be negative. Thus we have a bound on E(S(Y)|Y)P(Y), given by

E(S(Y)|Y)P(Y) ≤ $N

Similarly, switching Y for N we have

E(S(N))=E(S(N)|Y)P(Y)+E(S(N)|N)P(N)

and therefore

E(S(N)|N)P(N) ≤ $N

We can put this together in our last equation for E(S) to get

E(S) ≤ $2N

Proving the optimality of the solution presented earlier. It appears that the value of one bit is to exactly double your cash. If you can instead ask the genie a question with possible answers 1,2,3,... up to some fixed K then you can extend this proof to show it is optimal to multiply your money by K.

Naturally, it is possible to get other strategies to end with more than $2N, they just cannot guarantee ending with that much. Even with no genie one can simply play the game and only quit if you hit $0 or $3N, you might end with $3N in this case, but it cannot be guaranteed. I will also point out that the proof relied on the game not taking an arbitrarily long amount of time, my intuition is that the result is still valid even without that assumption, but I do not see a good proof.

I do like this solution in that it is practical, one would reasonably use it if actually presented with this situation, and the genie does not even need to do an infinite amount of work (probably not anyway, its possible that the random walk never terminates, but thats probability zero). The genie can even be replaced by a mathematically competent human who simply has access to the coming flips.

There is a harder problem posed of the xkcd forums where losing a flip costs you a $1 and winning a flip gains you $(1-q) where q is a small positive number. I have not made any real progress to finding a solution to this problem, but anything involving random walks seems risky, so another approach might be needed.

Bit In A Bottle

New puzzle time I suppose. This one looked like it was a bit of a silly one, but it turns out that there is a bit more interesting math in it than I expected. I first found this on the forums at xkcd:

You are playing a game where you are betting on the outcome of coin flips. Playing the game costs $1 and you get to guess either heads or tails. A coin is then flipped and if you guessed correctly you win back your $1 and another $1, if you guessed wrong you lose your $1. You may play the game as many times as you want as long as you have the money to continue, or may quit anytime. Before the game, you have access to a genie that will answer any one yes/no question about the coin flip game. The genie knows the results of all the coming flips. Given that you start the game with $N, find a strategy that maximizes your winnings.

Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.

Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.