MMO2025 Round 4

We begin by observing that for all integers $n,m\ge 1$, the inequality $$A_{n+m}\le A_n\cdot A_m$$ holds. This is because any subset of $\{1,2,\dots ,n+m\}$ avoiding adjacent elements can be formed by taking a subset of $\{1,2,\dots ,n\}$ and a subset of $\{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 $B_n$. A subset $X\subseteq \{1,2,\dots ,n\}$ with no two elements differing by $2$ can be partitioned into its odd and even elements: $$X_o=X\cap \{1,3,5,\dots \},X_e=X\cap \{2,4,6,\dots \}.$$ Since no two elements of $X$ may differ by $2$, it follows that both $X_o$ and $X_e$ must avoid consecutive elements within their respective sequences. That is, $X_o$ must avoid adjacent odd integers, and $X_e$ must avoid adjacent even integers.

Hence, $X_o$ is a subset of a set of size $\lfloor n/2\rfloor$ with no adjacent elements, and similarly for $X_e$, of size $\lfloor n/2\rfloor$. Thus, $$B_n=A_{\lfloor n/2\rfloor }\cdot A_{\lfloor n/2\rfloor }.$$ We now estimate $A_{2025}$. Using submultiplicativity, $$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.