that he will
cross every bridge once, and only once, on his return to the monastery.
This is, of course, quite easy to do, but on the way he thought to
himself, "I wonder how many different routes there are from which I
might have selected." Could you have told him? That is the puzzle. Take
your pencil and trace out a route that will take you once over all the
five bridges. Then trace out a second route, then a third, and see if
you can count all the variations. You will find that the difficulty is
twofold: you have to avoid dropping routes on the one hand and counting
the same routes more than once on the other.
[Illustration]
COMBINATION AND GROUP PROBLEMS.
"A combination and a form indeed."
_Hamlet_, iii. 4.
Various puzzles in this class might be termed problems in the "geometry
of situation," but their solution really depends on the theory of
combinations which, in its turn, is derived directly from the theory of
permutations. It has seemed convenient to include here certain group
puzzles and enumerations that might, perhaps, with equal reason have
been placed elsewhere; but readers are again asked not to be too
critical about the classification, which is very difficult and
arbitrary. As I have included my problem of "The Round Table" (No. 273),
perhaps a few remarks on another well-known problem of the same class,
known by the French as La Probleme des Menages, may be interesting. If
n married ladies are seated at a round table in any determined order,
in how many different ways may their n husbands be placed so that
every man is between two ladies but never next to his own wife?
This difficult problem was first solved by Laisant, and the method shown
in the following table is due to Moreau:--
4 0 2
5 3 13
6 13 80
7 83 579
8 592 4738
9 4821 43387
10 43979 439792
The first column shows the number of married couples. The numbers in the
second column are obtained in this way: 5 x 3 + 0 - 2 = 13; 6 x 13 + 3 +
2 = 83; 7 x 83 + 13 - 2 = 592; 8 x 592 + 83 + 2 = 4821; and so on. Find
all the numbers, except 2, in the table, and the method will be evident.
It will be noted that the 2 is subtracted when the first number (the
number of couples) is odd, and added when that number is even. The
numbers in the third column are obtained thus: 13 - 0 = 13; 83 - 3 = 80;
592 -
|