Open Thread for February 11 - 17

Scott Garrabrant

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

I wrote a logic puzzle, which you may have seen on my blog. It has gotten a lot of praise, and I think it is a really interesting puzzle.

Imagine the following two player game. Alice secretly fills 3 rooms with apples. She has an infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples. She must put a different number of apples in each room. Bob will then open the doors to the rooms in any order he chooses. After opening each door and counting the apples, but before he opens the next door, Bob must accept or reject that room. Bob must accept exactly two rooms and reject exactly one room. Bob loves apples, but hates regret. Bob wins the game if the total number of apples in the two rooms he accepts is a large as possible. Equivalently, Bob wins if the single room he rejects has the fewest apples. Alice wins if Bob loses.

Which of the two players has the advantage in this game?

This puzzle is a lot more interesting than it looks at first, and the solution can be seen here.

I would also like to see some of your favorite logic puzzles. If you you have any puzzles that you really like, please comment and share.

It is interesting to contemplate that the almost fair solution favors bob:

Bob counts the numbers of apples in 1st room and accepts it unless it has zero apples in it, in which case he rejects it.
If he hasn't rejected room 1 he counts the apples in 2 and if it is more than in 1 he accepts it else he rejects it.

For all possible numbers of apples in rooms EXCEPT one room has zero apples, Bob has 50% chance of getting it right. But for all possible number of apples in rooms where one room has zero apples in it, Bob has 5/6 chance of winning and only 1/6 cha... (read more)

2Scott Garrabrant12y

Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive. For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over. This algorithm uses on average 10240/1001=10.228770... rolls. What is the fewest expected number of die rolls needed to complete this task? When you know the right answer, you will probably be able to prove it. Solution

3solipsist12y

A long one-lane, no passing highway has N cars. Each driver prefers to drive at a different speed. They will each drive at that preferred speed if they can, and will tailgate if they can't. The highway ends up with clumps of tailgaters lead by slow drivers. What is the expected number of clumps?