Alex writes down a string with four digits. (Since this is a string, not a number, it can start with a $0.$ For example, Alex could write $0472.$) Alex then feeds this string into a special counting machine, which counts the number of times the digits $0,$ $1,$ $2,$ and $3$ appear in Alex's string, and then prints out the result. For example, suppose Alex wrote $2322.$ The machine counts the number of times $0$ appears (which is $0$ times), the number of times $1$ appears (which is also $0$ times), the number of times $2$ appears (which is $3$ times), and the number of times $3$ appears (which is $1$ time). So the machine prints out "$0031$". As another example, if Alex writes the string $0702,$ then the machine prints out "$2010$". Alex wants to see if there are any four-digit strings that they can write down, so that the string the machine prints out is the same as the string that they fed into the machine. We'll call this an automatic string.
(a) Prove that an automatic string cannot contain a digit that is $5$ or greater.
(b) Prove that an automatic string cannot contain a $4.$
(c) Prove that an automatic string cannot contain a $3.$
(d) Find all automatic strings.
If there is a digit of five or more, then the string cannot be automatic. With a digit that was five or higher appears any place in the string, say, 2352, then the machine prints out 0020. We want the digits to be the same after put through the machine, so we cannot have a number that inserts a 0 when put through the machine. We can use the same logic for a digit of 4. With a digit of 4, say 4110, then the machine prints out 1200. We want the digits to be the same after being put through the machine, so we cannot have a number that inserts a 0 when put through the machine, or else we would need to insert another number. So the automatic string cannot have a 4. The digit of 3 is a different case, because we can included 3 in an automatic string. If the machine prints out a 3 after a string is input, then we need to insert two more digits, which then does not give us an automatic string. For example, the machine turns 3303 into 1003, which is different from the number we put into the machine. So an automatic string cannot have a 3 either. We now know that we cannot have any digits 3 or higher, and we are now in a good place to find all automatic strings. Since the automatic string cannot have a 3 or higher, the number at the end will be 0, so the number at the start must be 1 or 2. If the number at the start is 1, then the automatic string cannot have any ones, so it would be a two. Therefore, the automatic string must look like 1XX0. The second digit is the number of ones. If the second digit is 2, then we will not have any room for any more digits of 1, so the second digit cannot be a 2. The second digit is 2 also is not possible. If the second digit is 2, then the third digit must be a 1, but after the string is put through the machine, then we get two ones. Now let 2 be the first digit. If the second digit is 2, then we have two twos, which does not leave room for ones, so this does not work. So let the third digit be 2. The automatic string now looks like 2X20. If X = 1, then we get 2120, which is not automatic, because there is one 1. If X = 0, then we get 2020 which is an automatic string. So the only automatic string is 2020.
