10
$\begingroup$

Each of the five teams A, B, C, D, E consists of five table tennis players. In their tournament last week, each player has played one match against each of the twenty players in the other four teams. The players were numbered 1, 2, 3, 4, ..., 25, and by a lucky coincidence every single match in the tournament was won by the player with the smaller number. Furthermore,

  1. team A has won at least $x$ matches against B;
  2. team B has won at least $x$ matches against C;
  3. team C has won at least $x$ matches against D;
  4. team D has won at least $x$ matches against E; and
  5. team E has won at least $x$ matches against A.

What is the largest value $x$ for which this story could be true?

$\endgroup$
  • $\begingroup$ Related: mathoverflow.net/questions/119867/… $\endgroup$ – Julian Rosen Jan 20 '15 at 3:35
  • $\begingroup$ 1. Sorry, but what is "smaller number"? A winning player number was smaller than what? 2. Is this correct, that 25*20=500 matches were played in total? $\endgroup$ – klm123 Feb 3 '15 at 21:20
  • $\begingroup$ Numbering of the players can be arbitrary and shoud not depend on a team? $\endgroup$ – klm123 Feb 3 '15 at 21:25
  • $\begingroup$ @klm: Every match is played by two players. Each of these two players has a number (from 1,...,25). Each matach is won by the player with smaller number. $\endgroup$ – Gamow Feb 4 '15 at 9:16
  • $\begingroup$ Doesn't that mean that the player with number 1 has played, and won 20 matches? How is the answer only 16? $\endgroup$ – ghosts_in_the_code Feb 5 '15 at 9:46
9
+50
$\begingroup$

x=16 with the following order:

A BB CCC DDDD EEEEE AAAA BBB CC D




Now I can also show that x=16 is best possible: Order the players from left to right by increasing number (as in my solution shown above). Put for every team the middle player in boldface (so that there are two players from the same team to its left and two players from the same team to its right):

A BB CCC DDDD EEEEE AAAA BBB CC D

Consider the rightmost of the five boldface players. If this rightmost boldface is from team A then he and his to team mates to the right lose all their matches against the three leftmost players from team B (the boldface player from B and his two team mates to the left of him). Similar and symmetric arguments work, if the rightmost boldface is from teams B,C,D,E. Altogether this means that team A loses at least nine matches against B, and can win at most 16 matches against E. Therefore x<=16

$\endgroup$
  • 2
    $\begingroup$ Very nice argument for the maximum value of x. It's worth specifically noting that this generalises to any number of 5 player teams (or 5 sided dice); there must always be some team with a rightmost middle player, and that team must lose at least 9 matches to all other teams, including the one they are supposed to beat x times. $\endgroup$ – frodoskywalker Feb 1 '15 at 11:56
4
$\begingroup$

$x=14$ with the following order:

abcde bcdea cdeab deabc eabcd

$\endgroup$
  • 2
    $\begingroup$ Actually, your example only shows $x\ge14$. It remains to find out whether even larger values are possible. $\endgroup$ – Gamow Jan 20 '15 at 10:03

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.