Solution: Knights and Pages

Last week I posted a puzzle that I originally found in the book The Chicken From Minsk And 99 Other Infuriating Brainteasers by Yuri B Chernyak and Robert M. Rose. Here is a scan of the puzzle as it appears in that book.

knights&pages

And here is a composite scan showing the official solution from the book. Click on the thumbnail to read. (I have some issues with their solution for the second part, but we’ll get to that later.)

Now, if all you came for was a solution, then you’ve already read as far as you need to. But if you want to go a little deeper, read on. I’ll start by describing how I personally went about solving the first part of the puzzle.

Part one (three knights and three pages)

In my very earliest attempts, I represented the three knights with capital letters A, B, C and the three pages with lower-case latters a, b, c. But I found this notation got in the way, with too many symbols spoiling the mathematical broth.

So I came up with a simpler, more elegant notation. Three capital letters A, B, C, one for each knight-page pair. A bar over the letter represents the knight, and a bar under the letter represents the page. Also, I used a vertical bar to represent the river, and a dot above one side or the other to represent the boat.

Using this clearer notation made the puzzle much easier to solve. Below is the solution I came up with, which differs a little from the solution in the book (as the book says, it is not unique). As an aid to the reader I’ve added green arrows that show who crosses the river at each step. So ‘p’ means a page crosses, ‘p2’ that two pages cross, ‘k’ that a knight crosses, ‘k2’ that two knights cross, and ‘pk’ that a page and a knight cross together. It’s in green to make it clear that I didn’t actually write this down while scribbling my solution on paper – it’s purely for the reader’s benefit.

If you compare my solution with the solution in the book, you’ll notice that the second configurations differ, as do the second-to-last configurations. It just so happens there are two different solutions for those moves. At the start, I moved two pages forward then one page back, whereas the book moves a knight and a page and then the knight back. At the end, I moved a knight back and then finished by moving a knight and a page, whereas the book moves a page back and finishes by moving two pages. For all the other steps, there’s only one way to do them provided you disregard the identities of individual knights and pages.

Part two (four knights and four pages)

The brute force approach

The second part of the puzzle is to prove that there is no solution for four pairs of knights and pages, and the easiest way to do this is to investigate each route individually and show that each one leads to a dead end. My way of doing so was to scribble down a diagram like this, which captures all possible routes that you can follow from the starting position:

The notation is the same as in the previous section, but this time I really did include all the arrows and labels, which were useful for keeping track of which paths I’d already tried.

I’ve captured in a diagram what the book attempts to explain in words, but for some reason the book ignores the branch where the two knights cross the river. It is therefore incorrect when it says that that the position with knights on one side and pages on the other is inevitable.

But in my opinion, this brute force method – following routes one at a time until there are none left to follow – is not very satisfying. I wondered if I could find a deeper pattern, some observation that, once made, would make it obvious why no solution exists. So I got thinking.

Observations on symmetry

One thing I noticed was the significant amount of symmetry in the first part of the puzzle. The initial configuration, with everyone on the starting side of the river, is a mirror image of the final configuration, with everyone on the finishing side. The 2nd and 2nd-last configurations are a special case because of there being two different solutions, but they are still mirror images of each other if you consider all possible solutions. The 3rd and 3rd-last configurations (with a single page on one side of the river and everyone else on the other) are mirror images of each other as are the 4th and 4th-last (with the knights on one side and the pages on the other), the 5th and 5th-last, and so on. Remember that the identities of individual knights and pages are irrelevant here.

I realised that if I could prove symmetry — that if there’s a solution at all then there’s a symmetric solution in which the nth step is always the mirror image of the nth-last step — then I could easily prove the lack of a solution with four, five, or any higher number of knights and pages. And this would be much more elegant than the brute force proof.

Here’s why that follows. If there is a symmetric solution, then half way through the solution there must be either (a) a configuration that is its own mirror image, or (b) a configuration that, when one more move is performed, is converted to its own mirror image. Now, we can rule out (a) because there is only one boat, which must be on one side of the river or the other, so no configuration can possibly be its own mirror image. As for (b), we can easily see that with four knights and pages there is no possible configuration that can be converted to its own mirror image in one move.

There is such a configuration with five knights and pages (shown below), but it doesn’t lead anywhere: all moves other than endlessly switching to and from mirror images are dead ends. So it can’t be part of a solution.

The algebraic approach

In order to investigate symmetry, I stopped using letters to represent knights and pages, and started using them to represent configurations. For example, the letter X might represent the configuration in which two pages and the boat are on the east side of the river and everyone else is on the west. (Actually, if it’s the River Neva, as in the book, then it should be north and south, but I think it’s best to keep the diagrams aligned with the tradition of putting north at the top of the page.)

Now, let represent the minimum number of moves required to get from configuration P to configuration Q.

From the definition of “minimum mumber of moves” we can immediately see that the following equation is true. Call this Premise #1.

Because every configuration has its mirror image (identical except that each object is on the opposite side of the river), let P with a bar on top represent the mirror image of P, etc. Now, the following two equations express elementary facts about the puzzle. The first follows from the fact that all moves are reversible (e.g. if you send a knight out on a boat it’s always possible to send him back again), and the second follows from the fact that whatever’s possible on one side of the river is possible on the other. Call these Premise #2 and Premise #3 respectively.

Now suppose M is an intermediate configuration on the route from A to A-bar, and that M is nearer to A than to A-bar. We capture those suppositions in the following two equations. Call them Premise #4 and Premise #5 (the latter is not used below but I have included it for completeness).

Consider the route from M to M-bar. From Premise #1 we have the first equation below, and with help from Premises #2, #3 and #4 we can get from there to the second equation below.

Let us now reflect upon the implications of this final equation.

If the less-than-or-equal sign were a less-than sign, we would have what we were looking for: proof of a symmetric route from any allowable configuration to its mirror image, i.e. . On the other hand, if the less-than-or-equal sign were an equal-to sign, this would describe another type of route which I’ll call cyclic. A cyclic route is really a pair of routes in which each, traversed backwards, is a mirror image of the other. In a diagram: (note the complete cycle). It’s not hard to invent alternative rules in which all my premises are true but solutions are cyclic rather than symmetric. To prove symmetry for this particular puzzle, we need more information.

The geometric approach

Having reached a dead end, I switched to a totally different approach in which I tried representing all possible moves and configurations in simple diagrams.

The first step was to realise that every possible combination of knights and pages on a given side of the river can be represented in a two-dimensional grid, with one axis for the number of knights and the other for the number of pages. The number of matched knight-page pairs is a dependent variable that’s always the same as the number of pages, because if there are no knights then there are no pairs, and if there are knights, then every page is part of a pair.

The next step was to understand which combinations of knights and pages are safe. Here’s what it boils down to.

  • If no knights are present then any number of pages is safe.
  • If all knights are present then any number of pages is safe.
  • If there are more pages than knights (but some knights) then the excess pages would be killed, making that an unsafe configuration.
  • If there are more knights than pages (but not all knights) then some page on the other side of the river would be killed, making that an unsafe configuration.
  • In summary, the only safe configurations are where there are no knights, the maximum number of knights, or the same number of knights as pages.

Here are diagrams showing safe and unsafe configurations for versions of the puzzle with three, four and five pairs of knights and pages. Grid coordinates represent the number of knights and pages on a given side of the river. Green ticks represent allowable combinations and red crosses unallowable ones.

We also need a diagram representing all possible moves, i.e. the ways of getting from one configuration to another. Here’s what we know. Moves in which the boat leaves alternate with moves in which the boat returns. When the boat leaves, the number of knights may decrease by one or two, the number of pages may decrease by one or two, or the number of knights and pages may both decrease by one each. When the boat returns, the numbers increase rather than decrease, but the differences are the same. We can capture all these possibilities in the following diagram.

Putting the two diagrams together – one for configurations, one for moves – we have a convenient graphical representation of the entire puzzle. These diagrams are a powerful tool for understanding the puzzle, for seeing not only what is or is not possible, but why. I’ll try to justify that claim shortly.

The diagrams can be interpreted in either of two ways, and you can choose the way you like best. The first is to simply take it as a rule that “boat outgoing” moves alternate with “boat incoming” moves. The alternative is to imagine that the diagrams are three-dimensional, with a front layer (out of the page) representing the state of having the boat, and a back layer (into the page) representing the state of not having the boat. (Or the other way around as long as you’re consistent.) Then the “boat outgoing” arrows lead from the front layer to the back layer, the “boat incoming” arrows lead from the back layer to the front.

Using the diagrams

To see the diagrams in action. let’s first use them to solve the first part of the puzzle, with three knights and pages.

Taking the diagrams as representing the west (starting) side of the river, we begin with three pages, three knights, and one boat, ready for the first “boat outgoing” move. I’ll write configurations in coordinate form, in this case (3, 3, 1). You can trace the route on the diagram and see that after four moves, we end up at (1, 3, 1) – i.e. one page, three knights, one boat. Another boat-outgoing move takes us vertically to (1, 1, 0), a boat-incoming move to (2, 2, 1), a boat-outgoing move to (2, 0, 0), and four moves later we are at (0, 0, 0) with all pages and knights departed from that side of the river.

Putting this in a more general way that applies to any number of knights and pages, we begin in the part of the Z-shaped safe area where the number of knights is at a maximum (call this Zone One), must find a way to leap onto the region where the number of knights and pages is the same (call this Zone Two), and then must leap again onto the region where there are no knights remaining (call this Zone Three). This in a nutshell it’s the reason why there is no solution with four or more pairs.

To elaborate: you can’t leap further than two grid spaces, and after you arrive on Zone Two (via a boat-outgoing move) your next move must be a boat-incoming move, which takes you away from Zone Three. With four knights and pages, Zone Three is too far to jump, and your only choices are to go home or else stay in Zone Two for all eternity, alternating between (2, 2, 0) and (3, 3, 1). This is all much clearer on the diagram than in words, and is a much more elegant proof than the brute force approach because it lets us see intuitively why there are no solutions.

The diagrams also help us understand why the solutions are symmetric. For a given coordinate, its mirror image counterpart (which, on the same side of the river, contains the complementary set of objects) is removed from it by a 180 degree rotation. The reason why solutions are symmetric and not cyclic is simply that the safe zone with knights and pages in equal numbers passes through the centre, where configurations come closest to being their own mirror image counterparts, and all solutions must traverse that zone.

Part three (with the island)

I’m not going to go into much detail about the third part of the puzzle, but I will make a few remarks. First, let’s translate the solution from the book (which generalises to any higher number of knight-page pairs) into my own notation. It begins as follows:

That takes us half way — notice that the configuration I’ve stopped at is self-symmetric (i.e. is its own mirror image). So the rest of the solution is simply a mirror image of the steps that have gone before, and I won’t bother writing it out.

In the previous parts of the puzzle we observed that self-symmetric configurations are not possible, but with the island they are easy. All you need is to have the same sorts of characters on both sides of the river, and everything else (including the boat) on the island. It’s important to understand what a difference an island makes. Another difference, of course, is that knowing what’s happening on one side of the river doesn’t automatically tell you what’s happening on the other, which makes it much harder to draw neat little diagrams. But it also means that configurations with more knights than pages are potentially safe (example: the 3rd-last step shown above).

As for the version with five knights and pages, I won’t write out the whole thing, but I’ll tell you that if you try the solution in the book you’ll find that the configuration just before the half-way point is as follows. It’s converted into its own mirror image by taking knight C and his page to the other side.

Going back to four knights and pages for a moment, I’d like to point out an alternative solution that involves reducing it to the version with three knights, three pages, and no island. Here’s now to do that:

Now the task of getting pairs A, B and C across the river is reduced to the original problem, after which we can perform the mirror image of the steps shown above to retrieve pair D from the island. (Actually, the final step shown above is redundant, because the first step in solving the reduced version will be to take pair C back across the river.)

I like this puzzle because there are many ways of thinking about it, and in seeking to understand it more deeply we touched on quite a wide range of ideas. I hope you’ve enjoyed the tour. If you solved the puzzle using a different approach to mine, or you have some additional insights to add, then I encourage you to share what you’ve got.

Advertisements

You are welcome to add your thoughts.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s