Ponder This Challenge - August 1999 - Seating people on N+M tables

This puzzle is from Evan Morton.

Recently I went on a vacation with my wife and her extended family. The dining room staff at the resort said that the 14 of us could not be seated at the same table, so they put us at two tables, of 8 and 6 seats respectively. So I wondered, if everyone wants to sit at least once with everyone else, how many meals do we need to accomplish this?

When I say "sit with," I don't mean "sit next to", I just mean sit at the same table.

This leads to a more general question. Given any two numbers M and N, if M+N people are seated at tables of M and N respectively, how many meals does it take?

This is not a trick question. At a given meal you have to sit in one seat throughout the meal, the tables do not overlap, etc.)
It turns out to be a reasonably hard problem.

Solution

• Click here to view the solution

  Assume throughout that N >= M. Let's dispose of some strange cases first.

  If M=0 and N is either 0 or 1, then no sessions are required, since there are no pairs of people to worry about. If M=0 and N >= 2 then one session is required. If M=N=1 the problem is impossible: the two people can never sit together. So we will assume from here on that N >= M >= 1 and (N,M) not equal to (1,1). If 2M>N >= M >= 1 and both M and N are odd, you need exactly four sessions.. In all other cases you need exactly three sessions.

  Having disallowed the strange cases, you always need at least three sessions. That's because (in an optimal setup, using the least number of sessions) the arrangement on the first session is necessarily different from that of the second session, so there is one diner x who was at the N table the first night and the M table the second night. There is another diner y who sat at the M table the first night and the N table the second night. You need a third session for x and y to sit together. (You may need more.)

  CASE 1: N >= 2M Groups (A,B,C,D) of size (N-2M,M,M,M).

  • 1 session: (ABC)(D) at N table and M table respectively
  • 2 session: (ABD)(C)
  • 3 session: (ACD)(B)

  CASE 2: N<2M ; M even Groups (A,B,C,D) of size (N-M/2,M/2,M/2,M/2)

  • 1 session: (AB)(CD)
  • 2 session: (AC)(BD)
  • 3 session: (AD)(BC)

  CASE 3: N<2M ; N even Groups (A,B,C,D) of size (M-N/2,N/2,N/2,N/2)

  • 1 session: (BC)(AD)
  • 2 session: (BD)(AC)
  • 3 session: (CD)(AB)

  CASE 4: N<2M ; both M and N odd This is the only case that requires four sessions. First let's show that three sessions do not suffice for this case. Without loss of generality the first two sessions use groups (A,B,C,D) of size (X,X,N-X,M-X) for some integer X with 0 <= X <= M .

  • 1 session: (AC)(BD)
  • 2 session: (BC)(AD)

  If all four groups are nonempty, and if only three sessions are to be used, then the third session must seat (AB) together and must also seat (CD) together. (AB) is of size 2X , which is even, so can't fully occupy one table. Neither can (CD). So the third session cannot satisfy everyone. On the other hand if one of the groups is empty, then either X=0 or X=M . If X=0 then the first two sessions are identical, impossible. If X=M then we really had groups (A,B,C) of size (M,M,N-M) , and

  • 1 session: (AC)(B)
  • 2 session: (BC)(A)

  and the third session would have to put (AB) at one table, but the size of (AB) is 2M , which is larger than N . Therefore you need at least four tables for this case. We cannot have M=1 , since (N,M)=(1,1) is ruled out and we have assumed N<2M . So M is at least 3. Create seven groups (A,B,C,D,E,F,G) of sizes |A|=|B|=|C|=1 , |D|=(M-3)/2 , |E|=|F|=(M-1)/2 , |G|=N-(M+1)/2 . ( The various inequalities imply that all these sizes are nonnegative integers.)

  • 1 session: (ACDG) (BEF)
  • 2 session: (AEG) (BCDF)
  • 3 session: (BFG) (ACDE)
  • 4 session: (CEG) (ABDF)

  So this case can be done with four sessions. A related problem from information theory is how to arrange that each pair avoids each other at at least one meal, and there the answer is related to \log_2>(M+N).

Solvers

• Kunal Shroff (8.4.1999 @ 4:57 PM EST)
• Ludger Weber (8.5.1999 @ 2:52 AM EST)
• Glen Hattrup (8.5.1999 @ 4:36 PM EST)
• Tom Bradford (8.5.1999 @ 6:50 PM EST)
• Alamuru Krishal (8.5.1999 @ 9:20 PM EST)
• Chris Lusby-Taylor (8.5.1999 @ 10:23 AM EST)
• David MacMahon (8.5.1999 @ 10:31 PM EST)
• Dieter Verhofstadt (8.6.1999 @ 2:59 AM EST)
• Donna Byrne (8.6.1999 @ 7:16 AM EST)
• Sachin Desai (8.6.1999 @ 7:22 AM EST)
• Ming-Wei Wang (8.8.1999 @ 8:09 PM EST)
• Bruce Hoff (8.9.1999 @ 3:51 PM EST)
• Joseph Devincentis (8.11.1999 @ 9:49 AM EST)
• Ernst Munter (8.11.1999 @ 2:26 AM EST)
• Peter Huesken (8.14.1999 @ 9:26 AM EST)
• Bart VanSteirteghem (8.17.1999 @ 2:17 PM EST)
• Dan Peleg (8.23.1999 @ 3:10 AM EST)
• Cheryl Patrick (8.24.1999 @ 8:24 AM EST)
• Vivek Agrawal (8.24.1999 @ 12:36 PM EST)
• Petr Broz (8.30.1999 @ 5:33 AM EST)
• Manish C Tayal (9.1.1999 @ 11:26 AM EST)