11
$\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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Related: mathoverflow.net/questions/119867/… $\endgroup$
    – Julian Rosen
    Commented Jan 20, 2015 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
    Commented Feb 3, 2015 at 21:20
  • $\begingroup$ Numbering of the players can be arbitrary and shoud not depend on a team? $\endgroup$
    – klm123
    Commented Feb 3, 2015 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
    Commented Feb 4, 2015 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
    Commented Feb 5, 2015 at 9:46

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
1
  • 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
    Commented Feb 1, 2015 at 11:56
4
$\begingroup$

$x=14$ with the following order:

abcde bcdea cdeab deabc eabcd

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

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