Infinite Hats

Time for a new puzzle. I found this one on Tanya Khovanova’s Math Blog, as so many of my puzzles are:

There is a room with 100 logicians, and each of them have an infinite number of hats in a tower upon their head. Each hat can be either white or black, and the sequence of hats upon a given logicians head is random. Standard hat rules apply of course.

At a specified time, each logician must simultaneously write down a number. For each logician, the hat of the number they wrote down is checked (so if Bob wrote down 13, we look at the 13^th hat on his head), and if that hat is white, that logician is "correct". If all the logicians are correct, they win, if any of them are incorrect they will play the game again tomorrow with new random hats.

Before the game, they may strategize. The naive strategy gives you a 1/2¹⁰⁰ chance to win, so it will take about 2¹⁰⁰ days to be released, but they do not want to wait that long. Find a strategy that will probably get them out within the year.

Because the hats are random you may use a strategy that only will specify a number with probability one. For example, Bob could look at Alice's hats and look for "the first occurrence of 578 consecutive black hats", which will appear somewhere on her head with probability one.

Unfair Auction

Time for the solution to that stupid auction game puzzle from last time.

As with so many puzzles like this, it basically comes down to solving the simpler cases first and moving up. Actually, we will generalize the puzzle a bit, and assume Alice is starting with $N.

Alright, in the "one coin means winning the game" case, it is obvious Bob simply must open the bidding with $N. A bid of any less hands Alice the win, and a bid of any more is unnecessary, so we can see that Bob must start with $N also. We can actually say something a bit stronger, if we are in a position where Alice needs one more coin to win and Bob needs one more coin to win, then Bob wins iff he has at least as much money as Alice has left.

Next the two coin game. There are four positions to consider here, we will first introduce some variables to help the notation. Let A be the number of coins Alice needs in order to win, and let B be the number of coins Bob needs in order to win. Then the positions can be represented as (A,B) being any of (1,1), (1,2), (2,1), (2,2). Obviously if we are in (1,1) then Bob needs the same amount of money as Alice, and if we are in the position (1,2) then Bob needs twice as much money as Alice, as he must bid enough so she can't outbid him, twice. In the position (2,1), Alice will lose if she lets Bob get a coin, so when Bob bids x, Alice must pay x+1, and then Bob must have as much money as Alice left over so he can win. Thus Bobs money-x=Alices money-(x+1), so Bob can have 1 less dollar than Alice in this position, and then he can bid anything he wants and win. Finally, the position (2,2), Bob will have F dollars and Alice will have N dollars. Bob will bid z dollars on the first coin. If he wins, he will have F-z vs N, and we know that he can then win the game if F-z=N-1. If Alice outbids him for z+1, Bob will have F-z dollars and Alice will have N-(z+1), and we know that Bob can win the game if F-z=2(N-(z+1)).

Combining those equations we get F=3/2(N-1), which tells you the amount of money Bob needs to start with.

Alright, we can just keep that pattern going. Define F(A,B,N) as the amount of money Bob needs to win from the position where Alice needs A more coins, Bob needs B more coins, and Alice has N dollars left. Clearly F(1,B,N)=B*N, as Bob must bid N every round, and F(A,1,N)=N-(A-1) as Alice can outbid Bob each of A-1 times losing one dollar on him each time, and then be unable to outbid him the last time. Finally, from some position (A,B,N), Bob has F(A,B,N) dollars, Bob will bid x, and Alice can either let him have it, moving to (A,B-1,N) with Bob having F(A,B,N)-x, or Alice can outbid him, moving to (A-1,B,N-(x+1)), with Bob having F(A,B,N)-x. This means that F(A,B-1,N)=F(A-1,B,N-(x+1))=F(A,B,N)-x.

Looking back at the strategy in the two coin game, Bob needed $3z while Alice had $2z+1 when Bob bid z on the first round. Actually he can bid z on all three rounds and Alice does not have enough money to outbid him twice, so he trivially wins (we also showed it was a minimal win). If one expects this strategy to continue upwards, Bob simply identifies a z such that Alice cannot pay Az+A, so she cannot outbid him A times (Az=N-A+1 will work) and then Bob will need (A+B-1)z dollars to win (so he can pay $z each of the (A+B-1) times a coin is won). Thus, we expect that F(A,B,N)=(N-A+1)(A+B-1)/A is the solution. One can confirm is satisfies our earlier relations, with x=z that we have found.

Actually this has alot of discretization error in it, since Bob cannot bid non-integer values. By our solution we expect that in the case of A=B, the amount of money Bob needs is z(2A-1), with z=(N-A+1)/A, so if N=100 and A=3, say, then z=32+1/3 and Bob needs 161+2/3. If Bob is given $162, it is not enough, he can make bids of $33, $33, $32, $32, $32, and Alice can outbid the three times he bids $32. She could even outbid two $32's and one $33, she cannot outbid two $33's and one $32 though, so Bob needs 32+33+33+33+33 dollars, so Bob needs $164 to win.

Its a bit sad the solution is so boring, Bob has some freedom in how he bids, but the strategy of just "pick a number large enough that Alice cannot afford to outbid it enough times" is basically optimal. Asymptotically, in the case A=B, with N>>A>>1, the solution is that Bob needs 2N dollars and bids N/A each round, Alice being unable to outbid him A times.

Auctioning Coins

Time for a new puzzle. I thought I learned this one on the forums at xkcd, but I was incorrect, what actually happened was that I misread a puzzle that somebody had posted and created my own inadvertent variant. Anyway, here it is:

Bob and Alice are playing an auction game. In a round of the auction a single coin is going to be put up for auction and Bob makes a bid on that coin. Alice can then either outbid him or pass. If Alice outbids Bob, she wins the bid, Bob does not get to bid again (the auction is once-around). Additionally, it is an all-pay auction, any bid you make you must pay, even if you lose the bid. The first person to acquire three coins wins the game.

It is clear that Alice has a large advantage in this game, so Bob gets to start with extra money. Given that Alice starts with $100, what is the minimum amount of money that Bob needs to start with so that he has a winning strategy?

To be clear, only nonnegative integer bids are allowed, no fractions. In a given round, Bob bids $k (and immediately pays it) and Alice gets the choice of either paying $(k+1) for the coin or letting Bob have it. Bob is allowed to bid zero (and will be forced to if he runs out of money), and Alice may then take the coin for $1 (which she will probably do unless she is out of money).

On the forums, the actual puzzle had an infinite number of rounds of bidding, and a player won as soon as they had a three coin lead. That puzzle had a much more complicated answer, but if I am honest the answer to this one is actually sort of boring once you get it, I just found it fun to solve out.

Pigeonhole'd

Solution o'clock! Hopefully you have all solved out the balls in boxes problem from last time. Given that you probably have, writing a solution is a totally pointless act, done simply to amuse myself. Here we go.

First of all, lets find some N for which we cannot always win. Specifically, consider that N=1 and there are 1000 balls. Box 999 might have 500 of them and box 1000 has the other 500 of them. In this case we have no legal moves and cannot win. What is the largest N can be so that we still might have no legal moves? To put it another way, when is N big enough to guarantee that we always have a legal move?

The most balls we can have with no legal move is 1 ball in box 2, 2 balls in box 3, 3 balls in box 4,..... k-1 balls in box k. If we have any more balls than that it will be guaranteed that we always have at least one legal move. That number of balls is 1+2+3+4+..+999 = 999*1000/2. So if N is larger than 999/2, so 500 or more, then we always have a legal move. If N is less than 500 we might have no legal moves, thus we may have started in a position with no legal moves.

Now, if N is 500 or larger, we know we always have a legal move, is this enough to guarantee that we can eventually wander our way to a solution? First note that if all the balls were in box 1, we would basically be done, we can move balls from box 1 to any target box simply by moving them 1 at a time. In fact, if we want to move balls from box i to box j, it costs us nothing to move from box i to box 1 then from box 1 to box j, so we might as well only consider moves to and from box 1.

So, assume N is 500 or larger, we have some boxes that have enough balls in them such that we can perform a move. Make all the moves you can from those boxes to box 1, such that when we are done the only legal moves we have left are from box 1. When we are done this box 1 must be nonempty, for if box 1 was empty we would have no moves, and that is impossible for N at least 500. Now, either all the balls are in box 1 or they are not, if all the balls are in box 1 we are done, we can solve the problem as mentioned earlier. If not all the balls are in box 1, there exists some k and x where box k has x balls in it, with k>1, k>x, and x>0. One can see that box 1 has at least k-x balls in it, this is apparent because if it did not I could move all the balls from box 1 into box k and leave myself with no legal moves (which is impossible). So, we can move k-x balls from box 1 into box k, bringing box k up to k balls, and we may then move all the balls from box k to box 1. We repeat this process for each nonempty box k with k>1. In the end all the balls are in box 1 and the game is trivially won.

I'm not sure why I liked this problem so much, I guess I was just pleasantly surprised to see something so simple on a Putnam. I cannot say that their questions lack creativity, but this particular problem is just the kind of creativity I like.

Balls In Boxes

New puzzle o'clock! I should probably be working instead of blogging, but blogging is so much more fun. Anyway, I found something of a neat puzzle on the Putnam 2010 exam. Usually those exams are just filled with semi-impossible math problems involving stupid functions, but there was one question on that exam I thought was pretty cool as a puzzle:

There are 1000 boxes, labelled 1 through 1000. There are 1000*N balls in the boxes, distributed randomly between the boxes. You will be playing a 1 player game, trying to average out the balls in the boxes, so that each box has exactly N balls in it.

The only legal move in the game is to select a number K and move exactly K balls from box K into any other box. So you could go to box 247 and move exactly 247 balls from that box into any other box. If box 247 has fewer than 247 balls in it, you cannot do this, so you don't get to move any of them. You are allowed to keep making legal moves as long as you like, and you win if every box has exactly N balls in it.

Given that in total there are 1000*N balls in the 1000 boxes, for what values of N is it always possible to win, regardless of the initial configuration of the balls?

Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.