Maths Olympiad Prep

Library / /13 of 15

Combinatorics Difficulty 6.5 National olympiad Prove it Estonia

The numbers 00, 11, and 22 are written in the vertices of a triangle. One step involves increasing two of the three numbers by mm or decreasing one of the three numbers by nn. Is it possible that after some steps there are numbers 11, 22, and 33 (in an arbitrary order) written in the vertices if

a) m=3m = 3, n=6n = 6;
b) m=412m = 4\frac{1}{2}, n=6n = 6?

Solutions — 2

Solution 1

a) Both the step that involves increasing two of the numbers by 33 and the step that involves decreasing one of the numbers by 66 result in the sum of all three numbers being changed by 66. Thus the remainder when the sum of the three numbers is divided by 66 will always be the same regardless of the number of steps taken. But as the sums 0+1+20+1+2 and 1+2+31+2+3 give different remainders when divided by 66, it is impossible to reach the required end situation from the given initial situation.

b) First increase the second and the third numbers three times by 4124\frac{1}{2}; we end up with 00, 141214\frac{1}{2}, 151215\frac{1}{2} in the vertices. Now increase the first and the second numbers by 4124\frac{1}{2} and also increase the first and the third numbers by 4124\frac{1}{2}; so we end up with 99, 1919 and 2020 written in the three vertices, respectively. Finally decrease the first number once by 66 and the other two three times by 66, achieving the situation in question.

Solution 2

a) Consider one of the numbers. The remainder when this number is divided by 33 is the same regardless of the number of steps taken. Therefore, if we want to achieve the situation where 11, 22, 33 are located in the three vertices, the numbers 11 and 22 should stay in the same vertices where they were at the beginning and 33 has to be in the vertex where 00 was. Notice that two increasings are exactly cancelled out by one decreasing. Thus, the vertices where the numbers remain the same should have undergone an even number of increasings and the vertex where 00 is replaced by 33 should have been exposed to an odd number of increasings. Hence there should have been an odd number of increasings in total which is impossible since each increasing step influences the numbers in two vertices.

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