### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,959 hits

Advertisements

Programming Enigma Puzzles

2 June 2015

Posted by on **From New Scientist #1432, 29th November 1984** [link]

Blackbird pie is popular at the Palace. The King and Queen help themselves to the pie in turn until it is finished. But court etiquette is strict. It is bad form to cut a blackbird in two. It is greedy to cut oneself a slice containing more birds than the previous slice taken. It would be the height of ill-breeding for the King, who has the first go, to take the whole lot straight away. But the King does like finishing the pie.

How many blackbirds should he take in his first slice to be sure of being able to do this?

There are, of course, four-and-twenty blackbirds in a pie.

[enigma285]

Advertisements

%d bloggers like this:

This Python program runs in 42ms.

Solution:The King should take 8 blackbirds in his first slice to ensure he gets to finish the pie.If the King takes 8 blackbirds, that leaves 16 blackbirds in the pie when the Queen chooses and she can choose at most 8 blackbirds.

If she chooses to take just 1, that leaves 15, and both the King and Queen are can only take 1 each of the remaining 15 at each turn. As 15 is an odd number the King gets to take the last piece. And in general if the King is presented with an odd number of birds he can take just 1 and will always be left with the last piece of pie (and if he is presented with an even number of birds if he takes only 1 he is forcing the Queen to take the last piece of pie).

If the Queen takes 2, then that leaves 14 birds. The King takes 2 (as taking 1 would force the Queen to finish the pie), leaving 12. So the Queen is presented with an even number of birds and can choose to take 1 or 2. If she takes 1, then the King is forced to take the last piece of pie. If she takes 2 then the King is again presented with an even number of birds and so will also choose to take 2. And so each takes 2 of the remaining birds, until the King takes the final two. (And in general if the King is presented with an odd number of pairs, he can take 2 and force the Queen to either take 2 until the King is presented with the final pair, or to take 1 and present the King with an odd number of birds, in which case he also eventually takes the final piece).

If the Queen takes 3, then that leaves 13 birds, so the King can take 1 and force each remaining turn to take 1 so he ends up with the final piece.

If the Queen takes 4, then that leaves 12 birds. The King also takes 4, leaving 8 birds. If the Queen takes 4 of these, the King takes the remaining 4. If the Queen takes 3 or 1 the King takes 1 of the remaining odd number and ends up with the final piece. If the Queen takes 2, then King is presented with 6 birds, an odd number of pairs, so will end up with the final piece.

If the Queen takes 5, then that leaves 11 birds. The King can take 1, and so end up taking the final piece. Or he can take 3, leaving 8. So the situation above repeats (but this time the Queen doesn’t have an option of taking 4).

If the Queen takes 6, then that leaves 10 birds (an odd number of pairs). The King takes 2, and eventually the last pair.

If the Queen takes 7, then that leaves 9 birds. The King takes 1, and ends up taking the final piece.

If the Queen takes 8, then the King takes the remaining 8.

My program can be modified to produce the 21 possible sequences. Each starts with the King choosing 8, and ends after an odd number of “takes” with the King taking the final piece of the pie:

Hi Jim

Any chance you could give a few more words of explanation on how line 12 of your code works ?- there seems to be a lot going on in this single line!

Thanks

Geoff

Certainly. Here’s a more detailed explanation of how my code works.

The

choose(t, m)function is a generator that finds what values the King can choose, when presented with a pie containingtbirds, and the maximum number of birds that can be taken ism, such that, no matter what number of birds the Queen chooses, the King can always be certain to take the final piece of pie.It is written as a Python generator, so when it finds a value,

k, it uses theyieldoperator to pass it back to the calling routine. The calling routine can collect all the values (if there are any) by treating it as an iterator (which is what we do in lines 16 and 17).This means we can collect all the values by wrapping the call in a

list()constructor. So:list(choose(7, 5)) ⇒ [3, 1]list(choose(6, 5)) ⇒ []When there are no guaranteed choices for the King this returns an empty list. In a boolean context an empty list evaluates to

False, whereas a non-empty list evaluates toTrue.In the main part of the routine (at line 10), we consider how many birds the King can take by looking at values of

k, starting with the largest number possible,min(t, m), and then working down to taking only 1 bird.So we consider what happens when the Queen makes her choice from the remaining

t - kbirds. She can choose any valueqfrommin(k, t - k)down to 1. And we want to know if whatever value she chooses whether the King can always ensure he takes the final piece of pie.For each value

qthat the Queen chooses we look to see if there are values that the King can choose from the remainingt - (k + q)birds (with a maximum take ofq) to guarantee getting the last piece of pie. We do this with a recursive call tochoose(t - k - q, q), wrapped in thelist()constructor to explore all the values.We do this with the

all()construct, which returnsTrueif all the values it is passed areTrue(when evaluated in a boolean context), andFalseotherwise. (all([])isTrue). So this checks if, whatever value the Queen chooses, the King always has a take that will get him the final piece of pie.If this is the case, then the original choice for the King

kis a value that guarantees he can get the last piece of pie, so we useyieldto return it to the calling routine.If hope that gives you a better idea of what is going on.

One of the advantages of using

all(), rather than using a Pythonforloop, is that it will exit early if one of the elements it is testing evaluates toFalse, so it saves a more complicated loop with an early exit.In fact, instead of using

list(choose(t, m))to look for non-empty lists of values for the King to choose, we could use theany()construct. Which returnsTruewhen any of the elements it is passed evaluate toTruein a boolean context. (any([])isFalse).Also I now realise that there is no reason to examine

korqin reverse order, so we can simplify theirange()calls.So the modified program looks like this:

Also, after the King takes 8 birds, if the Queen wants to maximise the number she gets in total she should take 7 birds. The King then takes 1 bird to guarantee he gets the final piece of pie, and so each following take can only be one. This ends with the King taking a total of 13 birds and the Queen taking a total of 11.

If the Queen wants to minimise the number of birds she gets in total the best she can do is 8 (and the King gets the other 16). There are many ways this can be achieved. The shortest is for her to take 8 on her first move, the King then takes the remaining 8. The longest is for her to take 1 on her first move, the remaining 15 birds are then taken one at a time.