5
$\begingroup$

Eight people played chess in a round robin tournament.

No match ended in a tie and both A and B won the first place.

Since C and D were rivals, C beat all players who beat D and D beat all players who beat C.

What is the final score of A and B (the number of wins and defeats)?

$\endgroup$
  • 2
    $\begingroup$ Did the winner of C vs. D then play against and beat himself? $\endgroup$ – KSmarts Feb 2 '15 at 15:28
  • $\begingroup$ @KSmarts Probably. But, it was not recorded on the score board. :-) $\endgroup$ – P.-S. Park Feb 2 '15 at 15:35
9
$\begingroup$

With $8$ players, there have been $(8 \times 7)/2 = 28$ matches and therefore $28$ points.

If A and B scored 4 points or less, the other players would have scored at most 3 points which brings a total of at $2\times 4+6\times 3 = 26$ points or less. But there are 28 points altogether. Therefore A and B scored at least 5 points.

One of A or B must have lost against the other, and both have lost against C or D. Therefore one of them has lost 2 matches and scores at most 5 points.

As a result, A and B can have scored only 5 points. They won 5 and lost 2 matches each.

$\endgroup$
6
$\begingroup$

(I assume that $A, B, C, D$ represent names, and denote four pairwise distinct players; I call the other four players $E,F,G,H$. Furthermore, I assume that the statement "Since $C$ and $D$ were rivals ..." does not cover the particular game played between $C$ and $D$.)

By the problem statement, no player in $\{A,B,E,F,G,H\}$ has won both games against $C$ and $D$. Hence $\{A,B,E,F,G,H\}$ can be partitioned into three disjoint sets:

  • the set $L(C)$ of players who have lost to $C$ and won against $D$
  • the set $L(D)$ of players who have lost to $D$ and won against $C$
  • the set $L(CD)$ of players who have lost against both $C$ and $D$

By symmetry we now assume that $C$ ended up with at least as many points as $D$.

(1) $C$ scored at least $4$ points.

Proof: Suppose for the sake of contradiction that $C$ scored at most $3$ points. If $C$ won against $D$, this implies $|L(C)|\le2$ and hence $|L(D)|+|L(CD)|\ge4$; then $D$ has scored at least $4$ points; contradiction. IF $C$ lost to $D$, this implies $|L(C)|+|L(CD)|\le3$ and hence $|L(D)|\ge3$; then $D$ has scored at least $4$ points; another contradiction.

(2) $A$ and $B$ each scored at least $5$ points.

Proof: $A$ and $B$ won the first place, and hence scored more points than $C$.

(3) $A$ and $B$ each scored at most $5$ points.

Proof: Suppose for the sake of contradiction that $A$ and $B$ both scored at least $6$ points. They played one game against each other, and altogether $12$ games against the other six players. Then one of them must have won all six matches against ${C,D,E,F,G,H}$, and in particular his matches against $C$ and $D$; contradiction.

So the answer is: $A$ and $B$ each lost two matches and each won five matches.

$\endgroup$
3
$\begingroup$

For something like this, simply constructing a specific outcome that meets the requirements isn't actually that hard, and I think is an often overlooked way of solving some puzzles. Here's an example:

  a b c d e f g h total
a - 1 0 1 0 1 1 1   5
b 0 - 1 0 1 1 1 1   5
c 1 0 - 1 0 1 1 0   4
d 0 1 0 - 1 0 0 1   3
e 1 0 1 0 - 1 0 0   3
f 0 0 0 1 0 - 1 1   3
g 0 0 0 1 1 0 - 1   3
h 0 0 1 0 1 0 0 -   2

I started out with A beating everyone except D. It then immediately became obvious that B could not tie A. So I added another loss to A (against E). From there, I made sure C and D had mirror outcomes, and filled out the rest of the table making sure to keep everyone below 5 wins. The whole thing only required backtracking once.

$\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.