© Zyanya Santuario, MATH+
Autor: Lukas Protz (MATH+)
Challenge
When the security elf realized what had happened, he was terrified. The Grinch had managed to sneak into the vault room, where all the Christmas presents are stored. Not only that, he had cracked the code to open the vault, changed it, and reprogrammed it in such a way that everything inside would be destroyed if incorrect codes were entered too many times.
The security elf begged the Grinch to give him the correct code, but the Grinch viciously replied: “Gather 100 elves and take them to the vault, then we can play a little game and maybe you can save your presents.”
The security elf immediately followed the Grinch’s instructions and returned to the vault with 100 elves.
“The rules are the following,” the Grinch says. “The code for the vault consists of 100 non-repeating characters. In total, there are 199 characters to choose from.” The Grinch points towards a panel with 199 buttons, each labeled with exactly one character. “There is also a screen that displays the previously entered code. It highlights characters that are in the correct position in green and characters that appear in the code but are not correctly positioned in blue.
Each of you only gets one chance to open the vault. Moreover, during the game you are not allowed to communicate with the other elves in any way. To make things more difficult, I will make sure that only the elf whose turn it is, can see the screen.
During your turn, the screen only shows the characters being entered — with no indication whether they are correct or not. Only after you finish entering all 100 characters and step away will the vault evaluate your attempt. The screen will then highlight the characters for the next elf to see. As soon as the correct code is entered, the vault opens.
If no one of you enters the correct code, all presents will be automatically destroyed. You get 10 elf-minutes (the standard time unit at the North Pole) to come up with a strategy.”
After quite some time of thinking, one elf comes up with an idea: “Let us make a list of all characters. The first elf will try the first 100 characters on the list. For each subsequent try we do the following: If a character is highlighted green, it remains in the same position. If a character is highlighted blue, it will be placed in the next free position to the right in the code. A free position is a position, where no green character was placed yet. A blue highlighted character at the end of the code might not have a free position to the right. In this case, the character is placed in the first free spot in the code, starting from the beginning.
The remaining positions will be filled with the next unused characters on the list. Each of these characters is inserted into the first still free position in the code, scanning from left to right.” Running out of time, the elves agree on this strategy and start playing the game.
Hopefully, the elves can save their presents! Let m be the minimal number of elves that would be needed to guarantee that the elves crack the code with their strategy. What is the units digit of m?
Possible Answers
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 0