Hint for Problem 4: January 2024

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

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

For \(k\geq 3\) and \(m\geq 2\), if \(A\) compresses \([m:m+k-1]\), then \(A\) must contain \(m\) and \(m+1\).

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\geq k\)?