Comments on: Morris: Living with Crazy Buttocks

By: Stephen Morris

Stephen Morris — Sat, 14 Nov 2009 20:36:25 +0000

Some great answers. I've posted solution and the formula for calculating the chance of success here.

By: jyoak

jyoak — Sat, 07 Nov 2009 01:28:00 +0000

That puzzle is absolutely fantastic! I didn't recognize it and thus got the fun of tackling it, but once I came upon a solution I became convinced that I've seen this before, perhaps with different particulars. Is this a Martin Gardner puzzle or something? Has it ever been on the show?

I started trying to solve it like one of my hat puzzles -- trying to divide up the permutations such that when there is going to be any misses that there are tons of misses, but that correct guesses occur together. It is possible to make improvements over random this way. Consider 4 books / people, 2 guesses. (I assume throughout that we can find a way to make the boxes under the tree ordinal in some sense. "Closest to the southwest corner at the floor with ties broken by being southernmost" or some such. I assume that solving this isn't the puzzle you're aiming for and I treat it as though you can assume the boxes are numbered 1-20.) If you have people A and B both open boxes 1 and 2 and C and D always open 3 and 4, consider the cases:

1: A B C D

2: A B D C

3: A C B D

4: A C D B

5: A D B C

6: A D C B

7: B A C D

8: B A D C

9: B C A D

10: B C D A

11: B D A C

12: B D C A

13: C A B D

14: C A D B

15: C B A D

16: C B D A

17: C D A B

18: C D B A

19: D A B C

20: D A C B

21: D B A C

22: D B C A

23: D C A B

24: D C B A

With this strategy, you get 1, 2, 7, 8 or 1/6, which is considerably better than 1/2^4 you get for random. This kind of idea can be extended to larger numbers of boxes and perhaps improved upon, but it doesn't feel like a candidate for your favorite puzzle ever. I then had one of those pull-over-to-the-side-of-the-road epiphanies that you're throwing away a lot of information. Strategies of this form presume that you look into a box and see either your book or "not your book." You actually see some particular person's book and can alter behavior based on this event. That's a lot to throw away. How can we use this to cause good guesses to collide?

Consider person A assigned to open the first box. If he finds his own book, he's done. When he finds a book belonging to X, his concern is to open another box such that if if he finds his book and X happens to open that box first, that X will make a good decision. So if he finds B's book, and he opens box 2, he wants B, if starts at 2, to open box 1 next in the case that A's book is there and probably not otherwise. This same logic should apply to everyone. So generally, that means, that if you assign each person a different starting box, if they don't find their book, they should open the starting box corresponding to the person owning the book that was found. Assume A assigned 1, B to 2, C to 3, and D to 4.

In case 1, everyone finds their book straight off. A happy result.

In case 2, A finds his book. B finds his book. C finds the book of D, and so opens 4 and finds his book. 4 finds C, opens three and finds his book.

In case 3, A finds his book. B finds C, thus opens three and finds his book. C finds B, opens 2, and finds his book. D finds his book.

In case 4, A finds his book, B finds C, opens 3 and fails.

In case 5, A finds his book. B finds D, opens 4 and fails.

In case 6, A finds his book. B finds D, opens 4 and finds his book. C finds his book. D finds B, opens 2 and finds his book.

Already as many winning cases as my strategy above! It continues:

7: Hit

8: Hit

9: Fail

10: Fail

11: Fail

12: Fail

13: Fail

14: Fail

15: Hit

16: Fail

17: Hit

18: Fail

19: Fail

20: Fail

21: Fail

22: Hit

23: Fail

24: Hit

So we get to go to Paris a staggering 10/24 times. Since 12/24 or 1/2 seems to be a theoretical maximum, that's just astounding!

To extend this to the case of 20, After opening your second box, you continue on by opening the box of the person's book you find at each step. This is the point at which I started to think I'd seen this problem before. Since you're following a sort of chain here, you have a finite number of states and since your box is sure to be in the chain (you started with the box to which you're assigned) you know that if you could keep guessing and following this method that you'd find your book rather than being caught in a loop not containing your book.

The only question is whether the chain that your part of is short enough to get there in 10 hops. If you look back at the hits and misses from the case of 4, you see that you hit exactly when the state is one that could be obtained by sorting them so each person would find their book initially and the allowing the following operations:

Leaving a book alone (generates a chain of 1).

Exchange a book with another (generating a chain of 2). (This operation can't be repeating on any book already used in it, of course.)

In case of a fail, something else happened. Pick one at random, case 14: C A D B . With this , there is a chain of positions

1->3->4->2

and only then back to 1. A chain of 4. There should be chains of 3 in there as well. Looking... 4: A C D B . Position 1 is a chain of 1. The other chain is:

2->3->4

and then back to two.

This chaining idea is familiar to me, but I can't place where, and I'm pretty sure at least it wasn't books and boxes. But anyway... there you have it.

The next question I ask myself how often do you win with 20? All cases where no one lands in a chain of greater than length 10 (and so in all cases where no such chain exists) is an answer of sorts, but how often is that? I'm at a complete loss as to how to compute that. My guess is that it stays fairly close to one half, but gets worse as you add more people and boxes. (But it sure would be beautiful if it doesn't change at all, except by rounding error.) I could program it to come up with an estimate, but instead I think I'll stop and get some work done today. :-)

Steve, thanks for the puzzle. This was absolutely fantastic

By: Stephen Morris

Stephen Morris — Fri, 30 Oct 2009 19:01:43 +0000

Here is a clue, just in case you need one.

[spoiler]http://mathfactor.uark.edu/2008/10/follow-up-loops-and-the-harmonic-series/[/spoiler]

By: Stephen Morris

Stephen Morris — Fri, 30 Oct 2009 18:59:45 +0000

I've had a few questions about this puzzle. To clarify:

You cannot tell which book is in a box without opening it. The books are strapped down and weighted in some way.

The boxes, books and the room are identical when each guest enters. There is no way a guest can communicate with or leave clues for other guests once they enter the room. The puzzle is about the strategy they come up with before the game starts.

The guests have seen who gets each book and the arrangement of boxes before the game starts. They don't know which book is in which box.

By: laciermaths

laciermaths — Thu, 29 Oct 2009 13:16:08 +0000

Hint: If we reduce the problem to 2 people, the fact that a strategy helps becomes clear. Alice and Bob agree that Alice picks one box, and Bob picks the other. Then their odds of success are 1 in 2, instead of 1 in 4 without a strategy.

[spoiler]
If the boxes can be put in one-to-one correspondence with the guests, then we have a solution as follows — The arrangement of books within the boxes can be interpreted as a permutation of people; that is, it sends the person associated with the box to the person associated with the book inside. Then each person starts out by picking the box associated with himself. If that box does not contain the right box, then he next picks the box associated with the person whose book he found inside, and so on.

Since permutations can be discomposed into disjoint cycles*, iterating in this fashion eventually produces the right book if the person is allowed an arbitrary number of selections. But each person is only allowed 10 picks, so we are looking for the number of permutations with no cycle with length greater than 10.

Since there are only 20 elements being permuted, a given permutation has at most one cycle that is too long. Now we pick the elements in the bad cycle in (20 \choose k) ways and order them in (k-1)! ways**, and the other elements can behave arbitrarily amongst themselves in (20-k)! ways; and then sum from k = 11 … 20. This counts the bad permutations; we subtract the total from 20!. I’d finish the computation here, but there’s too little space in the margin.

I’m not sure this is the solution you’re looking for, because we’re still missing a way to assign a box to each person. It is, however, advantageous that the positions of the boxes is faithfully reset after each person, so provided that the guests can agree on a consistent way to list the boxes by position (e.g. in increasing order of distance from the entrance to the room; or in concentric circles starting with the largest and progressing clockwise through each circle), they can just put this list next to a consistent list of the guests (e.g. in alphabetical order). It’d help if the guests were allowed to see the arrangement of boxes while formulating their strategy.

In conclusion, this isn’t how I normally talk, I’ve just been doing far too many math psets lately.

Footnotes in second spoiler, for very slightly more rigor.
[/spoiler]
[spoiler]
* A quick proof: By iterating from a starting point you must go somewhere, and there are only finitely many places to go. Thus it is clear that any starting point puts you in a cycle, and you can eliminate weirdness by observing that permutations are invertible and cycles never cross.

** We can also get this number by picking distinct elements until we have “enough” and then forcing a loop. That is, pick the first in 20 ways, the second in 19 ways, …, the kth in 20-k+1 ways. This produces a k-cycle, but we could have started at any point in the cycle, so we’ve overcounted by a factor of k. Thus (20)(19)…(20-k+1)/k = (20!/(20-k)!)/k = (20 \choose k) * (k-1)!. (The counting I originally gave is produced by picking a k-subset, then fixing the lowest element in place before iterating.)
[/spoiler]

By: Blaine

Blaine — Wed, 28 Oct 2009 22:15:18 +0000

So far I’m stumped… is there any implicit ordering of the books? Could the group decide that they were going to number them from 1 to 20 going clockwise around the tree from a predetermined point?

Also, does everyone have to go and look at 10 books at a time? Or could they look at just one book and then decide to go back on a later round?

Tricky, tricky, tricky…

By: Andrew

Andrew — Tue, 27 Oct 2009 18:19:03 +0000

This strategy is about 5.7 times better than random, but I don’t know whether it’s optimal:
[spoiler]Split the people and the boxes into two groups of 10. Have the first group of people open the first group of boxes, and the second group of people open the second group of boxes. For each splitting of the people, there is one out of a possible 20C10 splittings of the boxes that will work, for a probability of success of 1/184,756.[/spoiler]