1
$\begingroup$

The problem that this applies to is difficult to explain (for me), which may account for a lot of why I cannot solve it. The example below should highlight the process for which I want to come up with a function or conditional expression:

  1. X people sit at a table with N seats (X = N). This is iteration 0 or position 1.
  2. Everyone gets up and changes seats. This is iteration 1 and creates position 2.
  3. A period of time goes by and then, again, everyone changes seats,BUT they cannot replace seats with the same person as last time (e.g., if I went and sat where Tim was sitting for the first iteration, I CANNOT go sit where Tim was just sitting again; I can only follow Tim 1x) AND they cannot return to a seat in which they have already sat. This is iteration 2 and creates position 3.
  4. This continues until all X people have sat in all N seats without ever sitting in the same seat twice or replacing the same person twice.

I have been able to solve for particular N/X's, but then fail to have a formula that generalizes to others. Here is an example of a 4-person solution: This is a 4 person solution Here is the formula from Google Sheets: These are the formulae

  1. Identified each person w/ number that corresponds to original position.
  2. Added subsequent iteration number to that person's number (which corresponds to their original position)
  3. If the sum of the person's ID and the subsequent iteration > # of people (4), subtract the sum by 4.

This formula solved the problem for 4 people:

  • no one is in a position more than once
  • no one replaced the same person more than once
  • everyone sat in every position.

The formula (shown in the second image), however, failed to work for X = 5 and X = 6.

THE GOAL: Create a formula that generalizes across all/most/positive values of X, people.

$\endgroup$
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it does not appear to be related to puzzles. $\endgroup$ – Deusovi Jun 4 '16 at 22:08
  • $\begingroup$ @Deusovi ah, but understandable. Where should I put it? I am looking to uncover a pattern. It has some family resemblance to a puzzle, right? $\endgroup$ – Derek DeBellis Jun 4 '16 at 22:13
  • 2
    $\begingroup$ It doesn't need to be closed; all it would take is some rephrasing so that it is presented in the format of a puzzle, and then add the open-ended tag to indicate that a better answer may exist than the one you have. $\endgroup$ – Bulldogg6404 Jun 5 '16 at 1:12
  • $\begingroup$ In (5.) do pairs of people swap seats, or do the set of $N$ people permute? Should (6.) read "This continues until everyone has added to all of the original notes."? Are you counting how many steps it takes for $N$ people or the number of ways to complete successfully for $N$ people? FYI: see derangement as it may well be relevant. $\endgroup$ – Jonathan Allan Jun 5 '16 at 5:17
  • 1
    $\begingroup$ Are you aware of Latin squares? I feel that there may be a way to translate this problem into finding a Latin square, Also this might be better suited to one of the mathematics boards on stack exchange. $\endgroup$ – Jasen Jun 5 '16 at 8:50
1
$\begingroup$

Note: I do hope I have not wasted my time with a misunderstanding of "they cannot replace seats with the same person as last time" - I interpreted that as "If Susan took Tim's seat last time, she cannot do so this time (but could next time)". See the end of the post for some results in the strict case.


I am not sure of an efficient algorithm to validate $N$ and yield a solution if one exists, but we can implement a naive algorithm that tries to find them, and also inspect the cases for small $N$.

A valid seating plan is a list of seating arrangements that adheres to your rules (much like the list of rows in your example).

Since everyone must sit in each seat exactly once a valid seating plan contains $N$ seating arrangements that, when arranged vertically, form a Latin square.

The rules then stipulate that a subset of such seating plans are valid (due to the no-following the same person rule described in your (3.)).

I count the number of valid plans produced by permuting Latin squares (my code does not enumerate fully reduced forms, so I then take a factor of $(N-1)!$ out from the sums in the equations below to put them back in line with reduced form).

$N=2$ has $1$ reduced form and yields $1!(1\times 2)=2$ seating plans.
This may be obvious but here they are:

((1,2), (2,1))

((2,1), (1,2))

$N=3$ has $1$ reduced form and yields $2!(1\times 0)=0$ seating plans
(we would need to make two seating changes, our options are limited to a cycle by $1$ seat or by $2$ seats since no one may remain in the same seat, however we must use both cycles so rule(3.) is not broken, but that would mean the second change would move everyone back to their original seats, breaking rule (4.))

$N=4$ has $4$ reduced forms and yields $3!(1\times 24+3\times 16)=432$ seating plans
(note that $1$ of the reduced forms yields $3!\times 24$ and the other $3$ yield $3!\times 16$)

$N=5$ has $56$ reduced forms and yields $4!(50\times 0+6\times 40)=5760$ seating plans, one is:

((1,2,3,4,5), (2,3,4,5,1), (4,5,1,2,3), (3,4,5,1,2), (5,1,2,3,4))

which follows the same scheme as your example, but swaps two of the arrangements (the third and fourth ones).

For $N=6$ the code will probably take too long to count them all (since it would naively check $\binom{6!}{6}=189492294437160$ combinations to find the Latin squares to permute).
However, if we just permute the Latin square your method would try we find this one first:

((1,2,3,4,5,6), (2,3,4,5,6,1), (4,5,6,1,2,3), (3,4,5,6,1,2), (5,6,1,2,3,4), (6,1,2,3,4,5))

If we do the same for larger $N$ we quickly find results $N<13$ and in a short time for $N=13$:

((1,2,3,4,5,6,7), (2,3,4,5,6,7,1),(4,5,6,7,1,2,3), (3,4,5,6,7,1,2), (6,7,1,2,3,4,5), (5,6,7,1,2,3,4), (7,1,2,3,4,5,6))

((1,2,3,4,5,6,7,8), (2,3,4,5,6,7,8,1), (4,5,6,7,8,1,2,3), (3,4,5,6,7,8,1,2), (5,6,7,8,1,2,3,4), (6,7,8,1,2,3,4,5), (8,1,2,3,4,5,6,7), (7,8,1,2,3,4,5,6))

((1,2,3,4,5,6,7,8,9), (2,3,4,5,6,7,8,9,1), (4,5,6,7,8,9,1,2,3), (3,4,5,6,7,8,9,1,2), (5,6,7,8,9,1,2,3,4), (6,7,8,9,1,2,3,4,5), (8,9,1,2,3,4,5,6,7), (7,8,9,1,2,3,4,5,6), (9,1,2,3,4,5,6,7,8))

((1,2,3,4,5,6,7,8,9,10), (2,3,4,5,6,7,8,9,10,1), (4,5,6,7,8,9,10,1,2,3), (3,4,5,6,7,8,9,10,1,2), (5,6,7,8,9,10,1,2,3,4), (6,7,8,9,10,1,2,3,4,5), (8,9,10,1,2,3,4,5,6,7), (7,8,9,10,1,2,3,4,5,6), (9,10,1,2,3,4,5,6,7,8), (10,1,2,3,4,5,6,7,8,9))

((1,2,3,4,5,6,7,8,9,10,11), (2,3,4,5,6,7,8,9,10,11,1), (4,5,6,7,8,9,10,11,1,2,3), (3,4,5,6,7,8,9,10,11,1,2), (5,6,7,8,9,10,11,1,2,3,4), (6,7,8,9,10,11,1,2,3,4,5), (8,9,10,11,1,2,3,4,5,6,7), (7,8,9,10,11,1,2,3,4,5,6), (10,11,1,2,3,4,5,6,7,8,9), (9,10,11,1,2,3,4,5,6,7,8), (11,1,2,3,4,5,6,7,8,9,10))

((1,2,3,4,5,6,7,8,9,10,11,12), (2,3,4,5,6,7,8,9,10,11,12,1), (4,5,6,7,8,9,10,11,12,1,2,3), (3,4,5,6,7,8,9,10,11,12,1,2), (5,6,7,8,9,10,11,12,1,2,3,4), (6,7,8,9,10,11,12,1,2,3,4,5), (8,9,10,11,12,1,2,3,4,5,6,7), (7,8,9,10,11,12,1,2,3,4,5,6), (9,10,11,12,1,2,3,4,5,6,7,8), (10,11,12,1,2,3,4,5,6,7,8,9), (12,1,2,3,4,5,6,7,8,9,10,11), (11,12,1,2,3,4,5,6,7,8,9,10))

((1,2,3,4,5,6,7,8,9,10,11,12,13), (2,3,4,5,6,7,8,9,10,11,12,13,1), (4,5,6,7,8,9,10,11,12,13,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,1,2), (5,6,7,8,9,10,11,12,13,1,2,3,4), (6,7,8,9,10,11,12,13,1,2,3,4,5), (8,9,10,11,12,13,1,2,3,4,5,6,7), (7,8,9,10,11,12,13,1,2,3,4,5,6), (9,10,11,12,13,1,2,3,4,5,6,7,8), (10,11,12,13,1,2,3,4,5,6,7,8,9), (12,13,1,2,3,4,5,6,7,8,9,10,11), (11,12,13,1,2,3,4,5,6,7,8,9,10), (13,1,2,3,4,5,6,7,8,9,10,11,12))

but at $N=14$ it will need to check $87178291200$ permutations to confirm that there are none, I thought this would be too many to bother with.

I noted however that the number of permutations checked before the first was found looks suspiciously like $(N-3)!$:

                        N : 4, 5, 6,  7,   8,   9,   10,    11,     12,      13
                   (N-3)! : 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 
tested before first yield : 1, 2, 6, 26, 121, 722, 5046, 40346, 363001, 3629522

So a back of the envelope calculation was that it would take about 14 times as long as it did for $N=13$,

Sure enough after $15$ minutes and going through $39921846\approx 11!$ invalid permutations it returned this result for $N=14$:

((1,2,3,4,5,6,7,8,9,10,11,12,13,14), (2,3,4,5,6,7,8,9,10,11,12,13,14,1), (4,5,6,7,8,9,10,11,12,13,14,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,14,1,2), (5,6,7,8,9,10,11,12,13,14,1,2,3,4), (6,7,8,9,10,11,12,13,14,1,2,3,4,5), (8,9,10,11,12,13,14,1,2,3,4,5,6,7), (7,8,9,10,11,12,13,14,1,2,3,4,5,6), (9,10,11,12,13,14,1,2,3,4,5,6,7,8), (10,11,12,13,14,1,2,3,4,5,6,7,8,9), (12,13,14,1,2,3,4,5,6,7,8,9,10,11), (11,12,13,14,1,2,3,4,5,6,7,8,9,10), (13,14,1,2,3,4,5,6,7,8,9,10,11,12), (14,1,2,3,4,5,6,7,8,9,10,11,12,13))

Python code:

from itertools import combinations, permutations

def examples(fromN=2, toN=13, strict=False):
    for n in range(fromN, toN + 1):
        leftShifLatinSquare = makeLeftShiftLatinSquare(range(1, n + 1))
        print('N = {0}:'.format(n))
        try:
            if strict:
                plan, countPrevious = next(iterPlansStrict(leftShifLatinSquare))
            else:
                plan, countPrevious = next(iterPlans(leftShifLatinSquare))
        except StopIteration:
            print('reached the end of the possibilities. No valid seating plan found.')
        else:
            print('iterated through {0} invalid seating plans, and then found:'.format(countPrevious))
            print(plan)
        print()

def iterSeatingPlans(people, strict=False):
    if strict:
        for latinSquare in iterLatinSquares(people):
            for plan in iterPlansStrict(latinSquare):
                yield plan
    else:
        for latinSquare in iterLatinSquares(people):
            for plan in iterPlans(latinSquare):
                yield plan

def seatingPlanCounts(nPeople, strict=False):
    people = tuple(p for p in range(nPeople))
    counts = dict()
    if strict:
        for latinSquare in iterLatinSquares(people):
            count = 0
            for plan, priorCount in iterPlansStrict(latinSquare):
                count += 1
            if count in counts:
                counts[count] += 1
            else:
                counts[count] = 1
    else:
        for latinSquare in iterLatinSquares(people):
            count = 0
            for plan, priorCount in iterPlans(latinSquare):
                count += 1
            if count in counts:
                counts[count] += 1
            else:
                counts[count] = 1

    return counts

def makeLeftShiftLatinSquare(elements):
    n = len(tuple(elements))
    return tuple(tuple(elements[(row+i) % n] for i in range(n)) for row in range(n))

def iterPlans(latinSquare):
    elements = latinSquare[0]
    for countPrevious, plan in enumerate(permutations(latinSquare)):
        prevMoves = [plan[0][plan[1].index(e)] for e in elements]
        for j in range(2, len(plan)):
                curMoves = [plan[j-1][plan[j].index(e)] for e in elements]
                if any(cur == prev for cur, prev in zip(curMoves, prevMoves)):
                        break
                prevMoves = curMoves
        else:
            yield plan, countPrevious

def iterPlansStrict(latinSquare):
    elements = latinSquare[0]
    for countPrevious, plan in enumerate(permutations(latinSquare)):
        replacements = [set((plan[0][plan[1].index(e)],)) for e in elements]
        for j in range(2, len(plan)):
                curMoves = [plan[j-1][plan[j].index(e)] for e in elements]
                if any(cur in replacements for cur, replacements in zip(curMoves, replacements)):
                        break
                for i, e in enumerate(elements):
                    replacements[i].add(curMoves[i])
        else:
            yield plan, countPrevious

def iterLatinSquares(elements):
    n = len(elements)
    for possible in combinations([e for e in permutations(elements)], n):
        if any(len(set(sp.index(e) for sp in possible)) != n for e in elements):
            continue
        yield possible

Solving the stricter version

I added 'strict' options to allow for the stricter version here are some results:

$N=2$ and $N=3$ remain the same

$N=4$ has $3!(1\times 0+3\times 8)=24$ solutions

$N=5$ has $4!(56\times 0)=0$ solutions

$N=6$ has solutions, one is:

((1,2,3,4,5,6), (2,3,4,5,6,1), (6,1,2,3,4,5), (3,4,5,6,1,2), (5,6,1,2,3,4), (4,5,6,1,2,3))

$N=7$ has no solutions that are permutations of your method

$N=8$ has solutions, one is:

((1,2,3,4,5,6,7,8), (2,3,4,5,6,7,8,1), (4,5,6,7,8,1,2,3), (7,8,1,2,3,4,5,6), (3,4,5,6,7,8,1,2), (8,1,2,3,4,5,6,7), (6,7,8,1,2,3,4,5), (5,6,7,8,1,2,3,4))

$N=9$ has no solutions that are permutations of your method

$N=10$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10), (2,3,4,5,6,7,8,9,10,1), (4,5,6,7,8,9,10,1,2,3), (3,4,5,6,7,8,9,10,1,2), (8,9,10,1,2,3,4,5,6,7), (5,6,7,8,9,10,1,2,3,4), (9,10,1,2,3,4,5,6,7,8), (7,8,9,10,1,2,3,4,5,6), (10,1,2,3,4,5,6,7,8,9), (6,7,8,9,10,1,2,3,4,5))

$N=11$ has no solutions that are permutations of your method

$N=12$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10,11,12), (2,3,4,5,6,7,8,9,10,11,12,1), (4,5,6,7,8,9,10,11,12,1,2,3), (3,4,5,6,7,8,9,10,11,12,1,2), (8,9,10,11,12,1,2,3,4,5,6,7), (11,12,1,2,3,4,5,6,7,8,9,10), (9,10,11,12,1,2,3,4,5,6,7,8), (5,6,7,8,9,10,11,12,1,2,3,4), (12,1,2,3,4,5,6,7,8,9,10,11), (6,7,8,9,10,11,12,1,2,3,4,5), (10,11,12,1,2,3,4,5,6,7,8,9), (7,8,9,10,11,12,1,2,3,4,5,6))

$N=14$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10,11,12,13,14), (2,3,4,5,6,7,8,9,10,11,12,13,14,1), (4,5,6,7,8,9,10,11,12,13,14,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,14,1,2), (6,7,8,9,10,11,12,13,14,1,2,3,4,5), (11,12,13,14,1,2,3,4,5,6,7,8,9,10), (9,10,11,12,13,14,1,2,3,4,5,6,7,8), (5,6,7,8,9,10,11,12,13,14,1,2,3,4), (12,13,14,1,2,3,4,5,6,7,8,9,10,11), (7,8,9,10,11,12,13,14,1,2,3,4,5,6), (13,14,1,2,3,4,5,6,7,8,9,10,11,12), (10,11,12,13,14,1,2,3,4,5,6,7,8,9), (14,1,2,3,4,5,6,7,8,9,10,11,12,13), (8,9,10,11,12,13,14,1,2,3,4,5,6,7))
$\endgroup$
  • $\begingroup$ Thank you for putting together such a fantastic solution! I can move forward with the project I've been stuck on for, uh, way too long. The problem: I do not know if have the background to say which answer is better, yours or ffao. Yours clearly has the practical upper hand. ffao, however, gives a useful background to the issue. Could we combine and give a dual-author win? Probably not. Regardless, thank you! $\endgroup$ – Derek DeBellis Jun 7 '16 at 6:15
1
$\begingroup$

The table you're looking for is called in mathematical terms a "column-complete latin square".

For even N, they are easy to construct: assuming the tables are in a circular arrangement, have everyone move right 1 table, then move left 2, then right 3, and so on.

For odd values of N it can get complicated. If N is 3,5 or 7, then there is no possible table that fulfills all constraints.

Jeffrey Higham gave in 1998 a way to make a table for every composite N in "Construction methods for row-complete latin squares", but it's not very simple.

As for the remaining prime numbers, no one knows how to construct a table for them or prove that the table does not exist.

Here's how a sample solution looks for the first odd composite number, 9:

123456789
291784635
376948152
418295376
547861923
635129847
789513264
864372591
952637418
$\endgroup$
  • $\begingroup$ I am working on a brute-forcer and I have solutions for $N=5$ and $N=7$ - is it possible that you are thinking that "Susan can not move to the seat occupied by Tim if she has ever done so before" rather than the less strict "Susan can not move to the seat occupied by Tim if she did so last seat change"? $\endgroup$ – Jonathan Allan Jun 6 '16 at 1:16
  • $\begingroup$ @JonathanAllan The fundamental problem is that the start of the post describes one problem and the end of the post a different one. As you guessed, I went with the bottom, more strict, version (no one replaced the same person more than once) $\endgroup$ – ffao Jun 6 '16 at 1:28
  • $\begingroup$ I should have read the edit in it's entirety. $\endgroup$ – Jonathan Allan Jun 6 '16 at 1:29
  • $\begingroup$ Does the column-complete definition effectively include a seat change from the finishing arrangement to the starting one though? $\endgroup$ – Jonathan Allan Jun 6 '16 at 1:33
  • $\begingroup$ I don't see anything relating the first and last rows in the column-complete definition, why do you think so? $\endgroup$ – ffao Jun 6 '16 at 4:05
0
$\begingroup$

Label the seats $0, \dots, n-1$ and the iterations and people likewise. Let addition be modulo $n$. Suppose that in each iteration $i$, whichever person $P_i$ is in seat $0$, person $P_i+s$ is in seat $s$. Then we need a sequence $P_0,...,P_{n-1}$ which is a permutation of $0, \dots, n-1$, with all the $n-1$ successive differences $P_{i}-P_{i-1}$ distinct, modulo $n$.
If $n$ is even, this is possible with $P_{2k} = k$ and $P_{2k-1} = n-k$.

$\endgroup$
  • $\begingroup$ I can't see this response. I need to hover over to see it. Is there a reason why? Sorry, I am excruciatingly novice. $\endgroup$ – Derek DeBellis Jun 7 '16 at 6:23
  • $\begingroup$ This is intended. Many people read puzzling.SE for the puzzles & to try solving them without accidentally seeing other people's tries. So in answering a puzzle with what we think are (full or partial) answers, we use spoiler-blocks, where, as you see, you need to hover to see them. $\endgroup$ – Rosie F Jun 7 '16 at 6:38
  • $\begingroup$ That makes complete sense. Cool feature. Thanks so much for your answer! I need to try to apply it. Interesting to these answers intersect $\endgroup$ – Derek DeBellis Jun 7 '16 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.