Maths Olympiad Prep

Library / /4 of 10

Combinatorics Difficulty 8.1 Shortlist Prove it Netherlands

Let n1n \ge 1 be an integer. Ruben takes a test with nn questions. Each question on this test is worth a different number of points. The first question is worth 11 point, the second question 22, the third 33 and so on until the last question which is worth nn points. Each question can be answered either correctly or incorrectly. So an answer for a question can either be awarded all, or none of the points the question is worth. Let f(n)f(n) be the number of ways he can take the test so that the number of points awarded equals the number of questions he answered incorrectly.
Do there exist infinitely many pairs (a,b)(a, b) with a<ba < b and f(a)=f(b)f(a) = f(b)?

Solution

For the first few values of ff, note that f(1)=0f(1) = 0, f(2)=f(3)=f(4)=1f(2) = f(3) = f(4) = 1, f(5)=f(6)=2f(5) = f(6) = 2, f(7)=f(8)=3f(7) = f(8) = 3, f(9)=f(10)=5f(9) = f(10) = 5. We claim that for n11n \ge 11, f(n)f(n) is strictly increasing as a function of nn. Therefore there is only a finite number of pairs as in the problem.

We view a way of taking a test as a subset of {1,2,,n}\{1, 2, \dots, n\} by taking the set of numbers of questions that are answered correctly. We say that a subset SnS_n of {1,2,,n}\{1, 2, \dots, n\} is an nn-equally correct set if the sum of all elements of SnS_n is equal to the number of elements in the complement of SnS_n in {1,2,,n}\{1, 2, \dots, n\}. So by definition, f(n)f(n) is the number of nn-equally correct sets. Note that a subset SnS_n of {1,2,,n}\{1, 2, \dots, n\} is nn-equally correct if and only if the sum of all elements of SnS_n plus the number of elements of SnS_n equals nn.

We first claim that f(n)f(n) is non-decreasing for n1n \ge 1. Let Sn1S_{n-1} be an (n1)(n-1)-equally correct set. Then adding 11 to the largest element of Sn1S_{n-1} gets us a subset SnS_n of {1,2,,n}\{1, 2, \dots, n\}. This subset has as many elements as Sn1S_{n-1} and has sum 11 higher than the sum of Sn1S_{n-1}, which is therefore an nn-equally correct set. This procedure defines an injective map FnF_n from the set of (n1)(n-1)-equally correct sets to the set of nn-equally correct sets for all n2n \ge 2. Therefore f(n)f(n1)f(n) \ge f(n-1) for all n2n \ge 2.

We now show that, for n11n \ge 11, there exists an nn-equally correct set that is not in the image of FnF_n. Note that an nn-equally correct set of which the two largest elements differ by exactly 11 cannot be in the image of FnF_n; the reason is that a set in this image is one that is obtained by adding 11 to the largest element of a subset of {1,2,,n1}\{1, 2, \dots, n-1\}. If n=2k+1n = 2k + 1 with k5k \ge 5, then S={1,k2,k1}S = \{1, k-2, k-1\} is nn-equally correct, as 1+(k2)+(k1)+S=2k+1=n1 + (k-2) + (k-1) + |S| = 2k + 1 = n. Similarly, if n=2kn = 2k with k6k \ge 6, then S={2,k3,k2}S = \{2, k-3, k-2\} is nn-equally correct, because 2+(k3)+(k2)+S=2k=n2 + (k-3) + (k-2) + |S| = 2k = n. We conclude that f(n)>f(n1)f(n) > f(n-1) for all n11n \ge 11. \square

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 and solution reproduced as published; topic and difficulty added by this site.