HMMT February

Note that every supported set $S$ contains $0,8,9,16,17,18,24-27,32-36,40-45$, 48-54, and all $n \geq 55$. Now define $\bar{S}:=\mathbb{Z}^{+} \backslash S$, which is a subset of $\{1-7,10-15,19-23,28-31,37,38,39,46,47,55\}$ satisfying the opposite property that $k \in \bar{S} \Longrightarrow k-8, k-9 \in \bar{S}$. Consider the above arrangement after removing the numbers not in $\bar{S}$. The condition that $S$ be supported ensures that sets $\bar{S}$ are in bijective correspondence with paths from $(0,0)$ to $(16,0)$ consisting of discrete steps of $\langle 1,1\rangle$ and $\langle 1,-1\rangle$ and lying above the $x$-axis: from the modified version of the above diagram, a unique path passes through the top items left in each column. The number of such paths is the 8th Catalan number, so the answer is $C_{8}=\frac{1}{8+1}\binom{8 \cdot 2}{8}=\frac{12870}{9}=1430$. (Incidentally, 16 choose 8 was computed in an earlier problem.) Without the explicit formula for Catalan numbers, the answer can be computed recursively by filling in the number of ways a path can reach $(16,0)$ from each position in the figure. One works right to left, obtaining the following: One can exploit symmetry and, having determined the middle column, sum the squares: $1^{2}+7^{2}+20^{2}+28^{2}+14^{2}=1430$