IBM Research | Ponder This | August 1999 solutions
Skip to main content

Ponder This

August 1999

<<July August September>>

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 \log2(M+N) .

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com