Question

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.

Answer 1

Answer: The answers to all parts of this question are based on "automatic string". The condition is also provided which states that the string the machine outputs is the same string (4-digit string) which is fed to the machine as input.

Explanation: (a) The string will not remain automatic string if it contains a digit greater or equal to $5$. As we know that machine should print the same string which is fed into it. In this case the machine will insert a 0 in place of $5$. So the number is inserting a 0 when it is output by the counting machine. For example if we input $2152$ machine will print "$0120$" which shows that the digits are not the same as fed to the machine. If we take string $0702,$ which is given in the question, we see that machine prints out "$2010$" which means that number is inserting a 0 so automatic string cannot contain a digit greater than $5$

(b) The same answer as given in (a). For example the if we write $4220$ machine prints out "$1020$". So the automatic string cannot contain $4.$

(c) This is a bit tricky as machine count the digit $3$. Lets take an example string $3303$. the machine prints out "$1003$". It counts three BUT its not an automatic string because the string printed out is different from the string that was fed to the machine. So automatic string cannot contain $3.$

(d) Now we know that an automatic string cannot contain digits 3,4,5 and above. So it can contain digits 0,1 and 2 with 0 at the end as the automatic string cannot contain digit 3 or above.Lets take a few examples of strings with combinations of 0,1 and 2 to check if they are automatic strings.

• $1220$ the machine prints $1120$ which is not the same as fed into machine so its not an automatic string.
• $2020$ the machine prints out "$2020$". Its 2 times "$0$", 0 times "$1$",2 times "$2$" and 0 times "$3$" which is the same as fed to machine so $2020$ is an automatic string.
• $1210$ is an automatic string as the machine prints out "$1210$" which is the same string fed to machine.