6
$\begingroup$

The other day, I met with professor Halfbrain and professor Erasmus in the coffee house. Professor Erasmus told us that he had been working on a schedule for a tennis club with $30$ senior and $30$ junior members.

  • Every senior member should play against one other senior member once, and against $15$ of the junior members once.
  • Every junior member should play against one other junior member once, and against $15$ of the senior members once.
  • No further matches should be scheduled.

Professor Halfbrain listened to this attentively, and then claimed that in each such schedule there will be two senior members $S_1$ and $S_2$ and two junior members $J_1$ and $J_2$ such that:

  • The two senior members $S_1$ and $S_2$ play against each other.
  • The two junior members $J_1$ and $J_2$ play against each other.
  • Each of $S_1$ and $S_2$ play against at least one of $J_1$ and $J_2$.
  • Each of $J_1$ and $J_2$ play against at least one of $S_1$ and $S_2$.

Question: Is professor Halfbrain's claim indeed true, or has the professor once again made one of his mathematical blunders?

$\endgroup$
  • $\begingroup$ With "there will be two senior members..." does that mean there is exactly one such a foursome, or at least one such a foursome that satisfy the conditions? $\endgroup$ – Ivo Beckers Mar 23 '16 at 13:30
  • 1
    $\begingroup$ @Ivo Beckers: It means that there exists at least one configuration of four players with the stated properties. $\endgroup$ – Gamow Mar 23 '16 at 13:33
4
$\begingroup$

It is

true

Let's first split $S$ in half such that people in the first half are paired with people in the second half: $S_{first}$ and $S_{second}$.

Let's say the theorem isn't true. In that case the $15$ people from $S_{first}$ must be paired with the same $15$ $J$ and the other $15$ $J$ with $S_{second}$ and there are no links allowed between the two $J$ groups. However, $15$ is an odd number so you can't pair the 15 $J$ people with each other, so there exist at least one pair between two $J$ groups proving the theorem.

I hope it's clear what I mean because I had a hard time expressing it.

$\endgroup$
  • $\begingroup$ Just realized that splitting the $S$ group wasn't necessary at all. I just had to take any paired $S_1$ and $S_2$ and then logically they each need to be paired to 15 different $J$ and conclude the same way $\endgroup$ – Ivo Beckers Mar 23 '16 at 14:39
3
$\begingroup$

He's...

right.

Beginning of the proof:

Every junior can only play one match with another junior, so we can arrange the juniors into a 15 x 2 block with $J_n$ right above $J_{n+15}$ and match all the instances (same goes for the seniors group, where $S_n$ is "made" to play with $S_{n+15}$). Each of all matched two juniors plays with one or both seniors from the same matched senior pair, because in the worst case scenario the first junior plays with all of 7 pairs of seniors and one from another pair. The other junior does the same with the remaining pairs, but the last senior must come from one of the pairs the former has played. It also works the other way around (starting from seniors).

Some possibilities:

If said juniors/seniors play with both seniors/juniors in total, the four fulfill the conditions. If both only play with the same one, there's still work to do. A junior can play the whole of $a$ pairs, only play one senior out of $15-2a$ pairs, and avoid the remaining $a$ pairs. To prevent the conditions from being fulfilled, his/her pairmate must avoid the aforementioned first, play the same seniors in the second, and play the whole of the third. Thus, every combination consisting of one jr, one sr pair contains only one player (jr or sr) playing with both from the other pair. 15 is an odd number, so for each pair, there must be an odd number of other pairs one of whose players play with both players of it (such a pair combo looks the other way when seen backwards, therefore every opposite-pair combination falls into this category). There are 15*15=225 opposite-pair combos, but the sum of 30 odd numbers is even, leading to a contradiction and meaning the Professor must be right.

$\endgroup$
2
$\begingroup$

It's

true

because

put seniors in one set and juniors in another. Consider the x-lines connecting the two sets, where a x-line joins a junior and a senior who play eachother. There will be 15*30 = 450 such lines. Now consider only the x-lines between a pair of seniors partners and a pair of junior partners (where partners are two juniors who play eachother, or 2 seniors who play eachother). Call such a 4-player group a 'x-group'. Assume the theorem isn't true. Then there can be at most 2 x-lines for any x-group. If there were exactly 2 x-lines for each x-group, then there would be 2*15*15 = 450 lines in total, which is the number we need. Therefore there can't be less than 2 x-lines for any x-group. So for the theorem to be false, there must be exactly 2 x-lines for each possible x-group. Moreover, the two x-lines can't be parallel, i.e. both lines must terminate at the same player on one end, and at different players on the other end. Call such a line configuration a 'v-path'.

Going by this logic, we can build up a schedule by considering each possible x-group in turn, and selecting a single v-path. Each v-path will add 2 to the number of games played for one player on one side, and 1 to the number of games played for both players on the other side. Call these two operations a (2x1) addition and (1x2) addition respectively. Therefore the number of (2x1) additions has to be equal to the number of (1x2) additions. Since each player must end up playing 15 games (not including the one with his partner), all these additions must total to 30*15*2 = 900. Therefore we will have 225 (2x1) additions, and 225 (1x2) additions. Now, any time a player is given a (2x1) addition, his partner must also get one at some point, otherwise it would be impossible to give them equal games played with only (1x2) additions. Therefore the total number of (2x1) additions given out must be even. However, we have 225 (2x1) additions in total, which is odd. Therefore there's no way to satisfy the conditions highlighted in bold above, and since this is the only way to contradict the question statement, the statement must be true

$\endgroup$

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.