Problem 1126

a) Let's assume that all cells of the table are unit squares. Then the area $S$ of all cells below the diagonal is equal to the number of games in the tournament and the total number of points scored. We will color in red the cells containing ones for incorrect games. Note that all red cells are below the main diagonal. Draw a horizontal middle line of the table (if the number of participants is odd, the cells of the middle row will be divided in half; points from these cells will also be divided equally between the half-cells). It is clear that the sum of points in the upper half is not less than in the lower half.

The part of the table above the middle line but below the diagonal will be called an eighth, its area is less than $S / 4$ (since the table without the cells of the two main diagonals is easily divided into 8 eighths).

The area of the red region in the upper half of the table is no more than the area of the eighth, that is, less than $S / 4$. The area of the red region in the lower half of the table is no more than the sum of points from the lower half, that is, no more than $S / 2$. Therefore, the area (and thus the number) of red cells in the entire table is less than $3 S / 4$.

b) Consider a tournament with $2 m^{2}$ chess players. Divide them into $m$ groups of $2 m$ people each and number the members of each group from 1 to $2 m$. Let the player with the smaller number always win within the groups.

Now we will define the results of the games between participants from different groups. Let the games between players with the same numbers, as well as with numbers differing by $m$, end in a draw; with a difference in numbers greater than $m$, the player with the smaller number wins, and with a difference less than $m$, the player with the larger number wins. It is easy to see that each participant scored exactly $m$ points against players from any "foreign" group, so the placement of participants in the final standings is determined by the results of the games within the groups, that is, by their numbers (the smaller the number, the higher the place).

Let's estimate the number of correct games. First, these are all the games within the groups, their total number is less than $1/m$ of the total number of games in the tournament. Secondly, these are the games that ended in a draw: for each player (and thus in the entire tournament) they make up less than $1 / m$ of the total number of games. Thirdly, these are the correct decisive (non-draw) games played between players from different groups.

Consider the number of decisive correct games between players from any two groups $A$ and $B$. A player with number $k \leq m$ won $m-k$ correct games (against players with numbers $m+k+1, \ldots, 2 m$). Players with numbers greater than $m$ did not win any correct games. In total, $2((m-1)+(m-2)+\ldots+1)) = m(m-1)$ correct games, which is exactly $1 / 4$ of the total number $2 m(2 m-2)$ of decisive games between players from these groups. Therefore, the total number of "inter-group" decisive correct games is less than a quarter of the total number of games in the tournament.

Thus, the total number of correct games is less than $1 / 4 + 1 / m + 1 / m$ of the total number of all games in the tournament (but more than $1 / 4$ according to part a). The larger the number $m$ we choose, the closer the proportion of correct games will be to $1 / 4$.

## Answer

a) They cannot; b) They can.