Two Envelopes

So, this time I have a logic puzzle wrapped in a paradox. I'll introduce the paradox first, then the puzzle, then sometime over the next few weeks I'll resolve the paradox. Here is the setup:

A rich man has decided to give away some money to you. He selects a number, and writes a cheque for that amount of money and puts it in an envelope. Then he writes a cheque for twice as much money and puts that in another envelope. He shuffles up the envelopes and hands one to you. You look inside and see $100. Then he offers you the chance to switch envelopes. You know that you got the smaller or larger envelope with 50/50 chance, and the other envelope contains either $200 or $50, thus on average it has $125, therefore, you should switch. However, you can reach the conclusion that you should switch without even looking in the first envelope, as the other envelope contains 5/4 times as much, on average.

Clearly something is wrong here, one can find some time exploring to find out what the deal is. It basically comes down to the problem of saying "he selects a number", you cannot select a random real number without specifying a probability distribution. I'll go more into that later, but for now:

Assuming the initial amount of money is selected from a well defined (but unknown) probability distribution, there is a strategy that guarantees more money than one would get by just simply keeping the first envelope or by just switching blindly. What is the strategy?

Certainly the strategy must work for any choice of probability distribution, its sort of neat to know that it can exist.

Robots On A Circle

Alright, time for the solution to the robots on a sphere problem.

It is something of a neat problem, because many people get tripped up right away with the following idea:

If both robots start on opposite sides of the planet facing opposite directions, they will stay that way forever, always mirroring eachothers moves and never finding eachother, no matter what their program is.

This argument actually seems pretty rock-solid, and I spent some time wondering why this problem has such a blatant hole in it, but there is a way out, if you know that the robots are going to start in such a configuration, the solution is this:

Each robot takes a 90 degree turn right, and then moves forward.

This will cause the robots to turn and face eachother, and move forward until they meet 'halfway' (grab a convenient sphere and try it out if you don't believe me). It becomes clear that any solution that is going to cover the extreme case of robots on the opposite side of the planet is going to need to refer to handedness somewhere, using the word 'right' or 'left'.

Now, we may assume that the robots drop off their flags as soon as they land (waiting will not really help anything), and it is easy to see that any two distinct points on the sphere uniquely define a circle on that sphere. The circle can be found by taking the set of points that are equal distance from each of the two points. In the case where the two points are antipodal, the circle that results is the 'equator'. Now that the robots have found a circle that they agree upon (they can find eachothers flags easily, given their own size and the radius of the planet), we just need them to get walking along that circle in opposite directions. Have them travel along the circle with their own flag on the right, this will result in the going opposite directions along the circle, they will meet up eventually.

Robots On A Sphere

So, the blog seems to be reverting to a semi-weekly thing (where semi-weekly means every other week, not twice a week, which is apparently semi-standard english (where semi-standard means half standard, not twice standard, at least I'm consistent)). Anyway, I first found this puzzle on the xkcd forums:

Two robots are being sent to a planet, and you will have to write an algorithm for the robots to find eachother. The planet is a perfect, featureless sphere of known radius, and the robots are of a size epsilon (epsilon is small compared to the size of the planet). The robots each have a single flag that they can place anytime at their location that cannot be moved once placed. The robots have no sight range and can only find something by bumping into it, but they can tell the difference between their own flag, the other robots flag, and the other robot. Each robot must be given the exact same deterministic program, the robots will land somewhere randomly on the planet and will them just follow their program. Find an algorithm that guarantees that the robots can find eachother.

The hardest part is dealing with the fact that both robots must be given the same program. You may assume for simplicity that the robots already have a simple program for searching out an area (were you able to keep one robot stationary while the other moves, this problem would be trivial, as it is easy to search the entire planet surface given its radius and the robots size) so you don't need to write out such an algorithm explicitly.

Logicians Are Crazy

Time for the solution to the pirates problem from last time. The comments section last time gave away the essentials of the solution, so odds are nobody is going to be surprised by anything in the answers here, but whatever.

I guess I'll solve the four problems in the order I gave them in. For notation, the pirates will be labeled in order of ages as 1,2,3,4, and 5, with 5 being the oldest. First:

The proposing pirate gets a vote, and ties result in the motion passing.

Alright, so if only pirates 1 and 2 are left, then pirate 2 can propose to take all the gold, and the motion will pass. Thus, if 1,2,3 are all left, pirate 3 can offer just 1 gold to pirate 1 and pirate 1 will accept. So then, for 1,2,3,4, pirate 4 can offer 1 gold to pirate 2 and it will pass. Finally, with 1,2,3,4,5 all there, pirate five simply offers 1 gold to pirates 3 and 1.

Pirate 5 gets 98 gold, pirate 3 and pirate 5 both get 1, motion passing 3-2.

Inductioning this up is fairly easy, and will stop when the proposing pirate runs out of gold (Inductioning is a word, right?). Moving on to the next case:

The proposing pirate does not get a vote, and ties result in the motion passing.

Now, if there are only 2 pirates left, pirate 2 is dead no matter what he proposes (as pirate 1 would rather kill him and take all the money than just take all the money. Thus, pirate 2 will accept anything pirate 3 proposes, so pirate 3 will take all the gold himself if 3 pirates are left. With 4 pirates left, pirate 4 can propose 1 gold to pirates 1 and 2 to get their support. In the 5 pirate case, pirate 5 will have to offer 1 gold to pirate 3 to get his support, and will have to offer 2 gold to either pirate 1 or 2, it does not matter which.

Pirate 5 gets 97 gold, pirate 3 gets 1 gold and one of pirates 1 or 2 get 2 gold, the other getting zero, motion passing 2-2.

This is a bit harder to induction up, since at 6 pirates, pirates 1 and 2 do not know who pirate 5 will choose if he gets the chance. Next:

The proposing pirate gets a vote, and ties result in the motion failing.

This problem actually comes out exactly the same as the last one, as if there are 2N pirates left in this case, then N votes of support besides the proposing pirate are needed to pass, just like in the last one (as only 2N-1 votes are actually cast in the last one). If there are 2N+1 pirates left, then N votes of support are needed outside of the proposing pirate, just like the last one.

Pirate 5 gets 97 gold, pirate 3 gets 1 gold and one of pirates 1 or 2 get 2 gold, the other getting zero, motion passing 3-2.

Again, hard to induction up (induction is a verb, right?).
Final case:

The proposing pirate does not get a vote, and ties result in the motion failing.

This one is a bit different, now if there are 2 pirates left, pirate 2 is just dead as before. If 3 pirates are left, pirate 3 is just dead though, as pirate 1 will vote down anything still. So with 4 pirates left, pirates 2 and 3 will support anything, as they are dead otherwise. Finally, with 5 pirates, pirate 5 will offer 1 gold to pirates 1, 2, and 3 to get their support.

Pirate 5 gets 97 gold, pirate 1, 2, and 3 each get 1, motion passing 3-1.

This will induction up to 6 pirates, but no further because at 6 the pirate must choose if he offers 2 gold to two of {1,2,3}, but he does not care which ones.

In conclusion, the oldest pirate wins, alot. Also, logicians are crazy.

Puzzling Pirates

Hmm...been some time since I posted. Time for a new puzzle, I first found this one somewhere on the internets:

5 pirates have to divide up a 100 gold treasure they have found. The dividing will be done as follows: the oldest pirate will propose a division of the money among the pirates, and then the pirates vote on whether they accept the proposal or not. If the proposal passes, they divide up the money as the proposal suggested. If the proposal fails, the oldest pirate is killed and the next oldest one gets to make a proposal. This will continue until either a proposal is accepted or only one pirate is left (who takes all the treasure).
The 100 gold pieces cannot be divided in increments any smaller than 1 gold (a proposal cannot have a pirate getting 2.5 gold, for example). The pirates are perfect logicians, and all facts in this puzzle are considered common knowledge. The pirates priorities are: 1. live, 2. get as much money as possible, 3. kill as many other pirates as possible. The pirates ages are ordered, no two of them were born on the same day.
When the pirates all behave as perfect logicians, what is the final division of money among the pirates?

The more pedantic of you will realize that this puzzle is not yet well defined, I have not said how ties are resolved, nor have I been clear on if the proposing pirate gets a vote. I am unclear on both of these on purpose, this is actually 4 puzzles in 1.

1. The proposing pirate gets a vote, and ties result in the motion passing,
2. The proposing pirate does not get a vote, and ties result in the motion passing,
3. The proposing pirate gets a vote, and ties result in the motion failing,
4. The proposing pirate does not get a vote, and ties result in the motion failing.

If my memory is correct, each of these has a different solution, but I can't recall it perfectly. At any rate, they are sort of neat to work out and see the differences in them.

Patient Prisoners

So, continuing my earlier ideas about the solution to the prisoners problem, lets see how long we expect the strategies to take. First, as a warm up, lets figure out in the case that the prisoners know the initial position of the light switches. Before I can do that though, I need to prove a very useful lemma that will be used constantly in the discussion of the solution.

Consider a coin that lands on heads with probability p ∈ [0,1]. How many times on average do you have to flip the coin before it lands on heads?

Naively, one expects the answer to be 1/p (if the coin has 1/3 chance of landing on heads, you expect to need to flip it 3 times). Of course, there is a small chance that you will need 4 flips, or 5 flips, or a billion flips. There is some sort of concern that the infinite sum will ruin things, so lets actually perform the infinite sum. The chance of stopping on exactly the Nth flip is p(1-p)^N-1, as (1-p)^N-1 is the chance you failed the first N-1 flips, and p is the chance you stopped on the Nth one. Summing to find the expectation value of N, and we will denote 1-p=q and D as derivative with respect to q, so we have

< N > = Σ Np(1-p)^N-1 = p Σ Nq^N-1
= p Σ D(q^N) = p D Σ q^N = p D(1/(1-q)) = p(1/(1-q)²)
= 1/p

So, we see that the naive expectation is actually correct, still, it is nice to prove it.

Now, moving on with our actual problem, for our strategy to work, we first must have one of the 99 non master prisoners to come in, then we need the master to come in, then one of the 98 remaining, then the master again, and so on down the line. the chance of each of these events is easy to figure out (remember, we are assuming that the warden selects a random prisoner each day). So, for the first few terms, the number of days it takes is 100/99+100+100/98+100+100/97+... since each time the master needs to enter the room, it takes about 100 days for that to happen. The full sum is

100*99+100* Σ 1/N

Where N is summed from 1 to 99. Approximating, that comes out to 9900+100Ln99 ≈ 10359, which is a little over 28 years. It would be nice to see if there is a solution with a smaller expectation number of days, especially since the average number of days it takes for every prisoner to enter the room once is 100Ln100 ≈ 460.

Now, for the real problem we have a bit more of a trick on our hands. For the solution when the prisoners do not know the initial position of the switches, they must have the master enter the room 198 times to count everybody. This means we have a flat out 19800 days on top of how long it takes the non masters to do their stuff. Each prisoner must enter the room twice and then gets ignored. This is equivalent to the following problem:

Consider a bag filled with N white balls. At each step, you select a ball from the bag. If the ball is white, paint it green and return it to the bag. If the ball is green, paint it black and return it to the bag. If the ball is black, return it to the bag. On average, how many steps will it take for the bag to have only black balls left in it?

If we let F(N) denote the solution to that problem, then our prisoners expect to get out in 19800+F(99) days. This problem is actually difficult to solve, and I doubt it has a nice solution, I will share my thoughts on it here to see what we can get.

First, let f(w,g,b) denote how many steps on average it takes to get from a position with w white balls, g green balls, and b black balls to the final position of w+g+b black balls. Now, suppose that half the bag has black balls in it, that means that it is the same as a position with no black balls in it but every step takes twice as long. In mathspeak, I claim that f(w,g,w+g)=2f(w,g,0), similarly, if 2/3 of the balls are black each step will take 3 times as long, and this can be extended into the claim that f(w,g,b)=(w+g+b)/(w+g) f(w,g,0). Its a bit of a trick to prove it, but I assure you that it is true. Now, we know that from the position represented as (w,g,b), we can take three possible paths, giving us the result that

f(w,g,b)=w/(w+g+b) [f(w-1,g+1,b)+1]
+g/(w+g+b) [f(w,g-1,b+1)+1]+b/(w+g+b) [f(w,g,b)+1]

The three terms represent the chance of drawing a white, green, and black ball, respectively. Now, let us denote f(w,g,0) as H(w,g), then by the earlier claim we have f(w,g,b)=(w+g+b)/(w+g)H(w,g), and so, setting b=0 in the previous equation, we find for H, the relation

H(w,g)=w/(w+g) [H(w-1,g+1)+1]+g/(w+g) [f(w,g-1,1)+1]
H(w,g)=w/(w+g)H(w-1,g+1)+g/(w+g-1)H(w,g-1)+1

Alright, now just to find the H that satisfies that recursion relation with the initial condition H(0,0)=0. First, we can try to find H(0,g). It must satisfy

H(0,g)=g/(g-1)H(0,g-1)+1

This turns out to be solved by our previous solution of H(0,g)=g Σ 1/i summing i from 1 to g. One can try a similar trick for H(1,g), but the solution gets ugly fast.

This is as much progress as I have made on the solution, I still doubt it has a clean solution at all, but if anybody can get a solution feel free to post it in the comments.

Not Really A Dilemma

So, I always hate it when people misuse the word dilemma, I mean seriously now, its supposed to be a problem involving two choices. If you don't have exactly two choices its not a dilemma. Naturally, that didn't stop me from breaking this rule when I posted the problem last week and titled it prisoners dilemma. Whatever, anyway, lets have a look at the solution now.

First of all, its important to realize the two switches and the manditory flipping thing is a big ol' red herring. You can just use the switch on the right as a "dummy switch" and the switch on the left as your real switch. You flip the right switch if you are in the room and do not feel like flipping the left switch. So now there is just one switch in the room and flipping it is optional.

Next, the problem is alot easier if we assume that the prisoners know the initial position of the switch. So, let us assume that the switch starts in the up position. The solution is begins by having one person designated to be the "master" who will count off the prisoners by being the only person to flip the switch to up. The strategy for every prisoner who is not the master is:

If the switch is down, do nothing.
If the switch is up, then flip it down if you have never flipped it down before. If you have flipped it down before, do nothing.

The strategy for the master is:

If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 99 times, declare that all 100 prisoners have been in the room.

So flipping the switch up declares a prisoner to be 'counted', and each prisoner will be counted exactly once. Its interesting to ask how long it takes for this strategy to work assuming the warden picks prisoners at random, I'll get to that next week.

This strategy might even work if you don't know the initial position of the switch (because it might start as up anyway), but if it started as down then the master will count a prisoner that wasn't actually there and the warden (being an adversary) will arrange things so that you lose.

You could try to solve that by having the master count to 100, but then if it had started as up you will never manage to end the strategy, as nobody will ever make the last flip (and you will never be sure it isn't just the warden holding out on you).

So, with an unknown initial switch position it is a bit harder. You can deal with this by counting everybody off twice. Agian, designate a master, the strategy for any prisoner who is not the master is:

If the switch is down, do nothing.
If the switch is up, then flip it down if the number of times you have flipped it down before is one or zero. If you have flipped it down twice before, do nothing.

So now each prisoner will ask to be counted exactly twice. The strategy for the master is:

If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 198 times, declare that all 100 prisoners have been in the room.

Counting to 198 is counting every one of the "non-master" prisoners twice. Now, if the switch started as down, then you counted that once, but that does not matter. All that would mean is that there is a prisoner out there that you only counted once, which is good enough anyway.

Calculating how long this strategy takes is much harder, and I am still working on the solution to that.