Maths Olympiad Prep

Library / /31 of 31

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Estonia

Numbers 1,,2001, \dots, 200 are written on a blackboard in one line. Juku has to write in front of each number plus or minus sign so that for any positive integer n100n \le 100 the number itself and one of its multiples have different signs. Which numbers must he assign a minus sign in order to get the maximal possible value of the expression?

Solution

*Answer:* The numbers 51,,10051, \dots, 100.

If Juku writes a minus in front of the number 51,,10051, \dots, 100 and a plus in front of the others, then the conditions of the problem are satisfied: for 51n10051 \le n \le 100, the numbers nn and 2n2n have different signs; for n50n \le 50 there is at least one multiple of nn among the numbers 51,,10051, \dots, 100.

To show that this arrangement of the signs gives the maximal value of the expression,

consider an arbitrary arrangement of signs satisfying the conditions of the problem. Then always when 100n67100 \ge n \ge 67 and nn has a plus sign, 2n2n must have a minus sign. Also when 66n5166 \ge n \ge 51 and nn has a plus sign, then either 2n2n or 3n3n must have a minus sign. If we change all the pluses in front of the numbers nn with 100n51100 \ge n \ge 51 to minuses, and the minuses in front of the corresponding 2n2n or 3n3n to pluses, then changing minus to plus in front of mm corresponds to changing plus to minus in front of m2\frac{m}{2} or m3\frac{m}{3} or both. Since m2+m3<m\frac{m}{2} + \frac{m}{3} < m, the changes increase the value of the expression. Then we can also change all remaining minuses in front of the numbers 1,,501, \dots, 50 and 101,,200101, \dots, 200 to pluses, which also can only increase the value of the expression. This results in the arrangement of the signs described in the beginning. Hence this arrangement gives the maximal value of the expression.

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.