Seatings at tables

Task number: 3457

Consider a group of \(n=3k\) people and \(k\) tables, each seating 3 people. How many times must this group sit at the tables such that each pair of people encounter each other exactly once?

You may assume that a conforming seating plan is possible, even though this not need be true in general. For example, is any seating plan possible for an even number of tables? Generalize your reasoning for an \(n\)-person group, tables with \(s\) places, and \(t\)-tuples of people who must encounter each other exactly once.

  • Solution

    Choose an arbitrary person in the group \(x\); now we must divide the remaining people into pairs such that \(x\) will sit together with each pair exactly once. So the required number of seatings is \(\frac{n-1}2\). From here it follows that \(n\) is an odd multiple of three, so \(k\) is odd.

    Alternative reasoning: \(\binom{n}{2}\) pairs must meet in all, and in a single seating three pairs meet at each table, so in a single seating a total of \(3\frac{n}3=n\) pairs meet at all the tables. So now the number of seatings is given by \(\frac{\binom{n}{2}}{n}=\frac{n-1}2\)

    In general, at a single seating at an \(s\)-place table, \(\binom{s}{t}\) \(t\)-tuples will meet, and so in a single seating at all \(\frac{n}{s}\) tables, \(\binom{s}{t}\frac{n}{s}\) \(t\)-tuples will meet. There are a total of \(\binom{n}{t}\) \(t\)-tuples.

    The number of seatings equals: \( \frac{\binom{n}{t} s}{\binom{s}{t} n}\), which might not be an integer (in which case no appropriate seating plan exists).

     

    Side note: This is called a Steiner triple system with parallelism or a Kirkman triple system. This exists for all odd multiples of three, as was shown in 1965.

Difficulty level: Moderate task
Reasoning task
Cs translation
Send comment on task by email