6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is super elegant, if you think about drawing a 13 by 13 grid of points, and removing the line at infinity from the projective plane of order 13, and I should be asleep right now $\endgroup$ – Lopsy Feb 19 '15 at 5:26
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ when did they ever shake hands? $\endgroup$ – DaemonOfTheWest Feb 16 '15 at 1:54
  • 2
    $\begingroup$ More importantly, 22646 = 169 x 268 / 2. 169 choose 2 is 169 x 168 / 2 = 14196, which is divisible by 6. Nice idea, though. $\endgroup$ – Callidus Feb 16 '15 at 7:38
  • $\begingroup$ Gosh... My fingers are so unprecise... $\endgroup$ – rewritten Feb 16 '15 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.