USA-MTS problem
Alex is trying to open a lock whose code is a sequence that is three letters long, with each of the letters being one of possibly repeated. The lock has three buttons, labeled . When the most recent button-presses form the string, the lock opens. What is the minimum number of total button presses Alex needs to be sure to open the lock?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The answer is 2 9 and the following is a sequence of presses:
A A A C C C B C C A C B B C B A C A B C A A B B B A B A A
There are 3 × 3 × 3 = 2 7 different strings with each letter being one of A , B , C . All 2 7 of these strings appear consecutively in the above sequences of presses.
Each press of the button corresponds to attempting at most one more string, namely the one formed by the previous three presses. No string can be attempted after the first two presses. Therefore, the first time that all 2 7 strings can be tried on the lock is after 2 7 + 2 = 2 9 presses of the button, so 2 9 is indeed the minimum.