49 students solve a set of 3 problems. Each problem is marked from 0 to 7. Show that there are two students A and B such that A scores at least as many as B for each problem.
I saw this post on AoPs discussing the problem, and I was wondering if there's a solution that doesn't use posets? I think a solution involving the pigeonhole principle might be useful. There are obviously ${49\choose 2}$ pairs of students (A,B) where $A$ scores at least as many as B on problem 1. But the issue (as pointed out in the post) is that this doesn't necessarily imply that at least $147$ pairs of students had the same score on problem 2. Also, it is likely useful to observe that the set of triples $(a,b,c)$ so that each variable denotes a score on a problem and $a+b+c = 10$ has cardinality $48.$
It is perhaps easier to think instead of the following question: What is the largest group of students possible, so that no student has three scores that are equal or higher than another student ?
If you think about it this way, it becomes apparent that the group must all have the same total score on the three problems! It is easily demonstrated that this works. Let student A have scores $(a, b, c)$, then another student may have $(a-1, b, c+1)$. Clearly for every pair at least one value is larger and at least value is smaller. And therefore the criterion is satisfied.
What is the largest possible number of students, all having the same score ? Clearly this number is maximal when the score is closest to the average value, which is $10.5$. So both $10$ and $11$ will do. Let us choose $10$. We can now make a list of all possible scores corresponding to this total score:
$$(0, 3, 7) (0,4,6) (0,5,5) (0,6,4) (0,7,3)$$ $$(1,2,7) (1,3,6) (1,4,5) (1,5,4) (1,6,3) (1,7,2)$$ $$(2,1,7) (2,2,6) (2,3,5) (2,4,4) (2,5,3) (2,6,2) (2,7,1)$$ $$(3,0,7) (3,1,6) (3,2,5) (3,3,4) (3,4,3) (3,5,2) (3,6,1) (3,7,0)$$ $$(4,0,6) (4,1,5) (4,2,4) (4,3,3) (4,4,2) (4,5,1) (4,6,0)$$ $$(5,0,5) (5,1,4) (5,2,3) (5,3,2) (5,4,1) (5,5,0)$$ $$(6,0,4) (6,1,3) (6,2,2) (6,3,1) (6,4,0)$$ $$(7,0,3) (7,1,2) (7,2,1) (7,3,0)$$
We conclude that the maximum number of students is $48$. If we would add a 49th student, say with arbitrary score $(3, 2, 6)$, we recognize that his/her values are equal or better then $(2,2,6)$, $(3,1,6)$ and $(3,2,5)$.