5.S.1. USING CHAIN LINKS TO PAY FOR A ROOM [David Singmaster] The landlord agrees to accept one link per day and the owner wants to minimise the number of links he has to cut. Some weighing problems in 7.L.2.c and 7.L.3 are phrased in terms of making daily payment, but these are like having the chain already in pieces. See the Fibonacci in 7.L.2.c. Standart Answers: - Maximal Chain by Counting Method - By opening n links we get n+1 parts (plus the n open links). There are 2^(n+1) possible subsets of this parts times n+1 ways to add open links which gives the total of (n+1) 2^(n+1) possebilities (including zero). This can be reached by a chain of length (n+1) 2^(n+1) - 1 which is dissected into parts of length (n+1) 2^k with 0<=k<=n. Non Standart Answers: Assume that a chain of length k for every 1<=k<=length(chain) must be doable with the open links. Then you can reach links length dissection 0 1 1 1 5 1-(1)-3 2 13 1-(1)-3-(1)-7 3 29 1-(1)-3-(1)-7-(1)-15 4 61 1-(1)-3-(1)-7-(1)-15-(1)-31 n 2^(n+2)-3 References: E. B. Dynkin, S. A. Molchanov, A. L. Rozental, A. K. Tolpygo; Mathematical Problems: An Anthology (Revised english edition by Richard A. Silverman) Gordon and Breach, New York, 1967 Prob. 5: A six link open-ended bracelet to pay for a room Rupert T. Gould. The Stargazer Talks. Geoffrey Bles, London, 1944. A Few Puzzles _ write up of a BBC talk on 10 Jan 1939, pp. 106-113. 63 link chain with three cuts. On p. 106, he says he believes it is quite modern _ he first heard it in 1935. On p. 113, he adds a postscript that he now believes it first appeared in John O'London's Weekly (16 Mar 1935) ??NYS. Birtwistle. Math. Puzzles & Perplexities. 1971. Pp. 13-16. Begins with seven link open-ended bracelet. Then how big a bracelet can be dealt with using only two cuts? Gets 23. Then does general case, getting n + (n+1)(2^(n+1) - 1). Angela Fox Dunn; Second Book of Mathematical Bafflers. Dover, 1983. [Selected from Litton's Problematical Recreations, which appeared in 1959-1971.] Prob. 26, pp. 28 & 176. 23 link case. Jim Howson; The Computer Weekly Book of Puzzlers. Computer Weekly Publications, Sutton, Surrey, 1988, unpaginated. [The material comes from his column which started in 1966.] Prob. 30. Says a 23 link chain need only be cut twice, giving lengths 1, 1, 3, 6, 12, which make all values up to 23. Asks for three cuts in a 63 link chain and the maximum length chain one can deal with in n cuts. Martin Gardner; M. Gardner's Sixth Book of Mathematical Games from Scientific American, Freeman (1971) San Francisco - 6.4 Gold Links (n-link chain) general case: (n+1) 2^(n+1) - 1 Heinz Haber (Editor); Das Mathematische Kabinett, dva, Stuttgart, 1967, (paperback: Das Mathematische Kabinett Folge 1, dtv 904, 1973, ISBN 3-423-00904-7) (paperback: Das Mathematische Kabinett, dtv 10121, 1983, ISBN 3-423-10121-0 (selection of 1 and 2)) Bild der Wissenschaft (Math. Kabinett) (Maerz 1966) p241 Problem Bild der Wissenschaft (Math. Kabinett) (April 1966) p326 Solution - (1967, Problem 7: p93 and p109-110, Figure 119. The 23 link chain) nonstandart answer 3 links: 1-(1)-2-(1)-5-(1)-12 it is assumed that one chain with 1<=k<=23 links can be formed. - (1973, Problem 7: p112 and p132, Figure 119, The 23 link chain) - (1983, Problem 30: p110 and p134, Figure 128, The 23 link chain) standart answer 2 links: 3-(1)-6-(1)-12 David Singmaster; Sources in Recreational Mathematics, An Annotated Bibliography, 7th Pre. Ed., Oct. 1999 Part II, Sect. 5.S.1. USING CHAIN LINKS TO PAY FOR A ROOM Rec.Puzzles.Archive ==> logic/chain.p <== The 21 link case. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ==> logic/chain.p <== What is the least number of links you can cut in a chain of 21 links to be able to give someone all possible number of links up to 21? ==> logic/chain.s <== Two. OOO C OOOOO C OOOOOOOOOOO (where Os are chained unbroken links, and the Cs are the unchained broken links) And equivalently: OOO C OOOOOO C OOOOOOOOOO -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de