Maths Olympiad Prep

Library / /19 of 68

Combinatorics Difficulty 5.0 AIME Prove it Estonia

On the board there are numbers 11, 22, 33, 44, 55 and 66. In every step Juku deletes some two numbers aa and bb on the board and writes ab+a+bab + a + b on the board instead. He repeats such steps until there is only one number on the board. Find all possibilities what could be the last number on the board.

Solutions — 2

Solution 1

Since (a+1)(b+1)=c+1(a+1)(b+1) = c+1, where cc is a number that would be written on the board instead of aa and bb, the product of the numbers that are greater by 11 than the numbers on the board does not change in the process. In the beginning the product is 2345672 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 or 50405040. Consequently the only number that can be on the board in the end is 50401=50395040 - 1 = 5039.

Solution 2

Let us define xy=xy+x+yx * y = xy + x + y for every two numbers xx and yy, then in each step Juku substitutes some aa and bb with aba * b. The binary operation * is commutative and associative, due to which the final result is independent on the order the numbers are being deleted. Therefore in the end the board will contain one number that equals ((12)(34))(56)=(519)41=11941=5039((1 * 2) * (3 * 4)) * (5 * 6) = (5 * 19) * 41 = 119 * 41 = 5039.

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.