Putnam 2009, Problem B-3

Call a subset $S$ of $\{1, 2, \ldots, n\}$ mediocre if it has the following property: Whenever $a$ and $b$ are elements of $S$ whose average is an integer, that average is also an element of $S$. Let $A(n)$ be the number of mediocre subsets of $\{1, 2, \ldots, n\}$. [For instance, every subset of $\{1, 2, 3\}$ except $\{1, 3\}$ is mediocre, so $A(3) = 7$.] Find all positive integers $n$ such that $A(n + 2) - 2A(n + 1) + A(n) = 1$.

Solution:
The answer is \( n = 2^k - 1 \) for some integer \( k \geq 1 \). There is a bijection between mediocre subsets of \( \{1, \ldots, n\} \) and mediocre subsets of \( \{2, \ldots, n + 1\} \) given by adding 1 to each element of the subset; thus \( A(n + 1) - A(n) \) is the number of mediocre subsets of \( \{1, \ldots, n + 1\} \) that contain 1. It follows that \( A(n + 2) - 2A(n + 1) + A_n = (A(n + 2) - A(n + 1)) - (A(n + 1) - A(n)) \) is the difference between the number of mediocre subsets of \( \{1, \ldots, n + 2\} \) containing 1 and the number of mediocre subsets of \( \{1, \ldots, n + 1\} \) containing 1. This difference is precisely the number of mediocre subsets of \( \{1, \ldots, n + 2\} \) containing both 1 and \( n + 2 \), which we term "mediocre subsets containing the endpoints." Since \( \{1, \ldots, n + 2\} \) itself is a mediocre subset of itself containing the endpoints, it suffices to prove that this is the only mediocre subset of \( \{1, \ldots, n + 2\} \) containing the endpoints if and only if \( n = 2^k - 1 \) for some \( k \).

If \( n \) is not of the form \( 2^k - 1 \), then we can write \( n + 1 = 2^a b \) for odd \( b > 1 \). In this case, the set \( \{1 + mb \mid 0 \leq m \leq 2^a\} \) is a mediocre subset of \( \{1, \ldots, n + 2\} \) containing the endpoints: the average of \( 1 + m_1 b \) and \( 1 + m_2 b \), namely \( 1 + \frac{m_1 + m_2}{2} b \), is an integer if and only if \( m_1 + m_2 \) is even, in which case this average lies in the set.

It remains to show that if \( n = 2^k - 1 \), then the only mediocre subset of \( \{1, \ldots, n + 2\} \) containing the endpoints is itself. This is readily seen by induction on \( k \). For \( k = 1 \), the statement is obvious. For general \( k \), any mediocre subset \( S \) of \( \{1, \ldots, n + 2 = 2^k + 1\} \) containing 1 and \( 2^k + 1 \) must also contain their average, \( 2^{k-1} + 1 \). By the induction assumption, the only mediocre subset of \( \{1, \ldots, 2^{k-1} + 1\} \) containing the endpoints is itself, and so \( S \) must contain all integers between 1 and \( 2^{k-1} + 1 \). Similarly, a mediocre subset of \( \{2^{k-1} + 1, \ldots, 2^k + 1\} \) containing the endpoints gives a mediocre subset of \( \{1, \ldots, 2^{k-1} + 1\} \) containing the endpoints by subtracting \( 2^{k-1} \) from each element. By the induction assumption again, it follows that \( S \) must contain all integers between \( 2^{k-1} + 1 \) and \( 2^k + 1 \). Thus \( S = \{1, \ldots, 2^k + 1\} \) and the induction is complete.

**Remark.** One can also proceed by checking that a nonempty subset of \( \{1, \ldots, n\} \) is mediocre if and only if it is an arithmetic progression with odd common difference. Given this fact, the number of mediocre subsets of \( \{1, \ldots, n + 2\} \) containing the endpoints is seen to be the number of odd factors of \( n + 1 \), from which the desired result is evident. (The sequence \( A(n) \) appears as sequence A124197 in the Encyclopedia of Integer Sequences.)