Not a member?     Existing members login below:

Amusements in Mathematics

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 Problême des Ménages, 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 × 3 + 0 - 2 = 13; 6 × 13 + 3 + 2 = 83; 7 × 83 + 13 -
2 = 592; 8 × 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 - 13 = 579;
4821 - 83 = 4738; and so on. The numbers in this last column give the required solutions.
Thus, four husbands may be seated in two ways, five husbands may be placed in thirteen
ways, and six husbands in eighty ways.
The following method, by Lucas, will show the remarkable way in which chessboard
analysis may be applied to the solution of a circular problem of this kind. Divide a square
into thirty-six cells, six by six, and strike out all the cells in the long diagonal from the
bottom left-hand corner to the top right-hand corner, also the five cells in the diagonal
 
 
Remove