# Problem of the MonthProblem 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]$$.

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

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