Maths Olympiad Prep

Library / /5 of 5

, 2019

Combinatorics Difficulty 6.9 National olympiad Prove it Baltic Way

A hacker is locked into an underground industrial complex. She is presented with a computer screen, on which appears a long message of length 7272, consisting of the symbols EE, XX, II, TT, exactly 1818 letters of each kind in some seemingly random order. The message may be manipulated by inserting any one of the combinations
EXEX, XEXE, ITIT, TITI, IXIXIIXIXI
at an arbitrary place in the message. Such a combination may also be erased, wherever it may occur in the message.
The hacker may escape when the system is cracked, which happens when only the word `EXIT` is printed on the screen. Show that she may escape using less than 20192019 operations.

Solution

Let 18=n18 = n, so that the initial message has length 4n4n, with exactly nn symbols of each kind.
We first establish an invariant. Assign
E=3E = 3, X=3X = -3, I=2I = 2, T=2T = -2,
and let SS denote the sum of the values of all symbols appearing in the message. Initially, S=0S = 0, and the sum stays invariant under all the legal transformations.

Our next observation is that we may always insert or delete the combination TETET, for
{TI}{TEXI}{TETIXI}{TETEXIXI}{TETETIXIXI}{TETET}, \emptyset \mapsto \{TI\} \mapsto \{TEXI\} \mapsto \{TETIXI\} \mapsto \{TETEXIXI\} \mapsto \{TETETIXIXI\} \mapsto \{TETET\},
and this works also in reverse. Required are six operations.

To crack the system, first insert XE behind every I, and XE in front of every T:
IIXEI \mapsto IXE, \quad TXETT \mapsto XET.
This requires at most p1=4np_1 = 4n operations, after which the message has length at most 12n12n. It may now be considered a sequence of the four possible strings
EE, XX, IXIX, ETET.

Second, expand any single XX (not preceded by an II) into IXIXIXIXIXIX, and any single EE (not succeeded by a TT) into ETETETETETET:
XIXIXIXX \mapsto IXIXIX (one operation), EETETETE \mapsto ETETET (six operations).
This requires at most p2=12n6=72np_2 = 12n \cdot 6 = 72n operations, and the message now has length at most 72n72n.
It is at present reduced to some binary combination of the two strings
IXIX, ETET.

Third, effectuate all possible reductions
{ETIX}{EX}and{IXET}{IT}. \{ETIX\} \mapsto \{EX\} \mapsto \emptyset \quad \text{and} \quad \{IXET\} \mapsto \{IT\} \mapsto \emptyset.
There can be at most 18n18n such reductions, totalling p3=18n2=36np_3 = 18n \cdot 2 = 36n operations. The hacker will be left with a message of the types
ETETETETET \dots ET or IXIXIXIXIX \dots IX
or an empty screen. But since the invariant S=0S = 0, the screen must now, in fact, be empty.

Fourth, insert EXIT, using p4=2p_4 = 2 more operations. The number of operations was at most
p1+p2+p3+p4=4n+72n+36n+2=112n+2=11218+2=2018<2019. p_1 + p_2 + p_3 + p_4 = 4n + 72n + 36n + 2 = 112n + 2 = 112 \cdot 18 + 2 = 2018 < 2019.

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.