Maths Olympiad Prep

Library / /16 of 24

Combinatorics Difficulty 6.8 National Olympiad Prove it Italy

Problem:

In a mathematics competition, 3 problems are proposed, each of which is graded with an integer score between 0 and 7 (inclusive). It is known that, however two competitors are chosen, there is at most one problem on which they obtained the same score (for example, there are no two competitors whose scores on the three problems are 7, 1, 2 for the first and 7, 5, 2 for the second, but there could be two competitors whose scores are 7, 1, 2 and 7, 2, 1). What is the maximum number of participants in the competition?

Solutions — 2

Solution 1

Solution:

The answer is 64. We denote by p1,p2,p3p_{1}, p_{2}, p_{3} the scores that a competitor can obtain on problems 1,2,31, 2, 3, respectively. First of all we observe that certainly the number of competitors cannot exceed 64. Indeed, considering just the first two problems, the possible pairs of scores (p1,p2)\left(p_{1}, p_{2}\right) relative to these two problems are 82=648^{2} = 64, and therefore, if we want different competitors to correspond to different pairs, the number of competitors cannot exceed 64.

Secondly, however, with 64 competitors the required result can be achieved. Indeed, imagine that the 64 competitors obtain, on the first two problems, all 64 available pairs (p1,p2)\left(p_{1}, p_{2}\right) of scores. It is certainly possible, since the scores range between 0 and 7, that all competitors obtain a total score (that is, the sum of the scores p1+p2+p3p_{1} + p_{2} + p_{3}) divisible by 8. In this case there are no two competitors who have the same score on two different problems. Indeed, if two competitors have, for example, equal scores on problem 1 and on problem 3, then, by difference, they must also have an equal score on problem 2, contradicting the assumption made. A completely analogous argument applies to the case in which two competitors have equal scores on problem 2 and on problem 3.

Solution 2

Solution:

The first part of this solution coincides with that of the previous solution. For the second part, we show that 64 competitors can satisfy the required condition. We already know that, on the first two problems, our 64 competitors must obtain all 64 possible combinations of scores. We can therefore construct an 8×88 \times 8 table whose rows correspond to the scores of the first problem, and whose columns correspond to those of the second. Each cell of the table will correspond to one of the competitors, and in that cell we want to write the score he obtains in the third problem. The requirement of the exercise then becomes that no row and no column contain two equal numbers. The following table, for example, satisfies this requirement.

01234567
001234567
112345670
223456701
334567012
445670123
556701234
667012345
770123456

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.