Morris: Living with Crazy Buttocks
Janine is one of twenty guests at a Christmas party. Each guest is given a book as a present. Janines’s book is called ‘Living with Crazy Buttocks’. She isn’t sure what to make of that.
The guests are invited to play a game. Each book is put into an identical cardboard box. The boxes can be opened and closed without leaving a mark. The twenty boxes are piled up around the Christmas Tree.
The guests are told that they will each have the opportunity to open half of the boxes. Their objective is to find their own book. If they all succeed the group wins and they will win a trip to Paris. If any one of them fails then the group fails but they will each get a Twinkie to keep for life.
The guests are taken to another room and then taken to the tree one at a time. They cannot see what any other guest does at the tree. They are not able to communicate once the game starts. The boxes are put back after each guest, as though they had never been there.
You would think that the chance of the group succeeding was 1/2^20 but they can do much better than that.
The group must come up with a strategy before the game starts. What is the best strategy to get the group to Paris, and let Janine keep her ‘Crazy Buttocks’?
These books are all real. They will be helpful to you if you have had any of the following thoughts:
We all know the Nazis killed millions of innocent people but what were they like on ecological issues?
I would like to speak Italian but can’t be bothered to learn any Italian words, can you help?
Aubergines are very flushed, just how angry are they?
I think I’m dead, how can I tell for certain?
I am rich but dead. How should I pimp my coffin?
I am worried about running into large, slow moving objects; can you suggest any strategies to avoid this?
Just how boring was 1587?
I live thousands of miles from Versailles. Will I get a good view?
I am English, am I human?
My buttocks are insane.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Andrew said,
October 27, 2009 at 1:19 pm
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]
Blaine said,
October 28, 2009 at 5:15 pm
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…
laciermaths said,
October 29, 2009 at 8:16 am
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]
Stephen Morris said,
October 30, 2009 at 1:59 pm
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.
Stephen Morris said,
October 30, 2009 at 2:01 pm
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]
jyoak said,
November 6, 2009 at 8:28 pm
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
Stephen Morris said,
November 14, 2009 at 3:36 pm
Some great answers. I’ve posted solution and the formula for calculating the chance of success here.