Problem 4

The National Marriage Council wishes to invite

n

couples to form

17

discussion groups. Each group contains members of only one sex; the sizes of any two groups differ by

0

1

; every group is nonempty; and every person belongs to exactly one group. Find all

n\le1996

for which this is possible.

Step 3 of 5: Translate feasibility into four inequalities

Previous step Next step

xq\le n\le x(q+1),\qquad yq\le n\le y(q+1)

Detailed analysis

The $x$ male groups can partition $n$ men into sizes $q,q+1$ exactly when $xq\le n\le x(q+1)$ ; the same reasoning for the $y$ female groups gives $yq\le n\le y(q+1)$ . These inequalities are necessary for every valid arrangement.