## 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)
- 1 session: (AB)(CD)
- 2 session: (AC)(BD)
- 3 session: (AD)(BC)
- 1 session: (BC)(AD)
- 2 session: (BD)(AC)
- 3 session: (CD)(AB)
- 1 session: (AC)(BD)
- 2 session: (BC)(AD)
- 1 session: (AC)(B)
- 2 session: (BC)(A)
- 1 session: (ACDG) (BEF)
- 2 session: (AEG) (BCDF)
- 3 session: (BFG) (ACDE)
- 4 session: (CEG) (ABDF)
_{2}(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