Problem of the Month
Hint for Problem 4: January 2024

1. Any list that compresses $[1:9]$ must contain $1$. Think about the largest possible number of integers in $f(A)$ when $A$ is a list of length $k$.

2. First, try to find a list that compresses $[1:63]$ that is as short as possible. It might help to read about the binary representation of positive integers.

3. Work out a few more examples like the one in (b). It is possible to compress $[1:n]$ using a list $A$ that consists entirely or almost entirely of powers of $2$.

4. For $k\ge 3$ and $m\ge 2$, if $A$ compresses $[m:m+k-1]$, then $A$ must contain $m$ and $m+1$.

5. The answer is $39$. Do not worry about trying to compress $[5:k]$ using as short a list as possible. As well, inductive thinking could be useful here. Suppose you can show that there is some $k$ with the property that $[5:k]$, $[5:k+1]$, $[5:k+2]$, $[5:k+3]$, and $[5:k+4]$ are all compressible. Can you deduce that $[5:n]$ is compressible for all $n\ge k$?