## Nov 15 The Riddle of the Pilgrims

This is the twelfth Ernest Dudeney puzzle that I've written up on this website and if you want to read others you can get a collection of them here. This particular one is from his tour de force: The Canterbury Puzzles, although I met it at the conference of my exam board, MEI, one year. As always, I'll let Dudeney introduce it in his original words:

"One day, when the monks were seated at their repast, the Abbot announced that a messenger had that morning brought news that a number of pilgrims were on the road and would require their hospitality.

"You will put them," he said, "in the square dormitory that has two floors with eight rooms on each floor. There must be eleven persons sleeping on each side of the building, and twice as many on the upper floor as on the lower floor. Of course every room must be occupied, and you know my rule that not more than three persons may occupy the same room."

I give a plan of the two floors, from which it will be seen that the sixteen rooms are approached by a well staircase in the centre. After the monks had solved this little problem and arranged for the accommodation, the pilgrims arrived, when it was found that they were three more in number than was at first stated. This necessitated a reconsideration of the question, but the wily monks succeeded in getting over the new difficulty without breaking the Abbot's rules. The curious point of this puzzle is to discover the total number of pilgrims."

...

Since there has to be at least 1 pilgrim in each room, that means we can fill in 8 on each layer straight away. Since we have to have twice as many on the upper layer we would have to fit in 8 more up there. The sides already have 6 people on, so we need to arrange the 8 in the upper layer so that each side sums to an additional 5. However we can only place a maximum of 2 pilgrims in each room since there is already one pilgrim in each.

It turns out that 8 pilgrims isn't enough to get 5 on each side. The most we can get is 4 per side if we place 2 pilgrims in each corner room (to maximise them so that they can be double counted).

So let's try the problem again with more pilgrims. If we increase the number on the lower level by 1 then we have to increase the number on the top layer by 2. This becomes a problem of placing 10 additional on the upper and 1 on the lower. Here’s a (the) way and the resulting solution:

We want to put in an additional 3 pilgrims, so let's start with 1 in each room again and add an additional 12 on the upper and 2 on the lower. There are six distinct ways to place the 2 on the lower level, but the way that seemed most likely to me by placing them in opposite corners looked most likely and ended up working. I haven't explored whether the answer is unique barring rotations, but I suspect it is. Here's the solution which gives a final answer of 30 pilgrims to the riddle:

To just check that this is the only number of pilgrims that works we should check fitting 14 on the upper and 3 on the lower above the base number. The 14 on the upper will have to be divided into 6 rooms of 2 and two rooms of 1 or 7 rooms of 2. We want the sides to sum to 5, so we can't have 3 rooms in a row filled with 2, so the only orientation that works (just) is having the two rooms of 1 in opposite corners. However the 3 pilgrims on the lower are now going to push this over. Therefore it is impossible to fit them in and it follows that any higher number are also too many.