3. Vicky starts with a list $(a, b, c, d)$ of four digits. Each digit is $0,1,2$, or 3 . Vicky enters the list into a machine to produce a new list $(w, x, y, z)$. In the new list, $w$ is the number of $0 \mathrm{~s}$ in the original list, while $x, y$ and $z$ are the numbers of $1 \mathrm{~s}, 2 \mathrm{~s}$ and $3 \mathrm{~s}$, respectively, in the original list. For example, if Vicky enters $(1,3,0,1)$, the machine produces $(1,2,0,1)$.
(a) What does the machine produce when Vicky enters $(2,3,3,0)$ ?
(b) Vicky enters $(a, b, c, d)$ and the machine produces the identical list $(a, b, c, d)$. Determine all possible values of $b+2 c+3 d$.
(c) Determine all possible lists $(a, b, c, d)$ with the property that when Vicky enters $(a, b, c, d)$, the machine produces the identical list $(a, b, c, d)$.
(d) Vicky buys a new machine into which she can enter a list of ten digits. Each digit is $0,1,2,3,4,5,6,7,8$, or 9 . The machine produces a new list whose entries are, in order, the numbers of $0 \mathrm{~s}, 1 \mathrm{~s}, 2 \mathrm{~s}, 3 \mathrm{~s}, 4 \mathrm{~s}, 5 \mathrm{~s}, 6 \mathrm{~s}, 7 \mathrm{~s}, 8 \mathrm{~s}$, and $9 \mathrm{~s}$ in the original list. Determine all possible lists, $L$, of ten digits with the property that when Vicky enters $L$, the machine produces the identical list $L$.
3. (a) The initial list includes 1 digit equal to 0,0 digits equal to 1,1 digit equal to 2 , and 2 digits equal to 3 .
Therefore, the list produced by the machine is $(1,0,1,2)$.
(b) Suppose Vicky inputs the list $(a, b, c, d)$ and the machine outputs the identical list $(a, b, c, d)$. The fact that the output is ( $a, b, c, d$ ) tells us that the input consists $a 0 \mathrm{~s}, b 1 \mathrm{~s}, c 2 \mathrm{~s}$, and $d 3 \mathrm{~s}$.
Since the input consists of 4 digits, each equal to $0,1,2$, or 3 , then the sum of the number of $0 \mathrm{~s}(a)$, the number of $1 \mathrm{~s}(b)$, the number of $2 \mathrm{~s}(c)$, and the number of $3 \mathrm{~s}(d)$ in the input is 4 , and so $a+b+c+d=4$.
Since the input actually equals $(a, b, c, d)$, then the sum of the digits in the input is 4 . Now, we add up the digits of the input in a second way.
Since the output equals $(a, b, c, d)$, the input consists of $a 0 \mathrm{~s}, b 1 \mathrm{~s}, c 2 \mathrm{~s}$, and $d 3 \mathrm{~s}$. The $a$ 0s contribute $0 a$ to the sum of the digits, the $b$ 1s contribute $1 b$, the $c 2$ scontribute $2 c$, and the $d 3 \mathrm{~s}$ contribute $3 d$, and so the sum of the digits in the input also equals $0 a+1 b+2 c+3 d$.
Since the sum of the digits in the input is 4 , then $0 a+1 b+2 c+3 d=4$.
Therefore, $b+2 c+3 d=4$ for any input $(a, b, c, d)$ which produces the identical output $(a, b, c, d)$.
(c) We determine all possible lists $(a, b, c, d)$ that Vicky could input to produce the identical output $(a, b, c, d)$.
From (b), we must have $a+b+c+d=4$ and $b+2 c+3 d=4$.
Note that each of $a, b, c, d$ is a non-negative integer.
Since $b+2 c+3 d=4$, then $d=0$ or $d=1$. (If $d \geq 2$, the left side would be too large.) If $d=1$, then $b+2 c+3=4$ or $b+2 c=1$. Since $b$ and $c$ are non-negative integers, then we must have $b=1$ and $c=0$.
From the first equation, $a+b+c+d=4$ and so $a+1+0+1=4$ or $a=2$.
This would give $(a, b, c, d)=(2,1,0,1)$, but this input produces the output $(1,2,1,0)$, and so does not satisfy the requirements.
Thus, we cannot have $d=1$.
(We note here that if $(a, b, c, d)$ is a list with the desired property, then $a+b+c+d=4$ and $b+2 c+3 d=4$, but it is not necessarily true that if $a+b+c+d=4$ and $b+2 c+3 d=4$, then the list $(a, b, c, d)$ has the required property.)
Since $d$ cannot be 1 , then $d=0$, giving $a+b+c=4$ and $b+2 c=4$.
Using the second equation, $c=0$ or $c=1$ or $c=2$.
If $c=0$, then $b=4$. However, none of the digits can be larger than 3 , so this is not possible.
If $c=1$, then $b=2$. In this case, $a+2+1=4$ and so $a=1$, giving $(a, b, c, d)=(1,2,1,0)$.
Using this list as input gives output $(1,2,1,0)$, as required.
If $c=2$, then $b=0$. In this case, $a+0+2=4$ and so $a=2$, giving $(a, b, c, d)=(2,0,2,0)$.
Using this list as input gives output $(2,0,2,0$ ), as required.
We have exhausted all possibilities, so the lists that Vicky could input that produce identical output are $(1,2,1,0)$ and $(2,0,2,0)$.
(d) We show that there is exactly one such list $L$.
First, we model the work from (b) to determine similar equations that will help with our work.
Suppose Vicky enters the list $\left(a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}\right)$ and the machine produces the identical list $\left(a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}\right)$.
(Here, each of $a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}$ is a digit between 0 and 9 inclusive. The smaller numbers set below the main line of text are called subscripts and are sometimes used to give more meaningful names to unknown quantities.)
The fact that the output is ( $\left(a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}\right)$ tells us that the input includes $a_{0} 0 \mathrm{~s}$ and $a_{1} 1 \mathrm{~s}$ and $a_{2} 2 \mathrm{~s}$, and so on. Since the input consists of a total of 10 digits, then $a_{0}+a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}=10$.
This means that the sum of the digits in the input is 10 . We $a_{1} 1 \mathrm{~s}, a_{2} \mathrm{2s}$, and so on.
We can add up the digits of the input in a second way by saying that the $a_{0} 0$ s contribute $0 a_{0}$ to the sum of the Thus, the sum of the digits, the $a_{1} 1$ s contribute $1 a_{1}$, the $a_{2} 2 \mathrm{~s}$ contribute $2 a_{2}$, and so on, Thus, the sum of the digits of the input equals
$$
0 a_{0}+1 a_{1}+2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5}+6 a_{6}+7 a_{7}+8 a_{8}+9 a_{9}
$$

Since we already know that the sum of the digits in the input is 10 , then
$$
0 a_{0}+1 a_{1}+2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5}+6 a_{6}+7 a_{7}+8 a_{8}+9 a_{9}=10
$$

Now, we determine the possible lists $L$ that satisfy the desired condition.
Suppose that $a_{0}=k$. This is the first digit in the input and the first digit in the output, Since the output $L$ includes $a_{0}=k$, then by the definition of $a_{0}$, the input $L$ must include $k$ digits equal to 0 .
Note that $k \neq 0$, since if $k=0$, there would be at least 1 digit equal to 0 in the input, so the $k$ in the output would be at least 1 , which would contradict $k=0$.
Since $1 a_{1}+2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5}+6 a_{6}+7 a_{7}+8 a_{8}+9 a_{9}=10$, then at most 4 of the digits $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}$ can be non-zero. This is true because if 5 of these digits were non-zero, the five non-zero terms in the sum on the left side would be at least $1+2+3+4+5$ which is larger than 10 .
Therefore, at most 4 of the digits in $L$ after $a_{0}=k$ are non-zero, so at least 5 of the digits in $L$ after $a_{0}=k$ equal 0 , which tells us that $k \geq 5$.
If $k=5$, then the last 9 digits of $L$ include exactly 5 zeros, which means that the last 9 digits include exactly 4 non-zero digits.
Since $1 a_{1}+2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5}+6 a_{6}+7 a_{7}+8 a_{8}+9 a_{9}=10$ and the sum of the 4 non-zero terms is at least $1+2+3+4=10$, then the sum of the 4 non-zero terms must be exactly $1+2+3+4=10$.
This means that $a_{1}=a_{2}=a_{3}=a_{4}=1$ and $a_{5}=a_{6}=a_{7}=a_{8}=a_{9}=0$.
But an input $(5,1,1,1,1,0,0,0,0,0$ ) gives output $(5,4,0,0,0,1,0,0,0,0)$ which is not equal to the input.
Thus, $k \neq 5$, and so $k \geq 6$.
Since $a_{0}=k$ and $k \geq 6$, then the input $L$ includes at least one digit equal to $k$, so the output $L$ tells us that $a_{k} \neq 0$.
Since $1 a_{1}+2 a_{2}+3 a_{3}+4 a_{4}+5 a_{5}+6 a_{6}+7 a_{7}+8 a_{8}+9 a_{9}=10$, then $k a_{k} \leq 10$.
Since $k \geq 6$, then $a_{k} \leq 1$ (otherwise, $k a_{k}>10$ ). Since $a_{k} \neq 0$, then $a_{k}=1$.
Consider $a_{1}$ next.
Since $a_{k}=1$, this fact from the input $L$ tells us that $a_{1} \geq 1$ in the output $L$.
If $a_{1}=1$, then the input $L$ would include at least two $1 \mathrm{~s}\left(a_{1}\right.$ and $a_{k}$ ), so in the output version of $L, a_{1} \geq 2$, which disagrees with the input.
Therefore, $a_{1} \neq 1$, and so $a_{1} \geq 2$.
Since we know that $a_{0}=k$ and $k \geq 6$ and $a_{0}+a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}=10$,
then $a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9} \leq 4$.
Since $a_{k}=1$ already (and $k \geq 6$ ), then we must have $a_{1} \leq 3$.
If $a_{1}=3$, then the $a_{1}$ in the output would tell us that the input $L$ includes at least three 1s, which would give $a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9} \geq 3+1+1+1=6$, which is not possible.
Since $2 \leq a_{1} \leq 3$ and $a_{1} \neq 3$, then $a_{1}=2$.
Therefore, the input $L$ includes at least one 2 , and so the output $L$ has $a_{2} \geq 1$.
We know that $a_{1}=2$ and $a_{2} \geq 1$ and $a_{k}=1$ and $a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9} \leq 4$.
Thus, it must be the case that $a_{2}=1$, otherwise $a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}$ would be too large.
Since there are exactly 4 non-zero digits, we can also conclude that all of the entries other than $a_{0}, a_{1}, a_{2}$, and $a_{k}$ must equal 0 .
Since $a_{0}+a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}=10$, then
$$
k=a_{0}=10-\left(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}\right)=10-(2+1+1)=6
$$

Thus, the only possible input $L$ that produces the same output $L$ is $(6,2,1,0,0,0,1,0,0,0)$.
This list includes six 0 s, two 1 s, one 2 , and one 6 , so the output matches the input. Therefore, there is exactly one list $L$ that can be input to produce the same output. This list is $(6,2,1,0,0,0,1,0,0,0$.