You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

solipsist comments on Open Thread for February 11 - 17 - Less Wrong Discussion

3 Post author: Coscott 11 February 2014 06:08PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (325)

You are viewing a single comment's thread. Show more comments above.

Comment author: Coscott 11 February 2014 09:26:29PM 8 points [-]

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.

Comment author: solipsist 11 February 2014 09:51:36PM 1 point [-]

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?

Comment author: Coscott 11 February 2014 10:07:43PM 2 points [-]
Comment author: mwengler 11 February 2014 11:31:00PM 0 points [-]

Coscott's solution seems incorrect for N=3. label 3 cars 1 is fastest, 2 is 2nd fastest 3 is slowest. There are 6 possible orderings for the cars on the road. These are shown with the cars appropriately clumped and the number of clumps associated with each ordering:

1 2 3 .. 3 clumps

1 32 .. 2 clumps

21 3 .. 2 clumps

2 31 .. 2 clumps

312 .. 1 clump

321 .. 1 clump

Find the mean number of clumps and it is 11/6 mean number of clumps. Coscott's solution gives 10/6.

Fix?

Comment author: Coscott 11 February 2014 11:58:07PM 1 point [-]

My solution gives 11/6

Comment author: mwengler 12 February 2014 12:04:49AM 1 point [-]

Dang you are right.

Comment author: mwengler 11 February 2014 11:45:36PM 0 points [-]

Coscott's solution also wrong for N=4, actual solution is a mean of 2, Coscott's gives 25/12.

Comment author: Coscott 12 February 2014 12:02:22AM 1 point [-]

4 with prob 1/24, 3 with prob 6/24, 2 with prob 11/24, 1 with prob 6/24

Mean of 25/12

How did you get 2?

Comment author: mwengler 12 February 2014 12:45:04AM 0 points [-]

Must have counted wrong. Counted again and you are right.

Great problems though. I cannot figure out how to conclude it is the solution you got. Do you do it by induction? I think I could probably get the answer by induction, but haven't bothered trying.

Comment author: Coscott 12 February 2014 01:36:53AM 3 points [-]

Take the kth car. It is at the start of a cluster if it is the slowest of the first k cars. The kth car is therefore at the start of a cluster with probability 1/k. The expected number of clusters is the sum over all cars of the probability that that car is in the front of a cluster.

Comment author: solipsist 11 February 2014 10:09:39PM 0 points [-]

You got it.

Comment author: Coscott 11 February 2014 10:12:39PM 0 points [-]

I am not sure what the distribution is.

Comment author: gjm 11 February 2014 10:50:31PM 2 points [-]
Comment author: Coscott 11 February 2014 11:02:34PM 1 point [-]

Ah, yes, thank you.