Problem of the Month
Solution to Problem 4: January 2024

1. The positive integer $1$ cannot be expressed as the sum of more than $1$ positive integer, so if $A$ compresses $[1:9]$, then $A$ must contain the integer $1$. We want $A$ to be a list of positive integers of length four, and $1$ is the smallest positive integer, so we can assume that $A=[1,a,b,c]$ where $a$, $b$, and $c$ are integers with $1\le a\le b\le c$.

   The largest sum in $f(A)$ must be the sum of the three largest items in $A$, which is $a+b+c$, and since $f(A)=[1:9]$, we have $a+b+c=9$.

   Suppose that $a=1$ and $b=1$, then $a+b+c=9$ implies that $c=7$, but then $A=[1,1,1,7]$, which does not satisfy $f(A)=[1:9]$ since, for example, $4$ is not in $f(A)$. Therefore, $a$ and $b$ are not both $1$.

   Suppose that $a=1$ and $b=2$. Then $a+b+c=9$ implies $c=6$, so $A=[1,1,2,6]$, but then $f(A)$ does not contain $5$ so $f(A)\ne [1:9]$. Therefore, we cannot have $a=1$ and $b=2$.

   Suppose that $a=1$ and $b=3$. Then $c=5$, so $A=[1,1,3,5]$. It can be verified that $f([1,1,3,5])=[1:9]$, so this gives one possible list $A$.

   Suppose $a=1$ and $b\ge 4$. Then $c\ge 4$ as well since $b\le c$, but if $A=[1,1,b,c]$ where $b\ge 4$ and $c\ge 4$, then $f(A)$ does not contain $3$ which means $f(A)\ne [1:9]$.

   So far, we have shown that $A=[1,1,3,5]$ is the only list of the form we seek with $a=1$ and $f(A)=[1:9]$.

   We will now similarly examine the possibilities when $a=2$.

   If $a=2$ and $b=2$, then $c=5$, so $A=[1,2,2,5]$. It can be checked that $f(A)=[1:9]$ in this case.

   If $a=2$ and $b=3$, then $c=4$ and $A=[1,2,3,4]$. It can be checked that $f(A)=[1:9]$ in this case.

   If $a=2$ and $b\ge 4$, then $a+b+c=9$ implies that $c<4$, but we are assuming that $b\le c$, so this is impossible.

   Therefore, the only possibilities with $a=2$ are $A=[1,2,2,5]$ and $A=[1,2,3,4]$.

   If $a\ge 3$, then $A=[1,a,b,c]$ has $b\ge 3$ and $c\ge 3$ as well, but this would prevent $2$ from being in $f(A)$, so $A$ cannot compress $[1:9]$ in this case.

   Therefore, the only lists of length four that compress $[1:9]$ are $[1,1,3,5]$, $[1,2,2,5]$, and $[1,2,3,4]$.

   To see why no shorter list can compress $[1:9]$, we use the general observation that if $A$ is a list of length $k$, then there are at most $2^k-2$ integers in $f(A)$. This is because for each sum computed for $f(A)$, each of the $k$ items in $A$ is either included in the sum or it is not. This gives $2^k$ possible ways of computing a sum of some of the items in $A$. However, this count includes the sum of none of the items in $A$ (all are excluded from the sum) and the sum of all of the items in $A$. Both of these sums are excluded from $f(A)$, so there are $2^k-2$ ways to compute a sum to go in $f(A)$. We note that there could be multiple ways to express the same integer in $f(A)$ as a sum of items in $A$, which is why we can only say there are at most $2^k-2$ integers in $f(A)$ – in practice, there could be fewer than $2^k-2$.

   If $k\le 3$, then $2^k-2\le 2^3-2=6$, and so if $A$ is a list of length at most three, then $f(A)$ has at most $6$ integers. Therefore, $[1:9]$, which has nine integers, cannot be compressed by a list of length less than four.

2. At the end of the solution to part (a), we argued that if $A$ is a list of length $k$, then there are at most $2^k-2$ integers in $f(A)$. Since $2^6-2=62$ and $2^7-2=126$, we need $k\ge 7$ to achieve $2^k-2\ge 100$. Therefore, a list that compresses $[1:100]$ must have length at least seven. Now, we will provide a list of minimal length (seven) that compresses $[1:100]$.

   Consider $A=[1,2,4,8,16,32,38]$. Note that $1$ is in $f(A)$ and that the sum of all items in $A$ is $1+2+4+8+16+32+38=101$. Since $f(A)$ has sums of some but not all of the items in $A$, the integers in $f(A)$ are at most $100$. Rather than computing all of the sums, we will explain why $f(A)=[1:100]$ in a way that will give some insight for part (c).

   We first consider the sums that are achievable without using the integer $38$. The other integers in $A$ are $1=2^0$, $2=2^1$, $4=2^2$, $8=2^3$, $16=2^4$, and $32=2^5$. The sums that can be obtained by adding some or all of these integers are exactly the integers from $1$ through $63=2^6-1$. To get an idea of how this works, read about "binary expansions" or "binary representations" of integers. As an example, to represent $53$ as a sum of powers of $2$, first, find the largest power of $2$ that is no larger than $53$, which is $32$. Then compute $53-32=21$ to get $53=32+21$. Now find the largest power of $2$ that is no larger than $21$, which is $16$. Subtract to get $21-16=5$ or $21=16+5$. Now substitute to get $53=32+16+5$. Repeating this process, find the largest power of $2$ that is no larger than $5$, which is $4$. Subtracting, $5-4=1$ so $5=4+1$, but what remains, $1$, is a power of $2$, so we get $53=32+16+4+1=2^5+2^4+2^2+2^0$.

   The integers from $1$ through $63$ are all in $f(A)$. To write the integers from $64$ through $100$ as a sum of integers in $A$, notice that $100-38=62$, and so if $64\le m\le 100$, then $m-38\le 62$. To write such $m$ as a sum of integers from $A$, compute $r=m-38\le 62<63$, write $r$ as a sum of the integers from $A$ other than $38$, then include $38$ in the sum. For example, to see that $91$ is in $f(A)$, compute $r=91-38=53$, then use that $53=32+16+4+1$ to get that $91=1+4+16+32+38$.

   The only thing left to check is that none of the sums described above require using all seven items in $A$. To see why this is not a concern, recall that the sum of all items in $A$ is $101$, so if we express an integer that that is no larger than $100$ as a sum of items from $A$, then it cannot possibly use every item in $A$.

3. The result of part (b) generalizes as follows. For every positive integer $n$, the minimum length of a list $A$ that compresses $[1:n]$ is $\lceil {\log }_2(n+2)\rceil$. Notice that when $n=100$, since $100+2=102$ is strictly between $2^6=64$ and $2^7=128$, we have $\lceil {\log }_2(100+2)\rceil =7$, which agrees with the result from part (b).

   We will prove that $\lceil {\log }_2(n+2)\rceil$ is the minimum length of a list that compresses $[1:n]$ and, in the process, prove that $[1:n]$ is always compressible.

   To see that $\lceil {\log }_2(n+2)\rceil$ is the minimum length of a list that compresses $[1:n]$ in general, we will show that a list of length less than $\lceil {\log }_2(n+2)\rceil$ cannot possibly compress $[1:n]$, and then we will construct a list of length exactly $\lceil {\log }_2(n+2)\rceil$ that does compress $[1:n]$.

   Suppose $A$ has length $k<\lceil {\log }_2(n+2)\rceil$. Since $k$ and $\lceil {\log }_2(n+2)\rceil$ are both integers, this implies $k\le \lceil {\log }_2(n+2)\rceil -1$. For every integer $x$, it is true that $\lceil x\rceil -1<x\le \lceil x\rceil$, so we conclude that $k\le \lceil {\log }_2(n+2)\rceil -1<{\log }_2(n+2)$.

   From $k<{\log }_2(n+2)$, we get $2^k<n+2$ or $2^k-2<n$. As argued earlier, a list $A$ of length $k$ has the property that there are at most $2^k-2$ distinct integers in $f(A)$. Since $2^k-2<n$, we cannot have $f(A)=[1:n]$ when $A$ is a list of length $k<\lceil {\log }_2(n+2)\rceil$ since $[1:n]$ contains $n$ integers.

   We have shown that if $A$ compresses $[1:n]$, then it must have length at least $\lceil {\log }_2(n+2)\rceil$. We will now produce a list of length $\lceil {\log }_2(n+2)\rceil$ that compresses $[1:n]$. This requires explaining how to produce the list, then showing that the list has the correct length.

   Suppose $n$ is a positive integer. Define $k$ to be the largest non-negative integer with the property that $2^k\le n+1$ and define $m=n+2-2^k$. The list $A$ consisting of the powers of $2$ from $1$ through $2^{k-1}$ together with $m$ will compress $[1:n]$ and have length exactly $\lceil {\log }_2(n+2)\rceil$. Notice that it is possible for $m$ to be equal to one of the powers of $2$ from $1$ through $2^{k-1}$. In this situation, the list $A$ will include two copies of that power of $2$.

   Before verifying that the list described above does what is required, we will work through a couple of examples.

   • When $n=1$, we observe that $2^0=1$ and $2^1=2$ are the powers of $2$ that are no larger than $n+1=2$, and so $k=1$. Thus, $2^{k-1}=1$ and $m=n+2-2^k=1+2-2=1$, so the list is $A=[1,1]$. Indeed $f([1,1])=[1]$.

   • When $n=100$, we get $k=6$, so $2^{k-1}=32$ and $m=n+2-2^k=100+2-64=38$, so the list is $A=[1,2,4,8,16,32,38]$, which is exactly the list from part (b).

   We will now show that list $A$ has length $\lceil {\log }_2(n+2)\rceil$. The integer $k$ is the largest non-negative integer with the property that $2^k\le n+1$, and $A$ contains $2^0$, $2^1$, and so on up to $2^{k-1}$, along with the integer $m$. This gives a total of $k+1$ items in $A$. Therefore, it suffices to show that with $k$ chosen as described above, we have $\lceil {\log }_2(n+2)\rceil =k+1$.

   The function ${\log }_2$ is increasing, meaning that if $x$ and $y$ are positive real numbers with $x<y$, then ${\log }_2(x)<{\log }_2(y)$. Using this fact along with the fact that $2^k\le n+1$, we get that $k\le {\log }_2(n+1)<{\log }_2(n+2)$. As well, $k$ is the largest non-negative integer with the property that $2^k\le n+1$, which means $n+1<2^{k+1}$.

   Suppose $k+1<{\log }_2(n+2)$. Then $2^{k+1}<n+2$. From above, we also have $n+1<2^{k+1}$, so we conclude that $n+1<2^{k+1}<n+2$. The quantities $n+1$ and $n+2$ are consecutive integers, so the integer $2^{k+1}$ cannot lie strictly between them. Therefore, it is impossible for $k+1<{\log }_2(n+2)$, which means we must have ${\log }_2(n+2)\le k+1$. Combining this inequality with $k<{\log }_2(n+2)$, we have $k<{\log }_2(n+2)\le k+1$, and so we conclude that $\lceil {\log }_2(n+2)\rceil =k+1$.

   It remains to show that $A$ compresses $[1:n]$. As discussed earlier, since list $A$ contains the items $2^0$, $2^1$, and so on up to $2^{k-1}$, as well as at least one other item, $m$, $f(A)$ contains all of the integers from $1$ through $2^{k-1+1}-1=2^k-1$. This is because these integers can be expressed using the sum of some or all of the powers of $2$ from $1$ through $2^{k-1}$. These are exactly the integers that can be expressed without using $m$.

   If we do use $m$, then we can express every integer from $m$ through $m+2^k-1$ as a sum of items in $A$. Since $m+2^k-1$ is the sum of all items in $A$, it is excluded from $f(A)$ and so we have that $f(A)$ contains all of the integers from $m$ to $m+2^k-2$, and nothing larger. By definition, $m=n+2-2^k$, so $m+2^k-2=(n+2-2^k)+2^k-2=n$.

   We have shown that $f(A)$ is the list consisting of the integers that are in $[1:2^k-1]$ or $[m:n]$. To see that $f(A)$ is exactly $[1:n]$, we need to show that $m\le 2^k$. There might be overlap corresponding to multiple ways to express some integers in $[1:n]$ in $f(A)$, but this is allowed.

   Suppose $m>2^k$. Since these quantities are integers, we must have $m\ge 2^k+1$. By definition, $m=n+2-2^k$, and so we get that $n+2-2^k\ge 2^k+1$, which can be rearranged to get $n+1\ge 2^k+2^k=2^{k+1}$. Therefore, we have $2^{k+1}\le n+1$, but $k$ was chosen to be the largest integer with $2^k\le n+1$, so it is not possible that $2^{k+1}\le n+1$. Therefore, our assumption that $m>2^k$ must be wrong, so we conclude that $m\le 2^k$, as desired.

4. Fix a positive integer $k\ge 3$. We will show that for every integer $m\ge k$, $[m:m+k-1]$ is not compressible.

   To see this, suppose $A$ is a list that compresses $[m:m+k-1]$. Since $k\ge 3$, there are at least three items in $[m:m+k-1]$. If $A$ has only two items, then $f(A)$ has at most two integers since the allowable sums are just the two "singleton sums". Therefore, $A$ also contains at least three items. Note that since $m$ is the smallest integer in $f(A)$, $m$ must also be the smallest integer in $A$. (If $r$ is in $A$, then the "singleton sum" $r$ must also be in $f(A)$, so all integers in $A$ must be at least $m$. Also, since there is nothing smaller than $m$ in $A$, the only way to produce $m$ in $f(A)$ is by the "singleton sum" $m$.)

   Since $k\ge 3$, $m+1$ is also in $f(A)$. If $m+1$ is the sum of at least two items in $A$, then they must all be smaller than $m+1$, but the only integer in $A$ that is smaller than $m+1$ is $m$. This would mean $1$ must be in $A$, but this is impossible since $1<k\le m$ and $m$ is the smallest element in $A$. Therefore, we must also have $m+1$ in $A$, and so both $m$ and $m+1$ are in $A$.

   Now recall that $A$ has at least three items, so there is at least one element other than $m$ and $m+1$, and so $m+m+1=2m+1$ is in $f(A)$. Since $f(A)=[m:m+k-1]$, we must then have $2m+1\le m+k-1$, which can be rearranged to get $m\le k-2$, which is impossible since $m\ge k$.

   Therefore, it is not possible to compress $[m:m+k-1]$ when $m\ge k$. This means that there are only finitely many $m$ for which $[m:m+k-1]$ is compressible since all such $m$ must be at most $k$.

5. As mentioned in the hint, the answer is $39$. This means $[5:39]$ is not compressible, but $[5:k]$ is compressible for all $k\ge 40$. We will include a sketch of the proof here.

   One can check that the lists $A=[5,6,7,8,9,10]$, $B=[5,5,6,6,7,8,9]$, $C=[5,5,6,7,7,8,9]$, $D=[5,5,6,7,8,8,9]$, and $E=[5,5,6,7,8,9,9]$ compress the lists $[5:40]$, $[5:41]$, $[5:42]$, $[5:43]$, and $[5:44]$, respectively.

   Now suppose a list $A$ compresses $[5:k]$ and suppose $B$ is the list $A$ with a $5$ added to it. It can be shown that $B$ compresses the list $[5:k+5]$. Since $[5:40]$ is compressible, this shows that $[5:45]$ is compressible. Since $[5:41]$ is compressible, $[5:46]$ is compressible. Since we have five consecutive values of $k$ for which $[5:k]$ is compressible ($k=40$ through $k=44$), this reasoning can be used to show that $[5:k]$ is compressible for all $k\ge 40$. Note that the lists to compress $[5:k]$ given by this inductive process will not, in general, be as short as possible.

   Now suppose a list $A$ compresses $[5:39]$. It can be argued using reasoning similar to that from earlier parts that $5$ must be in $A$, $5$ is the smallest integer in $A$, and that the integers $6$, $7$, $8$, and $9$ also appear in $A$. Since the smallest integer in $A$ is $5$, the largest sum in $f(A)$ is $5$ less than the sum of all items in $A$. Therefore, the sum of all items in $A$ must be $39+5=44$. We already have $5$, $6$, $7$, $8$, and $9$ in $A$ which have a sum of $5+6+7+8+9=35$, and so the remaining items in $A$ have a sum of $44-35=9$.

   Next, note that using only the five items $5$, $6$, $7$, $8$, and $9$, a sum of $10$ is impossible. The list $A$ cannot contain the integer $10$ itself since we already determined that the remaining items in $A$ have a sum of $9$. It also cannot include the integers $1$, $2$, $3$, or $4$ since $5$ is the smallest integer in $A$. Therefore, the $10$ in $f(A)$ must come from the sum of two $5$s, which means $A$ must include a second $5$.

   We now have that $A$ contains (at least) the items $5$, $5$, $6$, $7$, $8$, and $9$, which have a total of $40$. Since the sum of all items in $A$ is $44$, there must be an additional item in $A$ that is no larger than $44-40=4$. This is impossible, so we conclude that $[5:39]$ is not compressible.