Problem of the Month
Problem 4: January 2024

In this problem, we will enclose a list of positive integers in square brackets. For example, $[1,2,4,7,9]$ is a list of positive integers of length five. All lists in this problem will be expressed in non-decreasing order. To denote the list of consecutive integers from $a$ to $b$ inclusive, we will use the notation $[a:b]$. For example, $[4:7]$ denotes the list $[4,5,6,7]$.

Given a list, $A$, of positive integers, we will define $f(A)$ to be the increasing list of distinct positive integers that are expressible as the sum of some, but not all, of the items in $A$. A sum is allowed to consist of just one item in $A$, and each item in $A$ can be used at most once in a particular sum.

For example, if $A=[1,1,3,7]$, then the sums of at least one but not all of the items in $A$ are shown below. $$\begin{array}{rl}1& =1\\ 1& =1\\ 3& =3\\ 7& =7\end{array}$$ $$\begin{array}{rl}1+1& =2\\ 1+3& =4\\ 1+7& =8\\ 1+3& =4\\ 1+7& =8\\ 3+7& =10\end{array}$$ $$\begin{array}{rl}1+1+3& =5\\ 1+1+7& =9\\ 1+3+7& =11\\ 1+3+7& =11\end{array}$$ Therefore, $f(A)=[1,2,3,4,5,7,8,9,10,11]$.

A list, $D$, of positive integers is called compressible if there exists some list $A$ with $f(A)=D$. In this situation, we say that $D$ is compressed by $A$ or that $A$ compresses $D$. From the example above, we have that $[1,2,3,4,5,7,8,9,10,11]$ is compressible and is compressed by $[1,1,3,7]$.

1. Find all lists of length four that compress $[1:9]$ and explain why no list of length three or less can compress $[1:9]$.

2. Find a list, $A$, that compresses $[1:100]$ and is as short as possible.

3. Show that for all positive integers $n$, the list $[1:n]$ is compressible. For each $n$, determine the smallest possible length of a list that compresses $[1:n]$.

4. Show that for all positive integers $k\ge 3$ there are only finitely many compressible lists of $k$ consecutive positive integers. That is, for each positive integer $k\ge 3$, show that there are only finitely many positive integers $m$ for which $[m:m+k-1]$ is compressible.

5. Find the largest positive integer $k$ such that $[5:k]$ is not compressible. (A full solution will not be provided for this part.)