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.