Problem

Source: 2016 Latvia BW TST P8

Tags: combinatorics



$3n - 2$ participants took part in the chess festival, some of them played one game of chess with each other. Prove that at least one of the following statements holds: (A) One can find $n$ chess players $A_1 , A_2 , . . . , A_n$ suchthat Ai has played a game with $A_{i+1}$ for all $i = 1, ...,n -1$. (B) Seven chess players can be found in $B_1 , . . . , B_7$, who have not played with each other, except perhaps three pairs $(B_1, B_2)$, $(B_3, B_4)$ and $(B_5, B_6)$, each of whom may or may not have played a game of chess.