Maths Olympiad Prep

Library / /52 of 61

Combinatorics Difficulty 6.9 National Olympiad Prove it Greece

On a blackboard we write in a line nn numbers, n40n \ge 40, each being equal to 11 or 1-1, such that:
(i) The sum of every 4040 successive numbers is equal to 00.
(ii) The sum of every 4242 successive numbers is not equal to 00.

We denote by Σn\Sigma_n the sum of the nn numbers on the blackboard. Find the greatest possible value of Σn\Sigma_n.

Solution

Let a1,a2,,ana_1, a_2, \dots, a_n be the numbers in a line on the blackboard. Since a1+a2++a40=0a_1 + a_2 + \dots + a_{40} = 0, it follows that half of the numbers a1,a2,,a40a_1, a_2, \dots, a_{40} are equal to 11 and the other half are equal to 1-1. Since a1+a2++a40+a41+a420a_1 + a_2 + \dots + a_{40} + a_{41} + a_{42} \neq 0 it follows that a41=a42=a{1,1}a_{41} = a_{42} = a \in \{-1, 1\}.

Similarly, a2+a3++a430a_2 + a_3 + \dots + a_{43} \neq 0 and hence a42=a43=a{1,1}a_{42} = a_{43} = a \in \{-1, 1\}. Proceeding in the same way we conclude that all numbers after a41a_{41} must be equal to aa.

Therefore, if n>60n > 60, the sum a22+a23++a61a_{22} + a_{23} + \dots + a_{61} has a41=a42==a61=aa_{41} = a_{42} = \dots = a_{61} = a, and hence 11 and 1-1 cannot have the same cardinality in the set. It means that a22+a23++a610a_{22} + a_{23} + \dots + a_{61} \neq 0, and that contradicts condition (i).

Hence the greatest value of nn is 6060.

The maximal value of Σn\Sigma_n is obtained when we have as many as possible numbers equal to 11. We remind that between the first 4040 numbers we must have 2020 numbers equal to 1-1. Hence the numbers equal to 11 can be at most 4040. Therefore Σn20\Sigma_n \le 20. In fact, we observe that maxΣn=20\max \Sigma_n = 20. It happens for
a1==a20=1, a21==a40=1 and a41==a60=1 a_1 = \dots = a_{20} = 1,\ a_{21} = \dots = a_{40} = -1 \text{ and } a_{41} = \dots = a_{60} = 1

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 reproduced verbatim; metadata (topic, difficulty) added by this project.