From: Robin Chapman Subject: Re: Number Arrangement Puzzle Date: Fri, 03 Sep 1999 07:19:37 GMT Newsgroups: rec.puzzles,sci.math Keywords: Langford problem In article <7qnaoc$fdv$1@news.fas.harvard.edu>, Noam D. Elkies wrote: > In article <37cee69f.112655039@news.apk.net>, > Parallax wrote: > >On Thu, 2 Sep 1999 21:16:38 +0100, "Dave Moore" > > wrote: > > >>Given two sets of the numbers 1 to 7 inclusive, the puzzle is to arrange > >>them in sequence so that there is one number between the two 1's, > >>two numbers between the two 2's, three numbers between the two 3's, > >>.... and so on, ending with seven numbers between the two 7's. > > >>Here is a solution to a similar problem using two sets of the > >>numbers 1 to 3 inclusive: > > >>3 1 2 1 3 2 > > >>Try also with two sets of the numbers 1 to n, where n=4, 5, 6 > > Why stop there? > > [spoilers for n=4,7 deleted] > > >5-set = I can't figure it out. > >6-set = Again, can't quite get it. > > n=5 and n=6 can't be done. Consider 5 for instance. There are 10 > available positions, 5 even and 5 odd. The 2's and 4's must occupy > positions of opposite parity, and the 1's, 3's and 5's positions > of the same parity. This makes it impossible to balance the even > and odd positions. Another (ultimately equivalent) way of seeing > this: we want {1,2,3,4,5,6,7,8,9,10} to be a permutation of > {a,a+2,b,b+3,c,c+4,d,d+5,e,e+6} for some a,b,c,d,e; but then > the sum 55 is 2(a+b+c+d+e)+20, which must be even -- contradiction. > > ObPuzzle: Which values of n are excluded by this argument? > > I find this problem in Martin Gardner's _Mathematical Magic Show_ > (Knopf, 1977; Vintage, 1978), page 70, where it is attributed to > "C.Dudley Langford, a Scottish mathematician, [who] was watching his > little boy play with colored blocks." On p.77 Gardner gives a > reference to _The Mathematical Gazette_ Vol.42 (Oct.1958), p.228, > and cites further discussion in the Dec.1959 issue of the same > journal. The solution for n=4 is unique up to reversals; for n=7 > there are 26 (Gardner, citing the Feb.71 Gazette). Computers have > naturally pushed the enumeration further. It is not clear to me > from the discussion whether it has been proved that the problem > can be solved for every n not excluded by the parity argument. John Miller has a web page on the Langford problem at http://www.lclark.edu/~miller/langford/langford-biblio.html He does assert that the parity condition on the n is necessary and suffient for there to be a solution, but it isn't clear to me in which item of his extensive bibliography a proof might be found. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "They did not have proper palms at home in Exeter." Peter Carey, _Oscar and Lucinda_ Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.