More Hats

Alright, so for a blog entitled "Standard Hat Rules Apply", the standard hat rules sure haven't applied very much here, so it's time to remedy that. Here is a problem I first learned on the forums over at xkcd.
Consider a room of seven people around a table. They will each be assigned hats from seven different colours (ROYGBIV colours for definiteness, if you like). Hat colours may repeat, it is possible everybody will be given a blue hat or something. Standard hat rules will apply.

They must each simultaneously guess what their own hat colour is. If anybody is correct, everybody wins and are all given kittens. If everybody is incorrect they all lose and no kittens will be awarded, also the players will be killed. They may strategise before the hats are assigned. What is a strategy that guarantees victory (and thus kittens)?

Solution next time.

Ball Solutions

So, last time I introduced a ball problem, and I guess its time to show the solution. The solution is actually really simple, but I feel like doing a full-blown derivation.

First, let us define f(n,m) to be the solution to our problem, specifically it is how many black balls will be left if we started with n white and m black balls. We know f on the boundary cases:
1. f(0,m)=m
2. f(n,0)=0
To get the rest, consider that from a given position with n white balls and m black balls, we have a m/(n+m) chance to remove a black ball, and a n/(n+m) chance to remove a white ball. This means that:
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)
From here we can start to figure stuff out.

First, let us find f(1,m)
f(1,m)=m/(m+1)*f(1,m-1)+1/(m+1)*m
f(1,m)=m(m+1)*(f(1,m-1)+1)
From here, you can find f(1,1)=1/2, f(1,2)=1, f(1,3)=3/2 and guess f(1,m)=m/2. Alright, great, then a similar process on f(2,m) gives you that it is m/3, and this leads one to the general guess of f(n,m)=m/(n+1). Since it is already known to be true for the boundary cases, it suffices to show that when this formula holds for f(n-1,m) and f(n,m-1) it then holds for f(n,m). Something of a double induction:
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)
f(n,m)=m/(n+m)*(m-1)/(n+1)+n/(n+m)*m/n
f(n,m)=m/(n+m)*((m-1)/(n+1)+1)
f(n,m)=m/(n+m)*(m-1+n+1)/(n+1)=m/(n+1)
Yep, it works.

Actually, after the fact, you can intuit the answer in the limit of large m (does it still count as intuiting it after the fact?). If m is large, you can picture many black balls in a line, with a few white balls in the mix. If they are sorted randomly, and then taken from one end how many black balls will be after the last white ball? The white balls will evenly divide up the black balls into n+1 groups, and so at the end there will be m/(n+1) black balls.

Ball Problems

Man, I sure expected to post more often than once a week when I started this stupid thing. Eh, whatever, who reads this anyway? Anyway, time to introduce a new problem. I originally learned this problem somewhere randomly on the intertubes.
Consider you have a bag with n white balls and m black balls in it. You randomly pull balls out of the bag, one at a time, until you have drawn all the white balls. On average, how many black balls will be left when you stop?

Yeah, OK, thats all I got. Solution to follow later.

Some Days You Can't Lose

So, last week (man, I planned to write more often than this, but blogging is so hard) I wrote about the card flipping problem, and I guess its time to discuss the solution. First though, its probably best to discuss a common "solution" that does not work (well, actually it works, as we shall see, but its not the solution to the problem).

Attempted solution is as follows:
As soon as you have seen more black cards go by than red cards, say stop.

This looks like a good solution, as anytime you say stop you will have a greater than 1/2 chance to win. What exactly is the overall chance to win though? In the case of a 52 card deck, that is very hard to find, so lets try for a 4 card deck.

There are two separate cases where this strategy will say stop.

1. If the first card is black (1/2 chance), you say stop and win 2/3 of the time.

2. If the first card is red (1/2 chance), then you will only say stop if the next two cards are black (1/3 chance), but then you are guaranteed to win.

So far, you win (1/2*2/3+1/2*1/3)=1/2 of the times that you say stop.

OK, what about when you do not say stop? If you reach the end of the deck and have not seen more black cards than red, then you are in trouble, the last card of the deck is guaranteed to be black.

This summarizes the problem that you meet in the 52 card deck. Many games you will say stop at some point and you have a slightly better than 1/2 chance to win, but there will be the occasional game where you do not say stop and you are certain to lose. In the end you come out 50% no matter what.

OK, could you do better? No, as it turns out. The argument can be made with a few simple points:

1. When you say stop, it wouldn't matter if I were to shuffle the deck before that last flip.
2. When you say stop, if instead I just picked a face-down card in the deck from my choosing, it wouldn't change anything
3. When you say stop, I could just deal the next card from the bottom of the deck.


(This argument can be put more succinctly, but I find this method more convincing). So now we have a different game. I will deal cards off the deck until you tell me to stop. When you do so I will show the bottom card of the deck, if it is red you win, if it is black you lose. What is the optimal strategy for this game?

Its pretty easy to see this game is 50-50 no matter what you do. Even if you were trying to lose you couldn't do more than 1/2 the time (of course, in this game trying to win is equivalent to trying to lose the other way). Naturally, at any given moment when you tell me to stop, you might be better or worse than 1/2 (in particular, if you wait until the last card, then you are either 0 or 1), but for anything you try to do, you were 50-50 from the first card.

This realization that sometimes the order doesn't matter for random events can be very useful, and I will probably refer back to it from time to time (though, I can honestly only think of one major instance that I have used it in logic problems).

I have also used this idea in boardgames. In 1960: The Making of the President, there is a point in the game where you draw 3 cubes from a bag to determine the outcome of events. If at least 2 of the cubes come up your colour, then you win the event, but if at least 2 of them come up the opponents colour, then you lose it, either way, the cubes do not get returned to the bag. Not all the events are equal, and you can choose what order they happen in.

Some would argue something about wanting to do the less important event first, so if the opponents cubes come out, you have more of your cubes in the bag for the better event, and I'm sure one could also make some argument for doing the more important event first as well. However, its not hard to show that there is no optimal strategy here. Naturally, if you do the weaker event first and a bunch of your own cubes come out, you will be upset, but a priori all strategies had been the same.

Card Flipping

Alright, just to post because I haven't done so in a few days, I'll introduce a new problem. I first learned this problem (as with so many of my puzzles) from Bart:
I hold a deck of 52 cards, 26 of them are red, and the other 26 are black. I will flip cards face up off the deck one at a time until you tell me to stop. When you stop me, I will then flip one more card, if that card is black you lose the game, if it is red you win the game. You are required to stop me before I flip the last card of the deck. What is the optimal strategy to win this game?

As is my standard method, I'll post the solution next time.