April 2025
The list \((1,1,0,0,0)\) is not smooth. To see this, we apply \(f\) fifteen times. Setting \(L=(1,1,0,0,0)\), we have \[\begin{align*} f(L) &= (0,1,0,0,1) \\ f^2(L) &= (1,1,0,1,1) \\ f^3(L) &= (0,1,1,0,0) \\ f^4(L) &= (1,0,1,0,0) \\ f^5(L) &= (1,1,1,0,1) \\ f^6(L) &= (0,0,1,1,0) \\ f^7(L) &= (0,1,0,1,0) \\ f^8(L) &= (1,1,1,1,0) \\ f^9(L) &= (0,0,0,1,1) \\ f^{10}(L) &= (0,0,1,0,1) \\ f^{11}(L) &= (0,1,1,1,1) \\ f^{12}(L) &= (1,0,0,0,1) \\ f^{13}(L) &= (1,0,0,1,0) \\ f^{14}(L) &= (1,0,1,1,1) \\ f^{15}(L) &= (1,1,0,0,0)\end{align*}\] and so \(f^{15}(1,1,0,0,0)=(1,1,0,0,0)\). This means no matter how many times \(f\) is applied, the list of lists above will repeat every fifteen applications, so we will never arrive at the list of five \(0\)s.
The list \((1,1,0,0,0,0,0)\) is not smooth. Setting \(L=(1,1,0,0,0,0,0)\), we have \[\begin{align*} f(L)&=(0,1,0,0,0,0,1)\\ f^2(L)&=(1,1,0,0,0,1,1) \\ f^3(L)&=(0,1,0,0,1,0,0)\\ f^4(L)&=(1,1,0,1,1,0,0) \\ f^5(L)&=(0,1,1,0,1,0,1)\\ f^6(L)&=(1,0,1,1,1,1,1) \\ f^7(L)&=(1,1,0,0,0,0,0)\end{align*}\] which means \(f^7(1,1,0,0,0,0,0)=(1,1,0,0,0,0,0)\). As with the previous example, applying \(f\) repeatedly to \((1,1,0,0,0,0,0)\) will yield the original list every seven applications and no list of \(0\)s in this list of lists. Thus, the list of seven \(0\)s will never appear, so \((1,1,0,0,0,0,0)\) is not smooth.
There are two important observations to make from part (a).
Observation 1: It appears that if every integer in a list \(L\) is either \(0\) or \(1\), then every integer in \(f(L)\) is also either \(0\) or \(1\). Indeed, if every integer in \(L\) is either \(0\) or \(1\), then every integer in \(f(L)\) is one of \(|0-1|\), \(|1-0|\), \(|0-0|\), or \(|1-1|\), which all simplify to either \(0\) or \(1\). We will use this observation in later parts of this problem as well.
Observation 2: If \(L\) is a list in which every integer is equal to either \(0\) or \(1\), then it appears that \(f(L)\) has an even number of integers equal to \(1\).
Let us verify the second observation. We suppose \(L=(a_1,a_2,\dots,a_n)\) is such that \(a_k=0\) or \(a_k=1\) for each \(k = 1,2,\ldots,n\). The number of entries equal to \(1\) in the list \(f(L)\) is equal to the number of times that the sequence \[a_1,a_2,a_3,a_4,\dots,a_{n-2},a_{n-1},a_n,a_1\] changes value. For example, if \((a_1,a_2,a_3,a_4,a_5,a_6)=(0,0,1,1,0,1)\), then the sequence above changes value going from \(a_2\) to \(a_3\), \(a_4\) to \(a_5\), \(a_5\) to \(a_6\), and \(a_6\) back to \(a_1\). If the sequence above changed value an odd number of times, then its first and last integers would be different. However, the sequence starts and ends with \(a_1\), so it must change value an even (possibly zero) number of times. Hence, \(f(L)\) has an even number of integers equal to \(1\).
We now suppose \(n\) is odd with \(n\geq 3\) and that \(L=(a_1,a_2,\dots,a_n)\) is a list of nonnegative integers having the following three properties:
For every \(k\) in \(\{1,\ldots,n\}\), either \(a_k=0\) or \(a_k=1\).
There are an even number of indices \(k\) with \(a_k=1\).
\(a_k=1\) for at least one \(k\).
We will show that \(f(L)=(b_1,b_2,\dots,b_n)\) also satisfies properties (i), (ii), and (iii) (with "\(a\)" replaced by "\(b\)").
Since \(L\) satisfies property (i), Observation \(1\) and Observation \(2\) imply that \(f(L)\) satisfies properties (i) and (ii). To see that \(f(L)\) satisfies property (iii), first observe that \(n\) is odd, so properties (i) and (ii) of \(L\) imply that there are an odd number of \(k\) for which \(a_k=0\). In particular, this means the number of \(k\) for which \(a_k=0\) is not 0, so there is at least one integer in \(L\) that is equal to \(0\). Since \(L\) has at least one \(0\) and at least one \(1\) (by property (iii) of \(L\)), it must change values at some point. This will give rise to at least one \(1\) in \(f(L)\). Therefore, \(f(L)\) satisfies condition (iii).
Let \(n\) be an odd positive integer and consider the list \(L=(a_1,a_2,\dots,a_n)\) where \(a_1=a_2=1\) and \(a_k=0\) for \(k\geq 3\). Then \(L\) has properties (i), (ii), and (iii). Therefore, by the above reasoning, \(f(L)\) has properties (i), (ii), and (iii). In turn, this implies \(f^2(L)\) has properties (i), (ii), (iii), and so on. That is, \(f^m(L)\) has properties (i), (ii), and (iii) for all \(m\geq 0\). Property (iii) ensures that \(f^m(L)\) has at least one integer that does not equal \(0\), so this means \(f^m(L)\) is not the list of \(0\)s for any \(m\). Therefore, \(L\) is not smooth.
We will show that a list \((a,b,c)\) is smooth exactly when \(a=b=c\). Since each of \(a\), \(b\), and \(c\) is between \(1\) and \(100\) inclusive, this will give a total of \(100\) smooth lists.
Notice that if \(a=b=c\), then \(f(a,b,c)=(0,0,0)\), so \((a,b,c)\) is smooth. What needs to be verified is that if \((a,b,c)\) is smooth, then \(a=b=c\).
To start, we will establish a seemingly much less ambitious claim:
Fact 1: If \((a,b,c)\) is smooth, then \(a\), \(b\), and \(c\) have the same parity. That is, \(a\), \(b\), and \(c\) are either all even or all odd. (The parity of a number refers to whether it is even or odd.)
To establish this claim, we will assume that \(a\), \(b\), and \(c\) do not all have the same parity and deduce that \((a,b,c)\) is not smooth.
Suppose \(a\), \(b\), and \(c\) are nonnegative integers at least one of which is even and at least one of which is odd. Consider the list \[f(a,b,c)=(|a-b|,|b-c|,|c-a|).\] Since there are three integers in the list \((a,b,c)\), at least two of \(a\), \(b\), and \(c\) must have the same parity (are both even or both odd). This means at least one of the integers \(|a - b|, |b - c|\), or \(|c - a|\) is even. On the other hand, we are assuming at least two of \(a\), \(b\), and \(c\) have different parity (one is even and one is odd), so this means \(f(a,b,c)\) has at least one odd integer. Applying this reasoning repeatedly, it follows that if \((a,b,c)\) has at least one even integer and at least one odd integer, then \(f^m(a,b,c)\) has this property for every \(m\geq 1\). This means \(f^m(a,b,c)\) is never equal to \((0,0,0)\), so \((a,b,c)\) cannot be smooth.
We now know that if \((a,b,c)\) is smooth, then \(a\), \(b\), and \(c\) have the same parity. Since the difference between two integers of the same parity is even, this actually implies that if \((a,b,c)\) is smooth, then the integers in \(f(a,b,c)\) are all even. This will be important in finishing the argument, but we also need the following fact that allows for a sort of “reduction” in a smooth list having a common factor among its integers.
Fact 2: Suppose \(a_1,a_2,\dots,a_n\) are nonnegative integers with a common factor \(r>0\). Then the list \((a_1,a_2,\dots,a_n)\) is smooth if and only if the list \(\left(\dfrac{a_1}{r},\dfrac{a_2}{r},\dots,\dfrac{a_n}{r}\right)\) is smooth.
Suppose \(f(a_1,a_2,\dots,a_n)=(b_1,b_2,\dots,b_n)\). By the definition of \(f\), this means \[(b_1,b_2,\dots,b_n)=(|a_1-a_2|,|a_2-a_3|,\dots,|a_n-a_1|)\] Using properties of absolute values and that \(r>0\), we have \[\begin{align*} f\left(\dfrac{a_1}{r},\dfrac{a_2}{r},\dots,\dfrac{a_n}{r}\right) &= \left(\left|\dfrac{a_1}{r}-\dfrac{a_2}{r}\right|,\left|\dfrac{a_2}{r}-\dfrac{a_3}{r}\right|,\dots,\left|\dfrac{a_n}{r}-\dfrac{a_1}{r}\right|\right) \\ &= \left(\dfrac{|a_1-a_2|}{r},\dfrac{|a_2-a_3|}{r},\dots,\dfrac{|a_n-a_1|}{r}\right) \\ &= \left(\dfrac{b_1}{r},\dfrac{b_2}{r},\dots,\dfrac{b_n}{r}\right).\end{align*}\] In words, dividing each integer in a list by a common factor and then applying \(f\) has the same effect as applying \(f\) and then dividing each integer in the resulting list by that same common factor. Applying this fact repeatedly, it follows that if for some \(m\geq 1\) we have \(f^m(a_1,a_2,\dots,a_n)=(c_1,c_2,\dots,c_n)\), then \[f^m\left(\dfrac{a_1}{r},\dfrac{a_2}{r},\dots,\dfrac{a_n}{r}\right)=\left(\dfrac{c_1}{r},\dfrac{c_2}{r},\dots,\dfrac{c_n}{r}\right)\] Since \(r\neq 0\), \(c_k=0\) if and only if \(\dfrac{c_k}{r}=0\), and this is true for any \(1\leq k\leq n\). This means \(f^m(a_1,a_2,\dots,a_n)\) is the list of all \(0\)s if and only if \(f^m\left(\dfrac{a_1}{r},\dfrac{a_2}{r},\dots,\dfrac{a_n}{r}\right)\) is the list of all \(0\)s. This completes the proof of the fact.
We established earlier that if \((a,b,c)\) is smooth, then the integers in \(f(a,b,c)\) are all even. To use the above fact, we need a way of keeping track of the number of common factors of \(2\) among the integers in \(f(a,b,c)\).
To help with this, define a function \(E\) on the nonzero integers by \(E(a)=r\) where \(r\) is the largest power of \(2\) that is a divisor of \(a\). For example, \(E(12)=4\) since \(4\) is a divisor of \(12\), but \(8\) is not and neither is any higher power of \(2\). Also, \(E(n)=1\) for any odd number \(n\) since \(2^0=1\) is the largest power of \(2\) that divides any odd number.
Here are three features of the function \(E\) that we will use. Their proofs are left as an exercise.
(F1): \(\dfrac{a}{E(a)}\) is an odd integer.
(F2): If \(r\) is a power of \(2\) and \(\dfrac{a}{r}\) is an odd integer, then \(r=E(a)\).
(F3): \(E(a)=E(-a)=E(|a|)\).
Suppose \(L=(a,b,c)\) is smooth and that \(a\), \(b\), and \(c\) are all even and not all \(0\). We let \(r=\min\{E(a),E(b),E(c)\}\) and set \(K=\left(\dfrac{a}{r},\dfrac{b}{r},\dfrac{c}{r}\right)\). If some of \(a\), \(b\), and \(c\) are \(0\), then some of \(E(a)\), \(E(b)\), and \(E(c)\) are undefined. In this situation, \(r\) is the minimum of the values that are defined.
Because of how \(r\) is chosen, we will have that \(\dfrac{a}{r}\), \(\dfrac{b}{r}\), and \(\dfrac{c}{r}\) are all integers. Also, since \(r=E(a)\) or \(r=E(b)\) or \(r=E(c)\), at least one integer in \(K\) must be odd by F\(1\). We are assuming that \(L\) is smooth, so Fact \(2\) implies that \(K\) is smooth as well. Thus, \(K\) is a smooth list with at least one odd integer, which means that all three of the integers in \(K\) must be odd by Fact \(1\). By F\(2\), this means \(E(a)=E(b)=E(c)\). We have established the following: If \((a,b,c)\) is smooth with \(a\), \(b\), and \(c\) all even and not all \(0\), then \(E(a)=E(b)=E(c)\).
Next, suppose \(L=(a,b,c)\) is smooth and that \(a\), \(b\), and \(c\) are all odd. We want to prove that \(a=c\). To do this, we will suppose \(a\neq c\) and deduce a contradiction. Since \(a\), \(b\), and \(c\) are all odd, \(f(L)=(|a-b|,|b-c|,|c-a|)\) has all even integers and since \(a\neq c\), \(|c-a|\neq 0\). Also, \(L\) is smooth, so \(f(L)\) is smooth. From the previous paragraph, this means \(E(|a-b|)=E(|b-c|)=E(|c-a|)\). By F3 above, \(E(a-b)=E(b-c)=E(c-a)\). Let this common value be \(r\). Then by F\(1\), \(\dfrac{a-b}{r}\) and \(\dfrac{b-c}{r}\) are both some odd integer \(m\), so \(\dfrac{a-b}{r}+\dfrac{b-c}{r}=2m\). Then \[\dfrac{a-c}{r}=\dfrac{a-b}{r}+\dfrac{b-c}{r}=2m,\] so \(a-c=2rm\). Therefore, \(2r\) is a divisor of \(a-c\). Since \(r\) is a power of \(2\), so is \(2r\), and this means \(E(a-c)\geq 2r>r\). However, \(E(a-c)=r\), so this is a contradiction. We are forced to conclude that our assumption \(a\neq c\) is false, implying \(a=c\). By a similar argument, it can be shown that \(b=c\), so \(a=b=c\).
We have now established the following: If \((a,b,c)\) is smooth with \(a\), \(b\), and \(c\) all odd, then \(a=b=c\).
We now return to (and finish) the case when \((a,b,c)\) is smooth with \(a\), \(b\), and \(c\) all even.
Suppose again that \((a,b,c)\) is smooth and that \(a\), \(b\), and \(c\) are all even. If \(a=b=c=0\), then there is nothing to prove. Otherwise, we know \(E(a)=E(b)=E(c)=r\), so \(\dfrac{a}{r}\), \(\dfrac{b}{r}\), and \(\dfrac{c}{r}\) are all odd. Since \(\left(\dfrac{a}{r},\dfrac{b}{r},\dfrac{c}{r}\right)\) is also smooth, \(\dfrac{a}{r}=\dfrac{b}{r}=\dfrac{c}{r}\), from which it follows that \(a=b=c\).
Therefore, if \((a,b,c)\) is smooth, then \(a=b=c\).
You may be getting the idea that keeping track of the parity of the elements in a list is of great importance in this problem. In the previous part, we showed that if \((a,b,c)\) is smooth, then the integers in \(f(a,b,c)\) are all even.
The critical observation of this and the next part is that if \(a\), \(b\), \(c\), and \(d\) are any positive integers, then there is some \(m\) for which the integers in \(f^m(a,b,c,d)\) are all even. If you are familiar with modular arithmetic, you may be able to streamline most of the upcoming work. However, this solution will not assume any such knowledge.
For a list \((a_1,a_2,\dots,a_n)\) of nonnegative integers, define \[g(a_1,a_2,\dots,a_n)=(a_1+a_2,a_2+a_3,a_3+a_4,\cdots,a_{n-1}+a_n,a_n+a_1).\] For \(m\geq 2\), we define \(g^m(a_1,a_2,\ldots,a_n)\) to be the list attained from \((a_1,a_2,\ldots,a_n)\) by applying \(g\) repeatedly \(m\) times.
The function \(g\) looks similar to \(f\), but it lacks absolute values and involves addition rather than subtraction. While \(g\) and \(f\) are genuinely different functions, \(g\) can be used to keep track of the parity of the integers in lists produced by applying \(f\). More precisely, suppose \((a_1,a_2,\dots,a_n)\) and \((b_1,b_2,\dots,b_n)\) are lists of nonnegative integers with the property that for each \(1\leq k\leq n\), \(a_k\) and \(b_k\) have the same parity. If we set \(f(a_1,a_2,\dots,a_n)=(c_1,c_2,\dots,c_n)\) and \(g(b_1,b_2,\dots,b_n)=(d_1,d_2,\dots,d_n)\), then for each \(k\) with \(1\leq k\leq n\), \(c_k\) and \(d_k\) have the same parity as well. To see this, observe that for \(k\leq n\), we have \(c_k=|a_k-a_{k+1}|\) and \(d_k=b_k+b_{k+1}\) (where we take the convention that \(a_{n+1}=a_1\) and \(b_{n+1}=b_1\)). If \(c_k=a_k-a_{k+1}\), then \(c_k+d_k=(a_k+b_k)-(a_{k+1}-b_{k+1})\). By the assumptions on \((a_1,a_2,\dots,a_n)\) and \((b_1,b_2,\dots,b_n)\), \(a_k+b_k\) and \(a_{k+1}-b_{k+1}\) are both even, so \(c_k+d_k\) is even. This means \(c_k\) and \(d_k\) must have the same parity. Similarly, if \(c_k=a_{k+1}-a_k\), then \(c_k\) and \(d_k\) have the same parity.
The above paragraph shows that the integers in \(g(a_1,a_2,\dots,a_n)\) have the same parities as the corresponding integers in \(f(a_1,a_2,\dots,a_n)\). Applying the fact again, we have that the integers in \(g^2(a_1,a_2,\dots,a_n)\) have the same parities as the corresponding integers in \(f^2(a_1,a_2,\dots,a_n)\). This can be repeated to get that the integers in \(g^m(a_1,a_2,\dots,a_n)\) have the same parities as the corresponding integers in \(f^m(a_1,a_2,\dots,a_n)\) for all \(m\geq 2\).
We can use this to prove that the integers in \(f^4(a,b,c,d)\) are all even for any nonnegative integers \(a\), \(b\), \(c\), and \(d\). Consider an arbitrary list \((a,b,c,d)\) of four nonnegative integers and compute \(g^4(a,b,c,d)\): \[\begin{align*} &g^4(a,b,c,d) \\ =& g^3(a+b,b+c,c+d,d+a) \\ =& g^2(a+2b+c,b+2c+d,c+2d+a,d+2a+b) \\ =& g(a+3b+3c+d,b+3c+3d+a,c+3d+3a+b,d+3a+3b+c)\end{align*}\] which is equal to \[(2a+4b+6c+4d,2b+4c+6d+4a,2c+4d+6a+4b,2d+4a+6b+4c).\] While this could be seen as a bit of a mess, the important thing to notice is that every integer in \(g^4(a,b,c,d)\) is even. By the discussion above, this means every integer in \(f^4(a,b,c,d)\) is even. Finally, recall from part (b) that if \(a\), \(b\), \(c\), and \(d\) are all either \(0\) or \(1\), then every integer in \(f^4(a,b,c,d)\) is either \(0\) or \(1\). Hence, every integer in \(f^4(a,b,c,d)\) must be equal to \(0\) since \(1\) is odd. That is, \(f^4(a,b,c,d)=(0,0,0,0)\), so \((a,b,c,d)\) is smooth.
We can solve this problem by putting together several ideas that have come up in previous parts.
This proof is formalizing the following idea, which can be observed if you apply \(f\) repeatedly to an arbitrary list of four positive integers: After at most four applications, all numbers in the resulting list will have a common factor of \(2\). Also, the largest integer in the resulting list will be no larger than the largest integer in the original list. Using Fact 2 from the solution to part (c), the common factor of \(2\) can be divided out and we will have “reduced” to a list whose largest integer is strictly smaller than the largest integer in the original list. Applying \(f\) at most four more times, we can “reduce” again. Eventually, the integers in the list will have a common factor so large that when it is factored out, the remaining integers are all either \(0\) or \(1\). At this point, part (d) can be applied.
As mentioned, the final observation we will need is that for a list \(L\) of nonnegative integers, the largest integer in \(f(L)\) is no larger than the largest integer in \(L\). In other words, the largest integer in \(f(L)\) could be the same as the largest integer in \(L\), but it cannot be bigger. This is because the largest integer in \(f(a_1,a_2,\dots,a_n)\) is equal to the largest difference between two adjacent integers in \((a_1,a_2,\dots,a_n)\) (where \(a_1\) and \(a_n\) are considered adjacent). The largest difference that can possibly occur between adjacent integers in \(L\) is equal to the largest integer in \(L\). This occurs if a \(0\) happens to be adjacent to an occurrence of the largest integer in \(L\). In this case, the largest integer in \(f(L)\) will be equal to the largest integer in \(L\). Otherwise, the largest integer in \(f(L)\) is strictly smaller than the largest integer in \(L\).
We now suppose \((a,b,c,d)\) is a list of nonnegative integers that is not smooth. We will derive a contradiction from this assumption, thereby proving that all lists of four nonnegative integers are smooth.
If \((a,b,c,d)\) is not smooth, then \(f^4(a,b,c,d)\) is not smooth either. From part (d), \(f^4(a,b,c,d)\) consists of only even integers, say \(f^4(a,b,c,d)=(2a',2b',2c',2d')\). By the fact in part (c), \((a',b',c',d')\) is smooth if and only if \((2a',2b',2c',2d')\) is smooth, and so \((a',b',c',d')\) is not smooth since \((2a',2b',2c',2d')\) is not smooth. We also know that the largest integer among \(a,b,c,d\) is at least as large as the largest integer among \(2a',2b',2c',2d'\). This means the largest integer among \(a,b,c,d\) is strictly larger than the largest among \(a',b',c',d'\).
We have shown that if there is a list \((a,b,c,d)\) of nonnegative integers that fails to be smooth, then there is a list \((a',b',c',d')\) that fails to be smooth and its largest integer is smaller than the largest integer in \((a,b,c,d)\). This fact can be applied to \((a',b',c',d')\) to get another list \((a'',b'',c'',d'')\) that fails to be smooth but has a smaller largest integer than \((a',b',c',d')\). Since the largest integer in these lists keeps getting smaller, we must eventually get a list whose largest integer is \(1\) and is not smooth. In part (d), we showed that no such list exists. This gives the contradiction we sought.
In other words, every list \((a,b,c,d)\) of four nonnegative integers is smooth.