Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
The Dinner club has 169 members, and professor Erasmus is one of them. Every evening, four of the members meet and have dinner together in a fancy restaurant. Professor Erasmus claims that today is a very special day for the club: after today's dinner, every two club members will have had a club dinner together exactly once.
We wonder: Is this indeed possible, or has the professor once again made one of his well-known mathematical blunders and miscalculated the days and dinners?
It is possible, but I don't have a really neat proof. What I have is a construction proof.
Lemma 1: a club with 13 members can do this.
One member has four dinners, each one with three other members. That member has had dinner with everyone, and divided up the rest into four groups. Each member of a group has had dinner with all other members of the group and no members of the other groups. Number each group's members 0,1 and 2; we can construct dinner groups for the rest as follows:
0000, 0111, 0222
1012, 1120, 1201
2021, 2102, 2210
(The nth group is represented by the nth digit in each case).
That's nine dinners, and by inspection each member appears exactly once with each other member. Together with the initial four dinners, that covers everyone.
Lemma 2: from a collection of $p^2$ members, we can make $p^2 + p$ groups, each containing $p$ members, such that every member is in exactly one group with every other member, as long as $p$ is prime.
First divide the members into $p$ initial groups of $p$ each. Number them $0...p-1$ and also number each group member $0...p-1$ inside each initial group. Now we form the other $p^2$ derived groups by choosing one member from each of the initial groups as follows:
For derived group $a,b$, take member $a + gb$ (mod p) from initial group number $g$. The $a,b$ each vary independently over $0...p-1$, so there will be $p^2$ of these derived groups.
Suppose $x$ and $y$ from two different initial groups are each in two derived groups, $a_1, b_1$ and $a_2, b_2$
From the first group we have $x - y = a_1 + g_x.b_1 - ( a_1 + g_y.b_1 ) = b_1(g_x - g_y)$. From the second we have $x - y = b_2(g_x - g_y)$. Equating these, we get $(b_1 - b_2)(g_x - g_y) = 0$. That means one of three things:
* $g_x = g_y$, so they are in the same group. But we only choose one element from each group, so they must be the same element.
* Two non-zero numbers multiply to form a zero number. But that's not possible mod p, because p is prime.
* $b_1 = b_2$. Now we can say that $a_1 + g_x.b_1 = a_2 + g_x.b_2$, so $a_1 - a_2 = g_x.b_2 - g_x.b_1 = 0$, so $a_1 = a_2$, so these are not two groups but the same group.
Because each derived group contains one member from each initial group, every member must appear at most p derived groups (or else there would necessarily be overlap with at least one member of another initial group, because there are only p members in each initial group). Because there are $p^2$ groups of $p$ members making $p^3$ members in all the derived groups, and $p^2$ members in total, each member must appear in at least $p$ derived groups otherwise some members would need to appear in more than $p$ derived groups. Therefore every member appears in exactly $p$ derived groups, each time with a different member of each other initial group.
Combined with the initial groups, each member appears in $p+1$ groups total, and appears in a group of $p$ exactly once with each other member of the club.
Now for the final proof:
$ 169 = 13 x 13$, and 13 is prime, so we can create 182 groups of 13, such that every member appears with every other member exactly once - from Lemma 2.
Within each group of 13, we can have 13 dinners in groups of four such that every member dines with every other member exactly once - from Lemma 1.
Therefore, we can have $182 x 13 = 2366$ dinners for four, with every member dining with every other member exactly once.
It is impossible.
The number of handshakes between the members is ${169 \choose 2} = 22646$ and the number of handshakes in a four member dinner is exactly $6$, but the total number of handshakes is not a multiple of $6$, so either some handshake has been executed more than once, or some handshake is missing.
WARNING: Wrong calculation
