Sources page biographical material

5.C.1 RANKING COINS WITH A BALANCE
If one weighs only one coin against another, this is the problem of sorting except that we don't actually put the objects in order. If one weighs pairs, etc., this is a more complex problem.
J. Schreier. Mathesis Polska 7 (1932) 154 160. ??NYS -- cited by Steinhaus.

Hugo Steinhaus. Mathematical Snapshots. Not in Stechert, NY, 1938, ed. OUP, NY: 1950: pp. 36 40 & 258; 1960: pp. 51 55 & 322; 1969 (1983): pp. 53 56 & 300. Shows n objects can be ranked in M(n) = 1 + kn   2^k steps where k = 1 + [log₂ n]. Gets M(5) = 8.

Lester R. Ford Jr. & Selmer M. Johnson. A tournament problem. AMM 66:5 (May 1959) 387 389. Note that log₂ n! = L(n) is a lower bound from information theory. Obtain a better upper bound than Steinhaus, denoted U(n), which is too complex to state here. For convenience, I give the table of these values here.
n 1 2 3 4 5 6 7 8 9 10 11 12 13

M(n) 0 1 3 5 8 11 14 17 21 25 29 33 37

U(n) 0 1 3 5 7 10 13 16 19 22 26 30 34

L(n) 0 1 3 5 7 10 13 16 19 22 26 29 33

U(n) = L(n) also holds at n = 20 and 21.
Roland Sprague. Unterhaltsame Mathematik. Op. cit. in 4.A.1. 1961. Prob. 22: Ein noch ungelöstes Problem, pp. 16 & 42 43. (= A still unsolved problem, pp. 17 & 48 49.) Sketches Steinhaus's method, then does 5 objects in 7 steps. Gives the lower bound L(n) and says the case n = 12 is still unsolved.

Kobon Fujimura, proposer; editorial comment. Another balance scale problem. RMM 10 (Aug 1962) 34 & 11 (Oct 1962) 42. Eight coins of different weights and a balance. How many weighings are needed to rank the coins? In No. 11, it says the solution will appear in No. 13, but it doesn't appear there or in the last issue, No. 14. It also doesn't appear in the proposer's Tokyo Puzzles.

Howard P. Dinesman. Superior Mathematical Puzzles. Op. cit. in 5.B.1. 1968. No. 6: In the balance, pp. 18 & 85-86. Rank five balls in order in seven weighings.

John Cameron. Establishing a pecking order. MG 55 (No. 394) (Dec 1971) 391 395. Reduces Steinhaus's M(n) by 1 for n  5, but this is not as good as Ford & Johnson.

W. Antony Broomhead. Letter: Progress in congress? MG 56 (No. 398) (Dec 1972) 331. Comments on Cameron's article and says Cameron can be improved. States the values U(9) and U(10), but says he doesn't know how to do 9 in 19 steps. Cites Sprague for numerical values, but these don't appear in Sprague -- so Broomhead presumably computed L(9) and L(10). He gets 10 in 23 steps, which is better than Cameron.

Stanley Collings. Letter: More progress in congress. MG 57 (No. 401) (Oct 1973) 212 213. Notes the ambiguity in Broomhead's reference to Sprague. Improves Cameron by 1 (or more??) for n  10, but still not as good as Ford & Johnson.

L. J. Upton, proposer; Leroy J. Myers, solver. Problem 1138. CM 12 (1986) 79 & 13 (1987) 230 231. Rank coins weighing 1, 2, 3, 4 with a balance in four weighings.