Maths Olympiad Prep

Library / /12 of 19

Combinatorics Difficulty 6.1 National Olympiad Prove it New Zealand

Problem:

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

Solution

Solution:

Let S(n)S(n) be the set of such subsets. Consider the map from S(n)S(n) to S(n+1)S(n + 1) that adds one to the largest element of each AS(n)A \in S(n). This map is an injection (needs proof but easy) and not a surjection provided that S(n+1)S(n + 1) contains a set whose largest and second largest elements differ by one. For even n=2k2n = 2k \geqslant 2 this is true since we can take {k,k+1}S(n+1)\{k, k + 1\} \in S(n + 1) and for odd n=2k+15n = 2k + 1 \geqslant 5 this is true since we can take {1,k,k+1}\{1, k, k + 1\}. So for n5n \geqslant 5, we must have f(n)<f(n+1)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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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