Arthur's code

Discrete Mathematics Level 5

In front of you is a locked door with a code panel. There are \(5\) buttons marked \(A, B, C, D\) and \(E\), and the code to unlock the door is a combination of at most \(4\) letters. The code panel remembers the last few buttons pressed, and if they match the correct code, the door will open. What is the shortest sequences of letters you can use to guarantee you have included the correct code?

This problem is shared by Arthur M., who obtained it from Pål Hermunn Johansen in an IMO training camp.

Details and assumptions

You do not know whether the code length \(n\) is \(1, 2, 3\) or \(4\), but the code panel does, and it remembers only the last \(n\) buttons pressed.

As an explicit example, if the code is the 3 letters \(AAB\), then the door will be unlocked right at the end of typing in the following sequence: \(BABBABAAB\).


Problem Loading...

Note Loading...

Set Loading...