Problem

Source: ToT - 2001 Spring Junior A-Level #7

Tags: number theory unsolved, number theory



Alex thinks of a two-digit integer (any integer between $10$ and $99$). Greg is trying to guess it. If the number Greg names is correct, or if one of its digits is equal to the corresponding digit of Alex’s number and the other digit differs by one from the corresponding digit of Alex’s number, then Alex says “hot”; otherwise, he says “cold”. (For example, if Alex’s number was $65$, then by naming any of $64, 65, 66, 55$ or $75$ Greg will be answered “hot”, otherwise he will be answered “cold”.) (a) Prove that there is no strategy which guarantees that Greg will guess Alex’s number in no more than 18 attempts. (b) Find a strategy for Greg to find out Alex’s number (regardless of what the chosen number was) using no more than $24$ attempts. (c) Is there a $22$ attempt winning strategy for Greg?