A mathematical contest had $3$ problems, each of which was given a score between $0$ and $7$ ($0$ and $7$ included). It is known that, for any two contestants, there exists at most one problem in which they have obtained the same score (for example, there are no two contestants whose ordered scores are $7,1,2$ and $7,1,5$, but there might be two contestants whose ordered scores are $7,1,2$ and $7,2,1$). Find the maximum number of contestants.
Problem
Source: ITAMO 2016, Problem 2
Tags: combinatorics
11.05.2016 23:14
Consider the lattice points $(x,y,z)$ such that $x,y,z\in [0,7]\text{ and }x,y,z\in\mathbb{Z}$. Color a lattice point $(x,y,z)$ red if there exists a student who got $x$, $y$, and $z$ as their scores for the first, second, and third problems, respectively. The problem condition is equivalent to the condition that if $(x,y,z)$ is red, then $(x,y,k), (x,k,z), (k,y,z)$ are all not red for $0\le k\le 7$ (with the exception of when the point is equal to $(x,y,z)$), which correspond to the up-down, left-right, and front-back rows that contain $(x,y,z)$. Looking at all lattice points $(x,y,k)$ such that $x,y\in [0,7]$ and $k$ is a constant, by Pigeonhole principle there exists at most $8$ red lattice points, else there exists two red lattice points in the same row, contradiction. Thus, the maximum possible is $8\cdot 8=\boxed{64}$ and it remains to show this is attainable. However, a construction is easy; just take all points of the form $(x,y,x-y)$ where values are calculated mod $8$ and $x,y\in [0,7]$. (just draw a diagram and this obviously works)
04.12.2018 11:33
Assume there exists $65$ contestants . By Pigeon Hole Principle, at least $9$ got the same points on one problem , again by Pigeon Hole Principle from these $9$ contestants , at least $2$ got the same points on another problem , contradicition , so the number of contestants $\leq 64$