Maths Olympiad Prep

Library / Estonia — Open Contests /19 of 63

Estonia — Open Contests

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 2⋅3⋅4⋅5⋅6⋅72 \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 5040−1=50395040 - 1 = 5039.

Solution 2

Let us define x∗y=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 a∗ba * 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 ((1∗2)∗(3∗4))∗(5∗6)=(5∗19)∗41=119∗41=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.