Seating Arrangements (new puzzle)

At a certain series of dinner parties m people must sit in n chairs around a circular table; you are to lay the table for them. The m people, when taken 2 at a time, form C(2,m) pairs. You are given a description of the place-setting arrangements in lists similar to the following:

X X _ X X _ X _ _ _ _

(As it reads around the table. X represents a filled chair, and _ an empty one.)

What exactly are the requirements of a list? How about 1 chair, one person, and a list consisting of all zeros? (obviously, there is only one place setting, so there can be no more than one solution. Also, there are no pairs, so there cannot be any item in the list with a non-zero) I find the directions ambiguous.

:> 2 pairs whose members are seated next to one another :> 2 pairs whose members are separated by one chair :> 3 pairs whose members are separated by two chairs :> 1 pair whose members are separated by 3 chairs :> 2 pairs whose members are separated by 4 chairs :> [snip correct solution of warm-up problem] :> :> (Easy): There is only one solution, up to rotation and reflection of the :> table, to the list in the warm-up problem. Find the smallest m and n such :> that there exists a place-setting list with more than one distinct :> solution.

: What exactly are the requirements of a list? How about 1 chair, one : person, and a list consisting of all zeros? (obviously, there is only : one place setting, so there can be no more than one solution. Also, : there are no pairs, so there cannot be any item in the list with a : non-zero)

'1 chair, 1 person' is a valid list, since all pairs are accounted for, but it doesn't correspond to the question asked, which was to find the smallest m and n such that a list may have

In that case, how about this: X X X _ _ X _ _ X X _ X X _ _ _

where both satisfy the rule {2, 1, 2, 2}. The answer is therefore 4 people and 8 chairs.

I have 104 other solutions, too (accounting for all solutions with no more than 14 chairs). The rest require at least 10 chairs.)

The answer is 15:

X X _ X _ _ X X _ _ X _ and X X _ X _ _ X _ X X _ _ -> {2, 2, 4, 2, 3, 4} X X _ X X _ _ X _ X _ _ and X X _ X _ X X _ _ X _ _ -> {2, 2, 4, 3, 2, 4} X X X _ _ X _ X _ X _ _ and X X _ X _ X _ X X _ _ _ -> {2, 3, 2, 3, 4, 2} X X X _ X _ _ X _ X _ _ and X X _ X _ X X _ X _ _ _ -> {2, 3, 3, 2, 4, 2} X X X _ X _ X _ _ X _ _ and X X _ X X _ X _ X _ _ _ -> {2, 3, 3, 3, 3, 2} X X X _ X _ _ X _ _ X _ and X X _ X X _ X _ _ _ X _ -> {2, 3, 4, 2, 2, 4} X X X _ _ X X _ _ X _ _ and X X _ X X _ _ X X _ _ _ -> {3, 1, 3, 4, 3, 2} X X X _ X _ _ X X _ _ _ and X X X _ _ X X _ X _ _ _ -> {3, 2, 2, 3, 3, 4} X X X X _ _ X _ _ X _ _ and X X _ X X _ X X _ _ _ _ -> {3, 2, 4, 2, 2, 4} X X X X _ _ X _ X _ _ _ and X X X _ X _ X X _ _ _ _ -> {3, 3, 2, 2, 3, 4} X X X X _ X _ _ X _ _ _ and X X X _ X X _ X _ _ _ _ -> {3, 3, 3, 2, 3, 2} X X X X _ X _ _ _ X _ _ and X X X _ X X _ _ _ _ X _ -> {3, 3, 3, 3, 2, 2} X X X X _ _ _ X X _ _ _ and X X X _ _ X X X _ _ _ _ -> {4, 2, 1, 2, 4, 4} X X X X X _ _ _ X _ _ _ and X X X _ X X X _ _ _ _ _ -> {4, 3, 2, 3, 2, 2} X X X X X _ _ X _ _ _ _ and X X X X _ X X _ _ _ _ _ -> {4, 3, 3, 2, 2, 2}

X X _ X _ _ X _ _ _ X _ _ _ _ _ _ _ X X _ _ X _ _ X _ X _ _ _ _ _ _ _ _ X X _ X _ _ _ _ _ _ X _ _ _ _ X _ _

All share this rule: {1, 1, 2, 1, 1, 1, 1, 1, 2}

No other unique placings share this, so that 18 is such a number n. Also, by placing x-1 empty chairs between each of the existing chairs, a configuration with xn chairs is created with 5 people, and the rules are of this form:

{0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, ...} so that the property is preserved. Thus, if any n is found that satisfies this, all xn, for positive integers x, also satisfy this.

X X _ _ X _ _ _ X _ _ _ _ X _ _ _ _ _ _ _ _ _ _ X X _ _ _ X _ _ _ X _ _ X _ _ _ _ _ _ _ _ _ _ _ X X _ _ X _ _ _ _ _ _ _ _ X _ _ _ _ _ _ X _ _ _

Thus, all 24x set of chairs work.

Those are the only configurations I found for n<30. I have already proven the number to be infinite.

: The answer is 15:

[snip] : No other unique placings share this, so that 18 is such a number n. : Also, by placing x-1 empty chairs between each of the existing chairs, : a configuration with xn chairs is created with 5 people, and the rules : are of this form:

: {0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, ...} so that the property is : preserved. Thus, if any n is found that satisfies this, all xn, for : positive integers x, also satisfy this.

: X X _ _ X _ _ _ X _ _ _ _ X _ _ _ _ _ _ _ _ _ _ : X X _ _ _ X _ _ _ X _ _ X _ _ _ _ _ _ _ _ _ _ _ : X X _ _ X _ _ _ _ _ _ _ _ X _ _ _ _ _ _ X _ _ _

: Thus, all 24x set of chairs work.

: Those are the only configurations I found for n<30. I have already : proven the number to be infinite.

Very good - 30 is also such a number; and there are two threesomes:

X _ X _ _ X _ _ _ _ X _ _ _ _ _ _ X _ _ _ _ _ _ _ _ _ _ _ _ X _ X _ _ _ _ X _ _ _ _ X _ _ X _ _ _ _ _ _ _ _ _ _ _ _ _ _ X _ _ X _ X _ _ _ _ X _ _ _ _ _ _ _ X _ _ _ _ _ _ _ _ _ _ _

with rule {0,1,1,0,2,0,1,1,0,1,0,1,1,0,1},

and

X X _ _ _ X _ _ _ _ X _ _ _ _ _ X _ _ _ _ _ _ _ _ _ _ _ _ _ X X _ _ _ _ X _ _ _ _ X _ _ _ X _ _ _ _ _ _ _ _ _ _ _ _ _ _ X _ _ _ X X _ _ _ _ X _ _ _ _ _ _ _ _ X _ _ _ _ _ _ _ _ _ _

with rule {1,0,0,1,2,1,0,0,1,1,1,0,0,1,1}

I suspect there are threesomes for every n = 6a where a is an integer greater or equal to 3... lousy 32-bit machine won't let me check any higher unless I get cleverer though.

: taken 2 at a time, form C(2,m) pairs. You are given a description of the : place-setting arrangements in lists similar to the following:

[snip] :> but it doesn't correspond to the question asked, which was to find the :> smallest m and n such that a list may have

uncle, let your computer rest in piece. My math will do this one:

Consider the rule(s) consiting of these 10 pairs, where n=6i+12 and m=5:

0 i i+1 i+1 i+2 2i+2 2i+3 2i+4 3i+4 3i+5

Next, adjust them to a more meaningful (and additive) measure of distince, measured in distintance between people around the table. In effect, this will be one greater than the number of people between you.

1 i+1 i+2 i+2 i+3 2i+3 2i+4 2i+5 3i+5 3i+6

Now, consider a point A and a point B, separated by 3i+6. Obviously, the distance around both directions is 3i+6.

A (3i+6) B (3i+6)

Next, consider possible locations of point C, noting that AC + CB = AB. The possibilities for AC and CB are: {1, 3i+5} {i+1, 2i+5} {i+2, 2i+4} {i+3, 2i+3}

Note that if a point AC (or C is i+2, no point AD or BD could be i+2, since then both CB and either of AD or BD would have to be 2i+4, but only one pair is 2i+4. Thus, at least one i+2 length occurs between a piar other than one involving A or B. Let this pair be CD.

Noting the symmetry of the AB setup (both sides are identical), there are just three ways to arrange CD with AB.

Case 1: A is between C and D. The only pair that adds up to i+2 is {i, i+1}, so that we have this arrangement: C (1) A (i+1) D (2i+5) B (3i+5) The lengths used are: 1, i+1, 2i+5, 3i+5, i+2, 3i+6 The lengths that remain: i+2, i+3, 2i+3, 2i+4 Because A must be one closer to a point E than C (if it is in the ADB side) or visa versa (if on the ACB side), there are just 4 locations for E:

1. C (1) A (i+1) D (1) E (2i+4) B (3i+5) 2. C (1) A (i+1) D (i+2) E (i+3) B (3i+5) 3. C (1) A (i+1) D (2i+5) B (2i+3) E (i+2) 4. C (1) A (i+1) D (2i+5) B (i+2) E (2i+3)

The first is clearly impossible since only one pair is of length 1.

2. C (1) A (i+1) D (i+2) E (i+3) B (3i+5) 1 i+1 i+2 i+3 3i+5 i+2 2i+3 2i+5 3i+6 This one is valid.

3. C (1) A (i+1) D (2i+5) B (2i+3) E (i+2) 1 i+1 2i+5 2i+3 i+2 i+2 3i+6 2i+4 3i+4 3i+5 This one is valid.

4. C (1) A (i+1) D (2i+5) B (i+2) E (2i+3) This one is not valid because BC = DE = 3i+5

Case one yielded two good solutions. Time for case two:

Case 2 & 3: CD is between AB. There are two ways to arrange this, cases 2 and 3:

Case 2: A (1) C (i+2) D (2i+3) B (3i+6) used: 1 i+2 2i+3 3i+6 i+3 3i+5 left: i+1 i+2 2i+4 2i+5

As before, there are 4 possibilities: 1. A (1) C (i+1) E (1) D (2i+3) B (3i+6) 2. A (1) C (i+2) D (i+2) E (i+2) B (3i+6) 3. A (1) C (i+2) D (2i+3) B (2i+5) E (i+1) 4. A (1) C (i+2) D (2i+3) B (i+2) E (2i+4) The first one isn't possible because AC = ED = 1. The second one is not possible because CD = DE = EB = i+2 The third one is a rotation+reflection of case 1.3

4. A (1) C (i+2) D (2i+3) B (i+2) E (2i+4) CB = DE = 3i+5, so this one does not work either. Thus, case 2 yields NO additional solutions.

Case 3: A (i+1) C (i+2) D (i+3) B (3i+6) used: i+1 i+2 i+3 3i+6 2i+3 2i+5 left: 1 i+2 2i+4 3i+5

Put E a distance of 1 from each of the points in each way, giving 8 cases. 1. A (1) E (i) C (i+2) D (i+3) B (3i+6) 2. A (i) (E) 1 C (i+2) D (i+3) B (3i+6) 3. A (i+1) C (1) E (i+1) D (i+3) B (3i+6) 4. A (i+1) C (i+1) E (1) D (i+3) B (3i+6) 5. A (i+1) C (i+2) D (1) E (i+2) B (3i+6) 6. A (i+1) C (i+2) D (i+2) E (1) B (3i+6) 7. A (i+1) C (i+2) D (i+3) B (1) E (3i+5) 8. A (i+1) C (i+2) D (i+3) B (3i+5) E (1)

1 and 2 are gone because no pair should be i apart. 3 and 4 are gone because no two pairs are i+1 apart. 5 is gone because CE = DB = i+3 7 is gone because DE is i+4 (no pair is that far apart) 8 is a rotation of Case 1.2

That leaves 6:

6. A (i+1) C (i+2) D (i+2) E (1) B (3i+6) i+1 i+2 i+2 1 3i+6 2i+3 2i+4 i+3 3i+5 2i+5 So this is valid.

I conclude the construction with EXACTLY three solutions to this:

C (1) A (i+1) D (i+2) E (i+3) B (3i+5) C (1) A (i+1) D (2i+5) B (2i+3) E (i+2) A (i+1) C (i+2) D (i+2) E (1) B (3i+6)

QED.

Note: this proof is only meaningful if each unique expression has a unique value.

0 i i+1 i+2 2i+2 2i+3 2i+4 3i+4 3i+5 range if i=0: 0 0-2 2-4 4-5

so that the proof does not apply to i=0; range if i=1: 0 1-3 4-6 7-8 so the proof is valid for i=1. The ranges separate even further for higher i. Thus, I conclude that I have constructed a set with exaclty three solutions for every n=6i+12, with i>0.

when i=0: C (1) A (1) D (2) E (3) B (5) C (1) A (1) D (5) B (3) E (2) A (1) C (2) D (2) E (1) B (6)

The first two are reflected/rotated, so that when i=0, only two unique solutions result.