16 The Sheep Hotel – Mathekalender

Author: Matthew Maat (Universiteit Twente)

Project: Combining algorithms for parity games and linear programming

Challenge

With the sound of the angels’ choir still resounding in their memory, the shepherds Ananias, Benjamin, Caius and David head for Bethlehem. However, they first need to drop off their sheep at a sheep hotel, since they have large flocks of sheep of different types. All four of them go to different hotels. The standard rules for sheep hotels in the first century are as follows:

You are allowed to use as many rooms as you like.
It is not allowed to spread two different types of sheep over the exact same set of rooms. For example, if we divide all the black sheep over room number 1 and 2, we may put all the white sheep in room 1, or you may divide the white sheep over rooms 1,2 and 3, but we may not divide the white sheep exactly over rooms 1 and 2. We are also not allowed to, for example, put all black and all white sheep in room 1.
For every two types $x$ and $y$ of sheep, there is a type $z$ (which may be $x$ or $y$ ) such that the following holds for every room: Either there are no sheep of type $x$ , $y$ or $z$ in the room, or there are sheep of type $z$ in the room, and also sheep of type $x$ and/or $y$ .
The price is determined by the room with the most types of sheep. You pay as many gold pieces as there are types of sheep in that room.

For example, we can consider a shepherd with black (bl), white (w) and brown (br) sheep. We can fulfill the rules as follows (cf. figure 1):

For rule 1: The shepherd uses two rooms.
For rule 2: He puts all white sheep in room 1, all black sheep in room 2, and divides the brown sheep over rooms 1 and 2.
For rule 3: If $x$ is black sheep and $y$ is white sheep, we choose $z$ to be brown sheep. (If we swap the roles of $x$ and $y$ we will always choose the same $z$ . With this convention, the table in figure 1 is shortened accordingly.) If $x$ is black or white sheep and $y$ is brown sheep, then we choose $z$ to also be brown sheep.
For rule 4: In this case, the room with the most types of sheep contains two types of sheep. Therefore the shepherd pays two gold.

$\begin{array}{|c|c|c|c|}\hline\textbf{x, y} & \mathrm{bl}, \mathrm{w} & \mathrm{w}, \mathrm{br} & \mathrm{bl}, \mathrm{br}\\\hline\textbf{z} & \mathrm{br} & \mathrm{br} & \mathrm{br}\\\hline\end{array}$

Figure 1: Cheapest distribution for a shepherd with 3 types of sheep. top: distribution inside the rooms. bottom: Table of corresponding mapping $x,y\mapsto z$ .

Now it is given that Ananias has 4 types of sheep, Benjamin has 5, Caius has 6, and David has 7. Being experienced with the rules, each shepherd quickly finds the distribution of sheep that costs the least for them. It turns out that all of them only need to use 3 rooms each for their cheapest distribution. Ananias pays $A$ gold, Benjamin pays $B$ gold, Caius pays $C$ gold, and David pays $D$ gold. What is $A+B+C+D$ ?

Possible Answers

Challenge as PDF