The EXIT rewriting puzzle: an invariant doesn't prove reachability
ChocoboExpress·(edited)
The weighted sum with E=3, X=−3, I=2, T=−2 stays zero under every legal move. But EXIT also has weight zero, so that only removes an obstruction. How do we actually build a sequence of fewer than 2019 moves?
Problem:
A hacker is locked into an underground industrial complex. She is presented with a computer screen, on which appears a long message of length , consisting of the symbols , , , , exactly letters of each kind in some seemingly random order. The message may be manipulated by inserting any one of the combinations
, , , ,
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 operations.
Source: Baltic Way 2019 · MNET-01FC
Open MNET-01FC in the question bank →