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{align*} 1 & =1\\ 1 & =1\\ 3 & =3\\ 7 & =7\end{align*}\] \[\begin{align*} 1+1 & =2\\ 1+3 & =4\\ 1+7 & =8\\ 1+3 & =4\\ 1+7 & =8\\ 3+7 & =10\end{align*}\] \[\begin{align*} 1+1+3 & =5 \\ 1+1+7 & =9 \\ 1+3+7 & =11\\ 1+3+7 & =11\\\end{align*}\] 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]\).

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

Find a list, \(A\), that compresses \([1:100]\) and is as short as possible.

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]\).

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

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