Problem 1015
In the 2016 Superfinal of this mathematical contest, there were as many questions as finalists. Each question was resolved by all but three competitors. The organizers noticed that if we took two competitors at random, they had never, together, solved all the questions.- 1A. How many finalists were there, at most, in 2016?
- 2A. How many finalists were there, at least, in 2017?
For this problem, the written program takes as input the constant N, number of responses (or candidates), and the constant P, number of incorrect answers per question. It searches if there is a configuration that respects the constraint that two candidates have solved all the questions (the questions 1A and 2A are in fact identical, only with different values of N and P), and if necessary displays the corresponding table (the lines (resp. columns) are the questions (or candidates) -- or the opposite -- and the gray boxes are the wrong answers).
Given the combinatorics (the program contains a double recursion between the candidates and the questions), I optimized this program by noting that there is always a symmetry between the candidates and the questions, and by computing gradually the number of correct answers per question, in order to avoid going through all the determined answers at the time of the test, to know if a candidate can answer correctly a question. Also, for the "critical" values of N (12, 13, 14), I pre-filled manually the beginning of the array after observing the pattern for smaller constant values. For question 2, the program terminates in 13 seconds for N = 12 and 4 uncorrect answers, in a few hours for N = 13 (solution drawn below) and in a few days for N = 14 (no solution).
Compared to the designers' solution, we can add that an upper bound for the number of questions (or candidates) is 1 + P (P − 1) (with P the number of incorrect answers per question): in the best case, this number P is equal to the number of incorrect answers per candidate. Thus, the maximum number of rows (candidates) in the array is (at most) 1 (arbitrary line) + P (number of wrong answers on the arbitrary line) × (P − 1) (number of remaining candidates who do not answer this question correctly): this is the multiplication because, at best, all the remaining bad answers are on different lines. For 5 wrong answers per question, this gives a maximum of 21 questions. Although this reasoning does not prove that this maximum is attainable, we intuitively feel that it is always the case (I think it is possible to create the optimal array by construction, on the first lines it is very easy).
The code is available here.
The solution for N = 13 and P = 4 is given here:
Given the combinatorics (the program contains a double recursion between the candidates and the questions), I optimized this program by noting that there is always a symmetry between the candidates and the questions, and by computing gradually the number of correct answers per question, in order to avoid going through all the determined answers at the time of the test, to know if a candidate can answer correctly a question. Also, for the "critical" values of N (12, 13, 14), I pre-filled manually the beginning of the array after observing the pattern for smaller constant values. For question 2, the program terminates in 13 seconds for N = 12 and 4 uncorrect answers, in a few hours for N = 13 (solution drawn below) and in a few days for N = 14 (no solution).
Compared to the designers' solution, we can add that an upper bound for the number of questions (or candidates) is 1 + P (P − 1) (with P the number of incorrect answers per question): in the best case, this number P is equal to the number of incorrect answers per candidate. Thus, the maximum number of rows (candidates) in the array is (at most) 1 (arbitrary line) + P (number of wrong answers on the arbitrary line) × (P − 1) (number of remaining candidates who do not answer this question correctly): this is the multiplication because, at best, all the remaining bad answers are on different lines. For 5 wrong answers per question, this gives a maximum of 21 questions. Although this reasoning does not prove that this maximum is attainable, we intuitively feel that it is always the case (I think it is possible to create the optimal array by construction, on the first lines it is very easy).
The code is available here.
The solution for N = 13 and P = 4 is given here:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
|XXXXX|XXXXX|XXXXX|XXXXX| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
|XXXXX| | | |XXXXX|XXXXX|XXXXX| | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
| |XXXXX| | |XXXXX| | |XXXXX|XXXXX| | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
| | |XXXXX| | |XXXXX| |XXXXX| |XXXXX| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
| | | |XXXXX| | |XXXXX|XXXXX| | |XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
|XXXXX| | | | | | | |XXXXX|XXXXX|XXXXX| | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
| | | |XXXXX| |XXXXX| | |XXXXX| | |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
| |XXXXX| | | | |XXXXX| | |XXXXX| |XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
| | |XXXXX| |XXXXX| | | | | |XXXXX|XXXXX| |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
| | |XXXXX| | | |XXXXX| |XXXXX| | | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
| | | |XXXXX|XXXXX| | | | |XXXXX| | |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
| |XXXXX| | | |XXXXX| | | | |XXXXX| |XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
|XXXXX| | | | | | |XXXXX| | | |XXXXX|XXXXX|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
- 1A. There were, in 2016, at most 7 finalists.
- 2A. There were, in 2017, at least 14 finalists.