book in use contains 700 hymns. What is the smallest number

of single figured numerals which must be kept in stock so that the numbers of any four different hymns selected can be displayed ? How will the result be affected if an inverted 6 can be used for a 9 ? The answers are 86 and 81.
As another question take the following. A man bets l/?ith of his money on an even chance (say tossing heads or tails with a penny): he repeats this again and again, each time betting 1/nth of all the money then in his possession. If, finally, the number of times he has won is equal to the number
32 ARITHMETICAL RECREATIONS [CH. 11
of times he has lost, has he gained or lost by the transaction ? He has, in fact, lost.
Here is another simple question to which not unfrequently I have received incorrect answers. One tumbler is half-full of wine, another is half-full of water : from the first tumbler a teaspoonful of wine is taken out and poured into the tumbler containing the water: a teaspoonful of the mixture in the second tumbler is then transferred to the first tumbler. As the result of this double transaction, is the quantity of wine removed from the first tumbler greater or less than the quantity of water removed from the second tumbler ? In my experience the majority of people will say it is greater, but this is not the case.
Here is another paradox dependent on the mathematical theory of probability. Suppose that a player at bridge or whist asserts that an ace is included among the thirteen cards dealt to him, and let p be the probability that he has another ace among the other cards in his hand. Suppose, however, that he asserts that the ace of hearts is included in the thirteen cards dealt to him, then the probability, q, that he has another ace among the other cards in his hand is greater than was the probability p in the first case. For, if r is the probability that when he has one ace it is the ace of hearts, we have p = r .q^ and since p, q, r are proper fractions, we must have q greater than p, which at first sight appears to be absurd.
Permutation Problems. Many of the problems in per- mutations and combinations are of considerable interest. As a simple illustration of the very large number of ways in which combinations of even a few things can be arranged, I may note that there are 500,291833 different ways in which change for a sovereign can be given in current coins*, including therein the obsolescent double-florin, and crown ; also that as many as 19,958400 distinct skeleton cubes can be formed with twelve differently coloured rods of equal length f; while there are no less than (52!)/(13!/, that is, 53644,737765,488792,839237,440000
* The Tribune, September 3. 1906.
t Mathematical Tripos, Cambridge, Part I, 1894.
CH. Il]
ARITHMETICAL RECREATIONS
33
possible diflPerent distributions of hands at bridge or whist with a pack of fifty-two cards.
Voting Problems. As a simple example on combinations I take the cumulative vote as affecting the representation of a minority. If there are p electors each having r votes of which not more than 5 may be given to one candidate, and n men are to be elected, then the least number of supporters who can secure the election of a candidate must exceed pr/{ns + r).
The Knights of the Bound Table. A far more difficult permutation problem consists in finding as many arrangements as possible of n people in a ring so that no one has the same two neighbours more than once. It is a well-known proposition that n persons can be arranged in a ring in (n— l)!/2 different ways. The number of these arrangements in which all the persons have different pairs of neighbours on each occasion cannot exceed (n — l)(n — 2)/2, since this gives the number of ways in which any assigned person may sit between every possible pair selected from the rest. But in fact it is always possible to determine (n — l)(n — 2)/2 arrangements in which no one has the same two neiglibours on any two occasions.
Solutions for various values of 7i have been given. Here for instance (if n = 8) are 21 arrangements* of eight persons. Each arrangement may be placed round a circle, and no one has the same two neighbours on any two occasions.
1.2.3.4.5.6.7.8
; 1.2.5.6.8.7.4.3
; 1.2.7.8.4.3.5.6;
1.3.5.2.7.4.8.6
, 1.3.7.4.6.8.2.5
; 1.3.8.6.2.5.7.4;
1.4.2.6.3.8.5.7,
1.4.3.8.7.5.6.2,
, 1.4.5.7.6.2.3.8;
1.5.6.4.3.7.8.2
, 1.5.7.3.8.2.6.4^
1.5.8.2.4.6.3.7;
1.6.2.7.5.3.8.4
; 1.6.3.5.8.4.2.7
1.6.4.8.2.7.3.5;
1.7.4.2.5.8.6.3
; 1.7.6.3.2.4.5.8
, 1.7.8.5.6.3.4.2;
1.8.2.3.7.6.4.5
; 1.8.4.5.3.2.7.6
1.8.6.7.4.5.2.3.
The methods of determining these arrangements are lengthy,
and far from easy.
• Communicated to me by Mr E. G. B. Bergbolt, May, 1906, see The Secretary and The Queen, August, 1906. Mr Dudeney had given the problem for the case when 71 = 6 in 1905, and informs me that the problem has been solved by Mr B. D. Bewiey when n is even, and that he has a general method applicable when n is odd. Various memoirs on the subject have appeared in the mathe- matical journals.
u.
34 ARITHMETICAL RECREATIONS [CH. II
The Manage Problem*. Another difficult permutation problem, suggested by Lucas, is concerned with the number x of possible arrangements of n married couples, seated alternately man and woman, round a table, the n wives being in assigned positions, and the n husbands so placed that a man does not sit next to his wife.
The solution involves the theory of discordant permutations, and is far from easy. I content myself with noting the results when n does not exceed 10. When n = 3, ^ = 1 ; when ?i = 4, iz; = 2 ; when 9i = 5, ic = 13 ; when ?i = 6, a; = 80 ; when n = *7, x = 5l9; when n = 8, a; = 4738; when w=9, 0^ = 43387; and when n = 10, a;=439792.
Bachet's Weights Problem f. It will be noticed that a considerable number of the easier problems given in the last chapter either are due to Bachet or were collected by him in his classical Prohlhnes. Among the more difficult problems proposed by him was the determination of the least number of weights which would serve to weigh any integral number of pounds from 1 lb. to 40 lbs. inclusive. Bachet gave two solutions : namely, (i) the series of weights of 1, 2, 4, 8, 16, and 32 lbs. ; (ii) the series of weights of 1, 3, 9, and 27 lbs.
If the weights may be placed in only one of the scale-pans, the first series gives a solution, as had been pointed out in 1556 by Tartaglia|.
Bachet, however, assumed that any weight might be placed in either of the scale-pans. In this case the second series gives the least possible number of weights required. His reasoning is as follows. To weigh 1 lb. we must have a 1 lb. weight. To weigh 2 lbs. we must have in addition either a 2 lb. weight or a 3 lb. weight ; but, whereas with a 2 lb. weight we can weigh 1 lb., 2 lbs., and 3 lbs., with a 3 lb. weight we can weigh 1 lb., (3 - 1) lbs., 3 lbs., and (3 4- 1) lbs. Another weight of ,. 9 lbs. will enable us to weigh all weights from 1 lb. to 13 lbs. ; and we get thus a greater range than is obtainable with any
* Theorie des Nomhres, by E. Lucas, Paris, 1891, pp. 215, 491 — 495.
+ Bachet, Appendix, problem v, p. 215.
X Trattato de' numeri e misure, Venice, 1556, voL ii, bk. i, chap, xvi, art. 32.
CH. Il] ARITHMETICAL RECREATlONii 36
weight less than 9 lbs. Similarly weights of 1, 3, 9, and 27 lbs. suffice for all weights up to 40 lbs., and weights of 1, 3, 3^, ..., 3"~^ lbs. enable us to weigh any integral number of pounds from 1 lb. to (1 + 3 + 3^ + . . . 3"-^) lbs., that is, to i(3"-l)lbs.
To determine the arrangement of the weights to weigh any given mass we have only to express the number of pounds in it as a number in the ternary scale of notation, except that in finding the successive digits we must make every remainder either 0, 1 , or — 1 : to effect this a remainder 2 must be written as 3 — 1, that is, the quotient must be increased by unity, in which case the remainder is — 1. This is explained in most text-books on algebra.
Bachet's argument does not prove that his result is unique or that it gives the least possible number of weights required. These omissions have been supplied by Major MacMahon, who has discussed the far more difficult problem (of which Bachet's is a particular case) of the determination of all possible sets of weights, not necessarily unequal, which enable us to weigh any integral number of pounds from 1 to n inclusive, (i) when the weights may be placed in only one scale-pan, and (ii) when any weight may be placed in either scale-pan. He has investigated also the modifications of the results which are necessary when we impose either or both of the further condi- tions (a) that no other weighings are to be possible, and (b) that each weighing is to be possible in only one way, that is, is to be unique*.
The method for case (i) consists in resolving l-\-x-\-x- + ...-\-x^ into factors, each factor being of the form 1 + x^ -{- x^^ -{-... + x^"^; the number of solutions depends on the composite character of n -}- 1. The method for case (ii) consists in resolving the expres- sion a:-" -f a;-"+^ + ...-|-^~^-f-l+a;-l-...-h a;"-^ + x'"- into factors, each factor being of the form x'"^^ -+-... -I- x'"' -j-l -\-x^-\- ... + a;"""; ^ the number of solutions depends on the composite character of 2n -I- 1.
* See his article in the Quarterly Journal of Matheviatics, 16S6, vol. xxi, pp. 367 — 373. An account of the method is given in Nature, Dec. 4, 1600, vol. XLii, pp. 113—114.
3-2
36 ARITHMETICAL RECREATIONS [CH. II
Bachet's problem falls under case (ii), n = 40. MacMahon's analysis shows that there are eight such ways of factorizing a}~*° + x~^^ + , . . 4- 1 + . . . + '^"^ + ^^ First, there is the expres- sion itself in which a = 1, m=40. Second, the expression is equal to (1 — x^^)/a^^ (1 — x), which can be resolved into the product of (1 —x^)la;{l — x) and (1 — a;^^)/a^^(l — a;^); hence it can be resolved into two factors of the form given above, in one of which a = l, m = 1, and in the other a = 3, m = 13. Third, similarly, it can be resolved into two such factors, in one of which a = l, m = 4, and in the other a =9, m = 4. Fourth, it can be resolved into three such factors, in one of which a = l, m = l, in another a = 3, m=l, and in the other a = 9, m = 4. Fifth, it can be resolved into two such factors, in one of which a = 1, w = 13, and in the other a = 27, m = 1. Sixth, it can be resolved into three such factors, in one of which a=l, m = l, in another a = 3, m = 4, and in the other a =27, m=l. Seventh, it can be resolved into three such factors, in one of which a = 1, m = 4, in another a = 9, m = 1, and in the other a = 27, m= 1. Eighth, it can be resulved into four such factors, in one of which a = 1, m = 1, in another a = 3, m = 1, in another a = 9, m = 1, and in the other a = 27, m = 1.
These results show that there are eight possible sets of weights with which any integral number of pounds from 1 to 40 can be weighed subject to the conditions (ii), (a), and (6). If we denote p weights each equal to w by w^, these eight solutions are 1^°; 1, 3'^; l\ 9'; 1, 3, 9*; V\ 27; 1, S\ 27; 1\ 9, 27; 1, 3, 9, 27. The last of these is Bachet's solution: not only is it that in which the least number of weights are employed, but it is also the only one in which all the weights are unequal.
Problems in Higher Arithmetic. Many mathematicians take a special interest in the theorems of higher arithmetic: such, for example, as that every prime of the form 4?i+ 1 and every power of it is expressible as the sum of two squares*, and that the first and second powers can be expressed thus in only one way. For instance, 13 = 3^ + 2\ 13^ = 12-^ + 5^, 13^ = 46^ + 9^,
* Fermat's Diophantus, Toulouse, 1670, bk. m, prop. 22, p. 127; or Brassinne's Precis, Paris, 1853, p. 65.
CH. Il] ARITHMETICAL RECREATIONS 37
and so on. Similarly 41 = :>2f 4^ 41-= 40•^ + 0^ 4l='= 28(r + lir>2, and so on. Propositions such as the one just (jiiotcd may be found in text-books on the theory of numbers and therefore lie outside the limits of this work, but there are one or two questions in higher arithmetic involving points not yet quite cleared up which may find a place here. I content myself with the facts and shall not give the mathematical analysis.
Primes. The first of these is concerned with the possibility of determining readily whether a given number is prime or not. No test applicable to all numbers is known, though of course we can get tests for numbers of certain forms. It is difficult to believe that a problem which has completely baffled all modern mathematicians could have been solved in the seventeenth century, but it is interesting to note that in 1643, in answer to a question in a letter whether the number 100895,598109 was a prime, Fermat replied at once that it was the product of 898423 and 112303, both of which were primes. How many mathematicians to-day could answer such a question with ease ?
Mersexne's Numhers* Another illustration, confirmatory of the opinion that Fermat or some of his contemporaries had a test by which it was possible to find out whether numbers of certain forms were prime, may be drawn from Mersenne's Cogitata Physico-Matliematica which was published in 1644. In the preface to that work it is asserted that in order that 2^-1 may be prime, the only values of _p, not greater than 257, which are possible are 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257. To these numbers 89 must be added. Some years ago I gave reasons for thinking that the number 67 is a misprint for 61. With these corrections the statement appears to be true, and it has now been verified for all except fifteen values of p: namely, 101, 103, 107, 109, 137, 139, 149, 157, 167, 193, 199, 227, 229, 241, and 257. Of these values, Mersenne asserted that p = 257 makes 2^-1 a prime, and that the other values
* For rererences, see chapter x\ below.
38 ARITHMETICAL RECREATIONS [CH. II
make 2^ — 1 a composite number. The demonstration of the prime character of 2^— 1 when jj = 127 has not been published : and the verification in this case has not been corroborated by independent work.
Mersenne's revsult could not have been obtained empirically, and it is impossible to suppose that it was worked out for every case ; hence it would seem that whoever first enunciated it was acquainted with certain theorems in higher arithmetic which have not been re-discovered.
Perfect Numbers*. The theory of perfect numbers de- pends directly on that of Mersenne's Numbers. A number is said to be perfect if it is equal to the sum of all its integral subdivisors. Thus the subdivisors of 6 are 1, 2, and 3; the sum of these is equal to 6; hence 6 is a perfect number.
It is probable that all perfect numbers are included in the formula 2^"^ (2^ — 1), where 2^ - 1 is a prime. Euclid proved that any number of this form is perfect; Euler showed that the formula includes all even perfect numbers; and there is reason to believe — though a rigid demonstration is wanting — that an odd number cannot be perfect. If we assume that the last of these statements is true, then every perfect number is of the above form. It is easy to establish that every number included in this formula (except when ^ = 2) is congruent to unity to the modulus 9, that is, when divided by 9 leaves a remainder 1; also that either the last digit is a 6 or the last two digits are 28.
Thus, if j9= 2, 3, 5, 7,13, 17, 19, 31, 61, then by Mersenne's rule the corresponding values of 2^ — 1 are prime; they are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951; and the corresponding perfect numbers are 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, and 2658455991569831744654692615953842176.
* On the theory of perfect numbers, see bibliographical references by H. Brocard, L'IntermSdiaire des Mathematiciens, Paris, 1S95, vol. n, pp. 52 — 54; and 1905, vol. xii, p. 19. The first volume of the second edition of the French translation of this book contains (pp. 280—294) a summary of the leading investigation on Perfect Numbers, as also some remarks on Amicable Numbers.
CH. Il] ARITHMETICAL RECREATIONS 39
Euler's BiQiTADRATE THEOREM*. Another theorem, believed to be true but as yet unproved, is that the arith- metical sum of the fourth powers of three numbers cannot be the fourth power of a number; in other words, we cannot find values of x, y, z, v, which satisfy the equation x* + y* + z*=^v*. The proposition is not true of an algebraical sum, for Euler gave more than one solution of the equation x* -{- y* = z* -\- v*, for instance, x = 542, y = 103, z = 859, v = 514.
Goldbach's Theorem. Another interesting problem in higher arithmetic is the question whether there are any even integers which cannot be expressed as a sum of two primes. Probably there are none. The expression of all even integers not greater than 5000 in the form of a sum of two primes has been effected -f-, but a general demonstration that all even integers can be so expressed is wanting.
Lagrange's Theorem:!:. Another theorem in higher arith- metic which, as far as I know, is still unsolved, is to the effect that every prime of the form 4?2 — 1 is the sum of a prime of the fbrm 4n 4- 1 and of double another prime also of the form 4?i + 1 ; for example, 23 = 13 + 2 x 5. Lagrange, however, added that it was only by induction that he arrived at the result.
Fermat's Theorem on Binary Powers. Fermat enriched mathematics with a multitude of new propositions. With one exception all these have been proved or are believed to be true. This exception is his theorem on binary powers, in which he asserted that all numbers of the form 2"* + 1, where m= 2", are primes §, but he added that, though he was convinced of the truth of this proposition, he could not obtain a valid demonstration.
• See Euler, Commentationes Arithmetic ae CoUectae, St Petersburg, 1849, vol. I, pp. 473—476 ; vol. ii, pp. 450—456.
t Transactions of the Halle Academy {Naturforschung), vol. lxxii, Halle, 1897, pp. 5—214: see also L'IntermSdiaire des Mathematiciens, 1903, vol. x, and 1904, vol. xi.
+ Nouveaiix Blemoires de VAcademie Royale des Sciences, Berlin, 1775, p. 356.
§ Letter of Oct. 18, 1G40, Opera^ Toulouse, 1079, p. 162 : or Brassinne's Pricis, p. 143.
40 ARITHMETICAL RECREATIONS [CH. II
It may be shown that 2'^ + 1 is composite if m is not a power of 2, but of course it does not follow that 2'** + 1 is a prime if m is a power of 2, say, 2^ As a matter of fact the theorem is not true. In 1732 Euler* showed that if n= 5 the formula gives 4294,967297, which is equal to 641 x 6,700417 : curiously enough, these factors can be deduced at once from Fermat's remark on the possible factors of numbers of the form 2*" + 1, from which it may be shown that the prime factors (if any) of 2^'- + 1 must be primes of the form 64?i + 1.
During the last thirty years it has been shown f that the resulting numbers are composite when ?i= 6, 7, 8, 9, 11, 12, 18, 23, 36, 38 and 73. The digits in the last of these numbers are so numerous that, if the number were printed in full with the type and number of pages used in this book, many more volumes would be required than are contained in all the public libraries in the world. I believe that Eisenstein asserted that the number of primes of the form 2'" + 1, where m = 2", is infinite: the proof has not been published, but perhaps it might throw some light on the general theory.
Fermat's Last Theorem. I pass now to another assertion made by Fermat which hitherto has not been proved. This, which is sometimes known as Fermat's Last Theorem, is to the effect^ that no integral values of x, y, z can be found to satisfy the equation x^ ^ y^ — z^\ if n is an integer greater than 2.
* Commentarli Academiae Scientiarum Petropolitanae, St Petersburg, 1738, vol. VT, p. 104 ; see also Novi Comm. Acad. Sci. Petrop., St Petersburg, 1764, vol. IX, p. 101 : or Commentationes Arithmeticae Collectae, St Petersburg, 1849,
vol. I, pp. 2, 357.
t For the factors and bibliographical references, see A. J. C. Cunningham and A. E. Western, Transactions of the London Mathematical Society, 1903, series 2, vol. i, p. 175 ; and J. C. Morehead and A. E. Western, Bulletin of the American Mathematical Society, 1909, vol. xvi, pp. 1—6.
X Fermat's enunciation will be found in his edition of Diophantus, Toulouse, 1670, bk. II, qu. 8, p. 61 ; or Brassinne's Precis, Paris, 1853, p. 53. For bibliographical references, see the article on the theory of numbers in the Encyclopedic des Sciences Mathematiques : considerable additions are embodied in the French translation of this book which is therefore generally preferable to the German original. See also L'Intermediaire des Mather.iaticiens, Paris, 1908, vol. XV, p. 2S4.
CH. Il] ARITHMETICAL RECREATIONS 41
This proposition has acquired extr.K^rdiriary celebrity from the fact that no general demonstration of it has been given, but there is no reason to doubt that it is true.
Fermat seems to have discovered its truth first* for the case n = 3, and then for the case n = 4). His proof for the former of these cases is lost, but that for the latter is extant f, and a similar proof for the case of n = 3 was given by Euler J:. These proofs depend upon showing that, if three integral values of as, y, z can be found which satisfy the equation, then it will be possible to find three other and smaller integers which also satisfy it: in this way finally we show that the equation must be satisfied by three values which obviously do not satisfy it. Thus no integral solution is possible. It would seem that this method is inapplicable except when ?i = 3 and n = 4.
Fermat's discovery of the general theorem was made later. A demonstration can be given on the assumption that every number can be resolved in one and only one way into the product of primes and their powers. This assumption is true of real numbers, but it is not true when complex factors are admitted. For instance 10 can be expressed as the product of 3+1 and 3 - i, or of 3 4- 2 and 3 - 1, or of 2, 2 + i, and 2 - 1. It is possible that Fermat made some such erroneous supposition, though it is perhaps more probable that he discovered a rigorous demonstration. At any rate he asserts definitely that he had a valid proof — demonstratio mirabilis sane — and the fact that no theorem on the subject which he stated he had proved has been subsequently shown to be false must weigh strongly in his favour; the more so because in making the one incorrect statement in his writings (namely, that about binary powers) he added that he could not obtain a satisfactory demonstration of it.
It must be remembered that Fermat was a mathematician of quite the first rank who had made a special study of the theory of numbers. The subject is in itself one of peculiar
* See a Letter from Fermat quoted in my History of Mathematics, London,