Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!lambert
From: lambert@cwi.nl (Lambert Meertens)
Newsgroups: comp.ai
Subject: Re: Circular distance - partial answer
Summary: Formula is incorrect
Message-ID: <7946@boring.cwi.nl>
Date: 9 Mar 89 19:43:41 GMT
References: <18088@iuvax.cs.indiana.edu> <1268@wasatch.UUCP>
Sender: news@cwi.nl
Distribution: sci.math, rec.puzzles
Organization: CWI, Amsterdam
Lines: 19

) I think that F(n,k) = [n/(2^k)]
)   ([i] means smallest integer greater than or equal to i)

) 					F(n,k)
) 	n	k	2^k	n/2^k	[n/2^k]
) 	8	3	8	1	1

In a ring an element has (at most) two immediate neighbours.  If it
participates in 3 rings, it together has at most 6 immediate neighbours.
So at most 7 (counting the element itself) are within distance 1.
Conclusion: if F(n,3) = 1, then n <= 7.

Generalizing this argument to F(n,k) = d, we have n <= 2kd+1.

Hence F(n,k) >= (n-1)/(2k).

-- 

--Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl