Mathematical Olympiad Rioplatense

Label the points clockwisely $A_1,A_2,\dots ,A_{1000}$ starting at any desired position. To every selection of several points $A_j$ there corresponds bijectively a sequence $a_1{a}_2\dots a_{1000}$ of zeros and ones in which $a_j=1$ or $a_j=0$ according as $A_j$ is selected or not. So we may argue about $0$-$1$ sequences instead of selections. Such a sequence $\alpha =a_1{a}_2\dots a_{1000}$ is admissible if it contains exactly $k$ ones, if no two ones in it are adjacent, and if at least one of $a_1$ and $a_{1000}$ is zero. We distinguish between two types of admissible sequences: type 1 with $a_1=0$ and type 2 with $a_1=1$.

Let $\alpha$ be a type 1 admissible sequence. Since $a_1=0$, every term $1$ in it is preceded by at least one $0$. Delete one zero in front of each $1$. A $0$-$1$ sequence ${\alpha }^{\prime }$ of length $1000-k$ is obtained, with $k$ terms $1$. Call the latter a sequence of type 1'; there are $\left(\genfrac{}{}{0ex}{}{1000-k}{k}\right)$ of these. Writing a $0$ in front of every $1$ in ${\alpha }^{\prime }$ restores back the original $\alpha$. It follows that $\alpha \mapsto {\alpha }^{\prime }$ is an injection from the set of type 1 admissible sequences into the set of type 1' sequences. Now take a type 1' sequence and write a zero in front of each of the $k$ terms $1$. The result is an admissible type 1 sequence: it contains $k$ ones, no two of them adjacent due to the added zeros, and the first term is a zero. Thus $\alpha \mapsto {\alpha }^{\prime }$ is a bijection, implying that there are $\left(\genfrac{}{}{0ex}{}{1000-k}{k}\right)$ type 1 admissible sequences.

Let $\alpha$ be a type 2 admissible sequence. Here $a_1=1$, therefore $a_{1000}=a_2=0$. Thus each term $a_j=1$ with $j>1$ is preceded by at least one $0$. Delete one zero in front of every such term, also delete $a_1=1$ and $a_{1000}=0$. The obtained $0$-$1$ sequence ${\alpha }^{\prime }$ has length $999-k$ and $k-1$ terms $1$. Call the latter a sequence of type 2'; there are $\left(\genfrac{}{}{0ex}{}{999-k}{k-1}\right)$ of these. Like in the previous case $\alpha \mapsto {\alpha }^{\prime }$ is a bijection, hence there are $\left(\genfrac{}{}{0ex}{}{999-k}{k-1}\right)$ type 2 admissible sequences.

In summary there are $\left(\genfrac{}{}{0ex}{}{1000-k}{k}\right)+\left(\genfrac{}{}{0ex}{}{999-k}{k-1}\right)$ admissible selections.