A102508 Suppose there are equally spaced chairs around a round table. Then a(n) is the maximal number of chairs for which there exists a seating arrangement of n people around the table such that if a waiter puts two glasses (randomly) on the table in front of two (different) chairs, it is always possible to turn the table so that the two glasses end up in front of two seated persons.

1, 3, 7, 13, 21, 31, 39, 57, 73, 91, 95, 133

Offset: 1

Author

Ard Van Moer (ard.van.moer(AT)vub.ac.be), Mar 15 2005

Keywords

• nonn
• more
• hard

Comments

a(n) <= n(n-1)+1. Moreover, a(n)=n(n-1)+1 iff A058241(n)>0, i.e., when a perfect difference set modulo n(n-1)+1 exists. In particular, a(12) = 133, a(14)=183, a(17)=273, etc.

This problem is a circular analog of an optimal ruler problem; see A004137. - David Wasserman, Apr 15 2008

Solutions do not always exist for table sizes less than a(n). For example, for n = 5 there is no solution for a table of size 20. - David Wasserman, Apr 15 2008

Equivalently, largest value of S such that in some cyclic array of positive integers of length n, every positive integer <= S is the sum of consecutive terms. For example, the numbers 1..21 can be written as the sum of consecutive terms in the cyclic array [10,3,1,5,2]. So a(5) = 21. - Phil Scovis, Jan 29 2016

If there exists a ruler of length L and n marks, then it can be trivially transformed to a ruler of length L and n+1 marks, by simply dividing one of the segments into two. In other words, a(n+1) >= a(n). - Dmitry Kamenetsky, Aug 02 2025

a(14)=183, a(17)=273, a(18)=307, a(20)=381, a(24)=553 and so on. See Dan Gordon's site in links. - Dmitry Kamenetsky, Aug 02 2025

a(16) >= 195, since every length from 1 to 195 can be generated with the cyclic ruler [3,14,2,5,29,1,4,66,6,9,11,1,1,10,8,25]. - Dmitry Kamenetsky, Aug 02 2025

Examples

			a(5)=21 because if we have 21 chairs, 5 persons can sit down on chairs 1, 4, 5, 10 and 12. 1 == 5-4 (mod 21). 2 == 12-10 (mod 21). 3 == 4-1 (mod 21). 4 == 5-1 (mod 21). 5 == 10-5 (mod 21). 6 == 10-4 (mod 21). 7 == 12-5 (mod 21). 8 == 12-4 (mod 21). 9 == 10-1 (mod 21). 10 == 1-12 (mod 21). It is impossible to do the same with 22 or more chairs.
		

Links

• Dan Gordon, Difference Sets
• Don Reble, C++ Program

Crossrefs

Cf. A004137, A058241.

Extensions

3 more terms from David Wasserman, Apr 15 2008

Edited by Max Alekseyev, Apr 29 2010, Mar 01 2015

a(11) = 95 from Don Reble, Feb 25 2015. - N. J. A. Sloane, Mar 01 2015

a(12) from Max Alekseyev, Mar 01 2015