Maths Olympiad Prep

Library / /7 of 17

Combinatorics Difficulty 5.5 AIME, harder Prove it Mongolia

Let AnA_n denote the number of subsets of {1,2,,n}\{1, 2, \dots, n\} that contain no two elements differing by 11, and let BnB_n denote the number of subsets that contain no two elements differing by 22. Prove that A2025<B10132A_{2025} < B_{1013}^2.
(Batbayasgalan Balkhuu and Nursoltan Khavalbolot)

Solution

We begin by observing that for all integers n,m1n, m \ge 1, the inequality
An+mAnAm A_{n+m} \le A_n \cdot A_m
holds. This is because any subset of {1,2,,n+m}\{1, 2, \dots, n+m\} avoiding adjacent elements can be formed by taking a subset of {1,2,,n}\{1, 2, \dots, n\} and a subset of {n+1,,n+m}\{n+1, \dots, n+m\}, each with no adjacent elements, and combining them (note that elements from the first part are at least two less than those in the second part, so the union remains valid).

Now consider BnB_n. A subset X{1,2,,n}X \subseteq \{1, 2, \dots, n\} with no two elements differing by 22 can be partitioned into its odd and even elements:
Xo=X{1,3,5,},Xe=X{2,4,6,}. X_o = X \cap \{1, 3, 5, \dots\}, \quad X_e = X \cap \{2, 4, 6, \dots\}.
Since no two elements of XX may differ by 22, it follows that both XoX_o and XeX_e must avoid consecutive elements within their respective sequences. That is, XoX_o must avoid adjacent odd integers, and XeX_e must avoid adjacent even integers.

Hence, XoX_o is a subset of a set of size n/2\lfloor n/2 \rfloor with no adjacent elements, and similarly for XeX_e, of size n/2\lfloor n/2 \rfloor. Thus,
Bn=An/2An/2. B_n = A_{\lfloor n/2 \rfloor} \cdot A_{\lfloor n/2 \rfloor}.
We now estimate A2025A_{2025}. Using submultiplicativity,
A2025<A2026A5062A5072=(A506A507)2=B10132. A_{2025} < A_{2026} \le A_{506}^2 \cdot A_{507}^2 = (A_{506} \cdot A_{507})^2 = B_{1013}^2.
This completes the proof.

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 and solution reproduced as published; topic and difficulty added by this site.