Library / Irish Mathematical Olympiad /125 of 236

Irish Mathematical Olympiad

Combinatorics Difficulty 5.8 AIME, harder Prove it Ireland

Let $N_1 = 12$ . The goal in this problem is to obtain the number $N_k = 21$ after performing a finite number of steps according to the following rules. In each step, the numbers $N_i$ and $N_{i+1}$ need to be in Shamrock Relation. Two numbers are said to be in Shamrock Relation if and only if
(a) one number is obtained from the other by replacing any block $X$ of consecutive digits by its triple repetition $XXX$ ; or
(b) one number is obtained from the other by replacing any connected block of the form $XXY$ with $YYY$ , where $X$ and $Y$ represent blocks of consecutive digits.
Is the goal of obtaining 21 achievable?

Solution

The answer is yes. Here is one way to proceed.

$12 = (12)$
use (a) with $N=12, X=12$
$121212 = (1)(21)(21)2$
use (b) with $M = 121212, X = 21, Y = 1$
$212112 = 212(1)(1)(2)$
use (b) with $N = 212112, X = 1, Y = 2$
$212211 = 2(1)(2)(2)11$
use (b) with $M = 212211, X = 2, Y = 1$
$222111 = (222)111$
use (a) with $M = 222111, X = 2$
$2111 = 2(111)$
use (a) with $M = 2111, X = 1$
21
goal achieved.

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.