NZMO Round Two

Combinatorics Difficulty 6.1 National Olympiad Prove it New Zealand

Problem:

For any positive integer $n$ , let $f(n)$ be the number of subsets of $\{1,2,\ldots ,n\}$ whose sum is equal to $n$ . Does there exist infinitely many positive integers $m$ such that $f(m) = f(m + 1)$ ? (Note that each element in a subset must be distinct.)

Solution

Solution:

Let $S(n)$ be the set of such subsets. Consider the map from $S(n)$ to $S(n + 1)$ that adds one to the largest element of each $A \in S(n)$ . This map is an injection (needs proof but easy) and not a surjection provided that $S(n + 1)$ contains a set whose largest and second largest elements differ by one. For even $n = 2k \geqslant 2$ this is true since we can take $\{k, k + 1\} \in S(n + 1)$ and for odd $n = 2k + 1 \geqslant 5$ this is true since we can take $\{1, k, k + 1\}$ . So for $n \geqslant 5$ , we must have $f(n) < f(n + 1)$ and there do not exist infinitely many such pairs.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.