blinkdagger

And the winner is . . . Joshua Zucker!

28 Mar 2008 Quan Quach 9 comments 480 views

Let's number the leprechauns in order by age: #1000 for the youngest,
#1 for the oldest.

If only #1 is left, #1 gets all the gold.

If there are two left, clearly #2 will vote to split the gold rather
than go home, so they each get 50% of the total.

If there are three left, then #1 and 2 will gang up on #3, so #3 goes
home and #1 and #2 split the gold.

If there are four left, #3 can see that it's dangerous to let #4 go,
so #3 and 4 together will vote to split the gold immediately.

If there are 5, 6, or 7 left, then #1,2,3,4 can see that if it gets
down to four, they'd each get 1/4 of the gold, so they will gang up
against #5,6,7 ...

So then when there are eight left, #5,6,7,8 will all work together and
vote for the split.

Similarly, by induction, when there are 2^n + k left, k < 2^n, the 2^n
can see that they'll get 1/2^n of the total, so they'll vote as a
block.

Thus, when there are 512 Leprechauns left, #257 through 512 will vote
to split the gold, and with half the vote they will carry the day, and
so Leprechauns #1-512 each get 1/512th of the gold.

9 Responses to “And the winner is . . . Joshua Zucker!”

1. on 28 Mar 2008 at 7:09 am 1Joshua Zucker

   Thanks! I’m happy to be in the lucky winner in the company of such a set of distinguished solvers.

   I think several of the URLs are broken here — mine in the main body shows up funny-looking, and the last three links also seem to be missing the http:// in front.

   In response to your questions:
   1. Was the problem too easy? Too hard?

   It was fairly easy, but fun, because it was an interesting variation on a problem I’d seen before. (There was the one, a few years back in Scientific American, Dennis Shasha’s column I think? where the pirates/Leprechauns have the youngest propose a way of dividing the gold (integer numbers of coins) and then need to get half the votes in order to win, or walk the plank — pirates prefer more coins to fewer, and also prefer 0 coins to walking the plank).

   2. Is the contest duration too long?

   No, it’s nice to have a week. This cycle — one week of solving, one week of waiting for the winner and new problem to be announced — looks good to me. Especially if there are harder problems, or ones like the first that admit to many different solution methods and make for interesting discussions of techniques and pedagogy and stuff.

   3. Is the prize not good enough to warrant the time it takes to solve the problem?

   The problems are fun: that’s prize enough right there! Plus the fame. I don’t really care about the prize. But the fame! The glory! My name right there in the title of the post!

   4. How can the contest be improved?

   Maybe having two related problems, an easy and a hard, would be more interesting for a wider range of people, instead of having one sort of medium problem like you have now.

   5. Should we make the problem more matlab oriented?

   Heavens no! Well, unless you want to, but then it would be a different contest. I think making problems that are “matlabable” (matlab babble? No, able to be solved with matlab) would be fine, and then you’d get two types of solutions, those that people did by hand and those that people did by brute force on the computer. The first problem was like that; I did it by hand with combinatorics and also wrote a computer program to check all 3^5 cases just to be sure I had gotten it right.

   Thanks for the fun!
   –Joshua

2. on 28 Mar 2008 at 7:45 am 2UnA

   Hi guys, thanks for the interesting puzzle

   ..actually there is a slight flaw in joshua’s arguments..
   The money pot would never be split at at the last leprechauns as the when there are two leprechauns, leprechaun #2 would have voted for split and by the definition in the question that the money would split when there is 50% or more vote for split, the case would never reduce to 1 leprechuan. But nevertheless, his logic is sound and the reasoning is sufficient.

   A more interesting twist to the problem is that what if the leprechauns do not know the age of the other leprechauns.

3. on 28 Mar 2008 at 10:07 am 3Joshua Zucker

   Hi UnA,
   You might note that my argument says “If there is only one leprechaun left…” so if you deny that possibility then my if-then statement is still true.

   I don’t see what’s so special about 1 leprechaun never arising — if you start with 2^n + k, k < 2^n, you’ll never get less than 2^n. But you still need to look at all possible powers of 2 if you want to solve the problem in general for any starting number of leprechauns (including if you start with 1 leprechaun).

   I’ll have to think more about your final question about what happens when the leprechauns don’t know each others’ ages!

4. on 28 Mar 2008 at 2:26 pm 4Quan Quach

   Hmmmmmmmmmmmmmmmmmm . . . if each Leprechaun has zero knowledge on the ages of the other leprechauns . . .

   If there are only two leprechauns, then it wouldn’t matter how they voted because the expected value is the same in both situations.

   Very interesting indeed. I’ll have to think about this one!

5. on 28 Mar 2008 at 11:37 pm 5Joshua Zucker

   I think Quan’s argument generalizes: if they have no info, then they’re each equally likely to be “good” (old), so they just get 1/n on average whether they vote now or vote later.

   But maybe I’m missing something.

   Suppose on the other hand they know how to find the youngest current leprechaun, but not anyone else’s ages, so they know only who will leave if the vote to split fails. Then that leprechaun wants to vote yes but everyone else increases their expected share by voting no, so then you get down to the last two leprechauns splitting it evenly (since then the youngest remaining clearly votes yes).

   Hmmmm.

6. on 29 Mar 2008 at 7:40 am 6UnA

   hi guys..
   To Joshua> i see you point.. thanks for pointing that out.. my answer is actually similar to yours (i am one of the 12 ) except for the the case with 1 leprechaun.

   I was thinking about the twist to the problem..
   my current approach is to assume that the age of the leprechauns are normally distributed and that the mean and variance is known. Given that the leprechauns know these 2 parameters, they would then estimate their position in the 1000 leprechauns.

   The steps of the game would probably go as following..
   1. they estimate their own position and then vote as according to their projected position in the ideal case where they know everyone’s age. That is to say if you are a 4 year old you would definitely vote for split, but a 60 years old would vote for out.

   2.let voting proceed for one round and let the leprechauns reestimate their position in this new pool (estimated parameters should change as no of leprechauns change)

   the vote split when the size of group of leprechauns who thinks they are safe equals to the size of the group of those who think they aren’t (it need not necessary be at 512 )

   I think the number which is split is depend on the parent distribution model assumed and its parameters. (i am using normal for now). As for the actual model..think i might need some time..

   One assumption i made was that the age of the leprechaun that is being voted out is not being revealed..otherwise there should be a step where the leprechauns need to reestimate their distribution model (using a chi squared test? maybe).. just my two cents worth of thought..

   I am looking forward to the next Monday madness though. haha

7. on 06 Apr 2008 at 8:19 am 7Jonathan

   Hmm. I thought I provided a link to my blog?

8. on 25 Apr 2008 at 4:56 pm 8Wes Carroll

   Count me in! What can I do to get notified when a new problem is posted?

   W

9. on 25 Apr 2008 at 5:02 pm 9Quan

   subscribe to the RSS reader in the upper right hand side of the webpage!

Leave a Reply