Competition problem — Combinatorics

Library / /221 of 462

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,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.