When last they met, the Baron challenged Sir R----- to a game of cards in which he was at each turn to choose one of the Jack, Queen and King of hearts to stay in place and exchange the remaining pair. If he could find a sequence of moves such that he chose each card to stand in each place once and once alone, then he should have won a coin from the Baron; if not, then the Baron should have won a coin from him.

The key to figuring whether such a sequence could be found is to arrange the permutations of the cards in a wheel, thusly

Note that from each arrangement of the cards, the path through the hub of the wheel leads to the arrangement that results from selecting the centre card to stand, whilst those on its circumference lead to the arrangements that result from choosing the left or right cards instead.

Note further that following each path both to and fro involves choosing the same card to stand in the same place and consequently a winning sequence of moves should be one for which every path is traversed exactly once.

That no such route exists follows from the delightfully simple proof given by the great Euler of the impossibility of taking a walk during which one would cross, once and once alone, each of the seven river bridges of Königsberg, the layout of which might be roughly sketched as

The proof commences with the observation that to return to any of the land masses one must have first crossed a bridge out of it and then crossed another back. It is therefore only possible to begin and end such a walk upon the same piece of land if it has an even number of bridges upon it. Consequently, if a piece of land has an odd number of bridges connected to it then it must contain either the start or the end of the walk, but not both, and so there can be but two, if there be any at all, that do so. That all four regions have an odd number of bridges means that we can have no doubt whatsoever that no such walk is possible.

I explained this to the Baron, but I had the distinct impression that he failed to grasp its significance; specifically, that upon the wheel representing the moves of the Baron's game, all six permutations of the cards have three paths connected to them and so it is impossible to find a route that traverses each any every one of them once and once only and I should therefore have most emphatically advised Sir R----- to decline the Baron's wager!

The key to figuring whether such a sequence could be found is to arrange the permutations of the cards in a wheel, thusly

Note that from each arrangement of the cards, the path through the hub of the wheel leads to the arrangement that results from selecting the centre card to stand, whilst those on its circumference lead to the arrangements that result from choosing the left or right cards instead.

Note further that following each path both to and fro involves choosing the same card to stand in the same place and consequently a winning sequence of moves should be one for which every path is traversed exactly once.

That no such route exists follows from the delightfully simple proof given by the great Euler of the impossibility of taking a walk during which one would cross, once and once alone, each of the seven river bridges of Königsberg, the layout of which might be roughly sketched as

The proof commences with the observation that to return to any of the land masses one must have first crossed a bridge out of it and then crossed another back. It is therefore only possible to begin and end such a walk upon the same piece of land if it has an even number of bridges upon it. Consequently, if a piece of land has an odd number of bridges connected to it then it must contain either the start or the end of the walk, but not both, and so there can be but two, if there be any at all, that do so. That all four regions have an odd number of bridges means that we can have no doubt whatsoever that no such walk is possible.

I explained this to the Baron, but I had the distinct impression that he failed to grasp its significance; specifically, that upon the wheel representing the moves of the Baron's game, all six permutations of the cards have three paths connected to them and so it is impossible to find a route that traverses each any every one of them once and once only and I should therefore have most emphatically advised Sir R----- to decline the Baron's wager!

\(\Box\)

## Leave a comment