Skip to main content
2 of 3
deleted 99 characters in body

Seating problem: N tables with N people at each table

There are N tables at a party seating N people each, for a total of N^2 people. Every seat is initially empty.

At each round, every person must sit with a new group of people. If each person were given a number, they would need to see unique numbers at their table every round - numbers they have seen in previous rounds also count.

Question: How many rounds can occur before a person sees a duplicate?

The upper bound is (N^2 - 1) / (N - 1) = (N + 1) rounds trivially if you consider the problem from one person's perspective.

For N = 2 (4 people, 2 tables of 2) it is correct:

AB CD
AC BD
AD BC

Is there a general formula for this maximum number of rounds?

Inspiration: I was at a workshop with 36 people around 6 identical tables; at the end of each intermission, we were encouraged to sit with entirely new people.