7. arithmetic & number theoretic recreations a. Fibonacci numbers

Change, p. 211. Change a dollar into 50 coins. I.e. 100 for 50 at 1, 5, 10, 25, 50. (2, 0) answers, both given. Ripley's and Scott, pp. 129-130 are the same problem but give only one answer.

Six bills, p. 217. Pay $63 with six bills, no $1 bills used. I.e. 63 for 6 at 2, 5, 10, 20, 50. (1, 0) answer, given.

McKay. At Home Tonight. 1940.

Prob. 3: A mixed bag, pp. 63 & 75-76. 50 for 50 at 5, 1, ½. (Sheep, lambs, bundles of rabbits, where a bundle is one item.) This has (6, 5) solutions, but it is added that he got the same number of two items and this has (2, 1) solutions of which he gives the positive one.

Prob. 5: A question of change, pp. 63 & 77. I want to pay a friend 6/6 (= 78d), but I only have 4s (= 48d) pieces and he only has half-crowns (= 30d). I.e. 78 = 48x - 30y. Gives the smallest solution.

Prob. 22: Brown at the market, pp. 66-67 & 81. Spend 300 at 35, 25, 16. (Cows, sheep, pigs.) This has (5, 2) solutions, he gives the positive ones.

Prob. 32: A postage puzzle, pp. 69 & 82. Spend 2s (= 24d) on 2d and 4½d stamps. (2, 1) solutions, he gives the positive one.

McKay. Party Night. 1940. No. 24, pp. 181-182. 6 for 6 at 2, 1, ½. (Men, women, children eating loaves of bread.) Gives (1, 1) of the (3, 1) solutions.

Sid G. Hedges. The Book of Stunts & Tricks. Allenson & Co., London, nd [c1950?]. Shilling change, p. 45. Change a shilling into 12 coins without using pennies, i.e. 12 for 12 at 6, 3, ½, ¼. (2, 1) solutions -- he gives (1, 1).

The Little Puzzle Book. Op. cit. in 5.D.5. 1955. This has a number of examples which I include as illustrating mid 20C usage.

P. 6: Farm deal. 100 for 100 at 10, 5, ½. (Cows, hogs, chickens.) (1, 1) solutions, which he gives. = Alcuin 5 = AR 119.

P. 19: Christmas savings. 100 coins make 500 cents, using 50, 10, 1. (1, 1) solutions, which he gives.

Pp. 25-26: Arithmetic ability 1, 2, 3. 6 coins make 48, 52, 23 cents, using 25, 10, 5, 1. There are (1, 0), (1, 1), (1, 0) answers, which he gives.

P. 41: Buying stamps. 19 for 50 at 1, 2, 3, with the condition that there be more 1s than 2s. (4, 3) answers, of which (1, 1) satisfies the condition and he gives it.

Ripley's Puzzles and Games. 1966.

Pp. 16-17, item 8. Change a dollar into 50 coins, i.e. 50 for 100 at 1, 5, 10, 25, 50. (The use of a dollar is obviously impossible.) (2, 0) solutions, both with no 50s. Only the solution with a 25 is given. Cf Depew, p. 211. = Scott, pp. 129 130.

P. 23. Chickens and sheep have 24 heads and 76 feet, i.e. 24 for 76 at 2, 4.

[Henry] Joseph & Lenore Scott. Master Mind Brain Teasers. 1973. Op. cit. in 5.E.

Coin-counting, pp. 105-106. 100 for 500 at 1, 10, 25, 50. (Coins.) There are (9, 8) solutions -- only the one with a zero is given.

Change of a dollar, pp. 129-130. 50 for 100 at 1, 5, 10, 25, 50. As in Ripley's. Cf Depew, p. 211.

Shakuntala Devi. Puzzles to Puzzle You. Op. cit. in 5.D.1. 1976. Prob. 143: The farmer and the animals, pp. 88 & 134. Buy animals at 50, 40, 25, 10 (mules, sheep, goats, pigs) to produce an average value of 30. This is essentially an alligation problem as discussed under Fibonacci. She gives one answer: 1, 1, 2, 1 and says "Other answers are possible" -- somewhat of an understatement since it has a three parameter set of solutions and two of the parameters can range to infinity!

Michael Holt. Math Puzzles and Games. Walker Publishing Co., NY, (1977), PB ed., 1983. Hundred dollars for five, pp. 37-38 & 101-102. 10 for 500 at 10, 25, 50 -- making change, but requiring each type of coin to be used. (1, 0) answers, hence impossible if each type of coin must be used.

Liz Allen. Brain Sharpeners. Op. cit. in 5.B. 1991. Takeaway pay, pp. 83 & 133. Nine employees of three types, earning £5.00, £3.75 and £1.35 per hour earn £333.60 in a shift of a whole number of hours. How long was the shift? This gives us x + y + z  =  9, 500x + 375y + 135z = 33360/n, where n is the number of hours in a shift. In the problem, x is given as 1, but this information is not needed -- I have used this generalization for one of my problems.

Tom Bullimore. Sherlock Holmes Puzzles. (Originally: Baker Street Puzzles; Ravette; ©1992 with Knight Features.) Orient Paperbacks (Vision Books), New Delhi. India, 1998. No. 34, PP. 38 & 125. 2000 for 7500 at 3, 4, 5. (Goblet, candlesticks, figurines.) This would have (751, 749) answers, but he states that the sum of two of the numbers sold must be 506, which leads to just one solution. [Question: can you find values for the sum of two of the numbers which give two or three solutions?]

G. F. The crash. Mathematical Pie, 129 (Summer 1993) 1022 & Notes, p. 1. Determinate version involving vehicles having 2, 4, 8 wheels (motorcycles, cars, lorries), giving m + c + l = 11, 2m + 4c + 8l  = 44, m = 4. Omitting the last equation would give us 11 for 44 at (2, 4, 8), which has (4, 3) solutions.

David Singmaster. The hundred fowls, or how to count your chickens. Accepted by Mathematics Review (Univ. of Warwick) for 1994, but it closed before the article was published. General survey of the history.

J. Williams. Mathematics and the alloying of coinage 1202-1700. Annals of Science 52 (1995) 213-234 & 235-263. ??NYS -- abstracted in BSHM Newsletter 29 (Summer 1995) 42 -- o/o. Surveys the problem from Fibonacci through Kersey, etc. in the 17C.

Vladimir Dubrovsky. Brainteaser B161 - Two-legged, three legged, and four legged. Quantum 6:3 (Jan/Feb 1996) 15 & 48. Room contains a number of people sitting on three-legged stools and four-legged chairs. There are no spare seats and the total number of legs is 39. This gives x = y + z, 2x + 3y + 4z = 39.

7.P.2. CHINESE REMAINDER THEOREM
See Tropfke 636.

There are two forms of this. The ancient Indians describe them as the residual pulveriser, where one is given the residues to several moduli, and the non-residual pulveriser, where one has ax - c  0 (mod b) which is ax - by = c. The residual form is the classic Chinese Remainder Theorem, whose solution is generally found by reducing to the non-residual form, solved by the Euclidean algorithm.

Notation. Multiple congruences are written in an abbreviated notation. E.g. n    1 (mod 2) and n  2 (mod 3) is written n  1 (2), 2 (3) or even more abbreviatedly as n  -1 (2, 3).

Standard problem types.

A k. n  1 (2, 3, 4, 5, ..., k 1), 0 (k).

A-5. See: Tartaglia; Baker; Dilworth; Jackson.

A-7. See: Bhaskara I; Ibn al-Haitam; Fibonacci; AR; Benedetto da Firenze;

della Francesca; Chuquet; HB.XI.22; Pacioli; Tagliente; Cardan; Tartaglia;

Buteo; Baker; van Etten; Ozanam, 1725; Vyse; Dodson; D. Adams, 1801;

Badcock; New Sphinx; Magician's Own Book; Wehman.

Solution is 301 + 420k, but early examples give just 721.

A-10. See: Pacioli.

A-23. See: Pacioli.

B-k. n  0 (2, 3, 4, ..., k).

B-9. See: Euler; Bonnycastle 1782; Jackson.

B-10. See: Ripley's.

C-k. n  -1 (2, 3, ..., k).

C-5. See: Mahavira.

C-6. See: Ladies' Diary, 1748; Vyse; Bonnycastle 1782.

C-9. See: Tartaglia; W. Leybourn; Carlile.

C-10. See: Pseudo-dell'Abbaco; Muscarello; Ripley's.

C-20. See: Gentlemen's Diary, 1747; Vyse.

C. n   1 (3, 4, 5, 6). See: Brahmagupta; Bhaskara I ??; Bhaskara II.

D-k. n   1 (2, 3, 4, 5, ..., k 1), 0 (k).

D-5. See: Baker; Illustrated Boy's Own Treasury.

D-7. See: Fibonacci; Marliani; Benedetto da Firenze; Pacioli; Ghaligai; Cardan; Tartaglia;

Buteo; Baker; van Etten; Ozanam-Montucla; Dodson.

D-9. See: Pacioli.

D-11. See: Pacioli.

D-23. See: Pacioli.

E. General result for 3, 5, 7. See: Sun Zi; Fibonacci; Yang Hui; AR; Pacioli;

Tartaglia.

F. General result for 5, 7, 9. See: Fibonacci; Pacioli.

Cases with for moduli 28, 19, 15 arise in computing the Julian year -- see: Simpson; Dodson; Bonnycastle, 1782; Todhunter.

I have a separate index of problems.
Sun Zi (= Sun Tzu). Sun Zi Suan Ching (Master Sun's Arithmetical Manual). 4C. [This is not the famous general and writer of The Art of War, c-4C.] Chap. 3, prob. 26, p. 10b: There is an unknown number of things. ??NYS. n  2 (3), 3 (5), 2 (7) & problem E. Only the least answer is given. (See Needham, pp. 34 & 119. English in Needham 119, Mikami 32 and Li & Du 93; Chinese and English in Libbrecht 269.)

The problem has been transmitted as a folk rhyme in China and Japan. It is known as Sun Zi Ge (The Song of Master Sun) or Han Xin Dian Bin (General Han Xin's Method of Counting Soldiers). (Han Xin was a general of c 200.) The rhyme is cryptic but gives the three multipliers 70, 21, 15 for problem E. An English version of a 1592 version of the rhyme and of Sun Zi's text is in: Li Wenlin and Yuan Xiangdong; The Chinese Remainder Theorem, pp. 79 110 of Ancient China's Technology and Science, op. cit. in 6.AN. Li & Yuan also note that such problems arose and were undoubtedly solved in calendrical calculations in the 3C.

Li & Du, pp. 93 94, discuss several Chinese versions over the next centuries, including the rhyme of Li & Yuan. Li & Du's p. 94 mentions the calculation of the Da Ming Calendar by Zu Chongzhi in 462 which probably used 11 simultaneous congruences, but the method has not survived. (Li & Yuan say it was 10 congruences.)

Aryabhata. 499. Chap. II, v. 32 33, pp. 74-84. (Clark edition: pp. 42 50.) Rule for the residual form, i.e. the Chinese Remainder Theorem. The text is rather brief, but Shukla makes it clear that it is giving the Euclidean algorithm for the problem with two residues. Shukla does an example with three residues and gives the general solution, though the text stops with one solution. Shukla gives an alternative translation which would apply to the non-residual form of the problem and notes that later writers recognised the relation between the two forms. (See Libbrecht 229, Datta & Singh II 87 99 & 131 133 and Bag, op. cit. under Bakhshali MS in 7.P.1, pp. 193 204.)

Brahmagupta. Brahma sphuta siddhanta. 628. Chap. XVIII, sect. 1, art. 7. In Colebrooke, pp. 326 327. After some astronomical data, he gives Problem C as an example.

The earlier part of Section 1 (pp. 325-326) deals with the general rule and the later part (pp. 327-338) gives astronomical examples.

Bhaskara I. Mahā Bhāskarīya. c629. Edited and translated by Kripa Shankar Shukla. Lucknow Univ., 1960. Chap 1, v. 41 52, Sanskrit pages 7-9; English pages 29 46. These deal with the non-residual 'pulveriser' in its astronomical applications and it seems clearly illustrated. Illustrative examples are provided by Shukla, from other works of Bhaskara, or from Chap 8 of stated, but not worked, examples to this work, e.g. 44789760000 x   101  = 210389 y (chap. 8, no. 13).

Bhaskara I. 629. Commentary to Aryabhata, chap. II, v. 32-33. Sanskrit is on pp. 132-171; English version of the examples is on pp. 309-332. Some further applications are discussed on pp. 191-196, 199-201, 332-334. Bhaskara I gives 26 examples (and four further examples). I will just give the simpler ones. Shukla, pp. lxxxi-lxxxii, says Bhaskara I was the first to distinguish the residual and non-residual forms of the problem. He also gives tables of solutions of ax - 1 = by for values of a, b of astronomical significance -- Shukla gives these in Appendix II, pp. 335-339. Shukla asserts that the Indians were the first to find the general solution for the Chinese Remainder Problem and it was transmitted to China, c700. However, see Li & Du above.

Ex. 1: n  1 (5), 2 (7).

Ex. 2: n  5 (12), 7 (31).

Ex. 3: n    1 (7), 5 (8), 4 (9).

Ex. 4: A-7. First appearance; see beginning of section for list of later appearances. Answer: 721.

Ex. 5: 8x + 6  0 (13).

Ex. 6: 11x - 3  0 (23).

Ex. 7: 576x - 86688  0 (210389).

All the later examples are similar, arising from astronomical calculations.

(Bag, loc. cit., cites Examples 2 and 4 above and says C occurs, but it is not here. Datta & Singh may imply that C occurs here. Cf Brahmagupta.) (See Libbrecht 231 232 and Datta & Singh II 133 135.)

Bhaskara I. Laghu Bhāskarīya. c629. Edited and translated by Kripa Shankar Shukla. Lucknow Univ., 1963. Chap 8, v. 17-18, Sanskrit pages 26-27; English pages 99 102. This is a simplified version of his earlier Mahā Bhāskarīya, so it does not deal with the pulveriser, but these verses give some astronomical problems with number theoretic conditions which lead to uses of the pulveriser, e.g. 36641x - 24  0 (394479375).

Mahavira. 850. Chap. VI, v. 121 129, pp. 122 123. 6 simple and 3 more complex examples, e.g. the following.