The National Marriage Council wishes to invite $n$ couples to form 17 discussion groups under the following conditions: (1) All members of a group must be of the same sex; i.e. they are either all male or all female. (2) The difference in the size of any two groups is 0 or 1. (3) All groups have at least 1 member. (4) Each person must belong to one and only one group. Find all values of $n$, $n \leq 1996$, for which this is possible. Justify your answer.
Problem
Source: APMO 1996
Tags: combinatorics unsolved, combinatorics
10.04.2006 15:49
An easy one there are 36 solutions. 9,10,11,12,13,14,15,16, 18,19,20,21,22,23,24, 27,28,29,30,31,32, 36,37,38,39,40, 45,46,47,48, 54,55,56, 63,64, 72.
25.05.2012 01:12
Sorry to bring this post back up but the current solution seems very vague (in fact, it's not quite a solution at all). Also, I'm interested in the problem and I want to bring this post back to life so that it can have another chance of someone finding and posting a solution.
25.05.2012 01:50
It probably hasn't been solved or gotten a detailed solution because it's rather ugly casework without any neat insights to be had. Suppose there are $k$ groups of males and $17 - k$ groups of females; WLOG $k \geq 9$. Also suppose that all the groups have $m$ or $m+1$ members. Then $mk \leq (m+1)(17-k)$, or $(2m+1)(2k-17) \leq 17$. Since $m \geq 1$, we have $2k - 17 < 6$, so $9 \leq k \leq 11$. $k = 11$? Then only $m = 1$ works. We have at least 11 males and at most 12 females. So $n = 11, 12$ work. $k = 10$? Then only $m = 1$ or $m = 2$ works. For $m = 1$, we have at least 10 males and at most 14 females. So $n = 10$ through $14$ work. For $m = 2$, we have at least 20 males and at most 21 females. So $n = 20, 21$ work. $k = 9$? Then $m$ can be as high as 8. For a given $m$, we have at least $9m$ males and at most $8(m+1)$ females. This gives the range of solutions seen in post #2 which I won't recopy here. It turns out that this set of solution subsumes all the previous cases, so that is the complete list of answers.