3. Petya's favorite TV game is called "Sofa Lottery." During the game, viewers can send SMS messages with three-digit numbers containing only the digits $1, 2, 3$, and 4. At the end of the game, the host announces a three-digit number, also consisting only of these digits. An SMS is considered a winning one if the number in it differs from the host's number by no more than one digit (for example, if the host announced the number 423, then the messages 443 and 123 are winning, but 243 and 224 are not).

Petya wants to send as few messages as possible to ensure that at least one is definitely a winner. How many SMS messages will he have to send? (L. S. Korechkova)
Answer: 8.

Solution. An example of eight suitable SMS messages: 111, 122, 212, 221, 333, 344, 434, 443. Indeed, no matter what number the host names, it contains either at least two digits from the set $\{1,2\}$, or at least two from the set $\{3,4\}$. If the third digit is from the other set, we replace it with a digit from the same set as the other two, so that the sum of the digits is odd - this will definitely result in one of the specified options.

Now suppose there are fewer than 8 messages. Then some digit (for example, the digit 1) begins at most one message. Without loss of generality, let this message be 111 (if it exists at all). Consider the cases when the host names the numbers 122, 123, $124,132,133,134,142,143,144$. There are 9 of them, and for each of them, a separate message is needed (since the first digit is not 1, the second and third must be guessed).

Remark. The problem can be reformulated as: "What is the minimum number of rooks needed to cover a $4 \times 4 \times 4$ chessboard?". The general solution (for a board $n \times n \times n$) is provided, for example, in the comment at http://math.hashcode.ru/questions/52123.

Criteria. 4 points are given for the estimate, 3 points for the example. 1 point is given for the assertion that at least 7 SMS messages are necessary.