Maths Olympiad Prep

Library / /41 of 82

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:

There are 15 stones placed in a line. In how many ways can you mark 5 of these stones so that there are an odd number of stones between any two of the stones you marked?

Solution

Solution:

Number the stones 11 through 1515 in order. We note that the condition is equivalent to stipulating that the stones have either all odd numbers or all even numbers. There are (85)\binom{8}{5} ways to choose 55 odd-numbered stones, and (75)\binom{7}{5} ways to choose all even-numbered stones, so the total number of ways to pick the stones is (85)+(75)=77\binom{8}{5} + \binom{7}{5} = 77. (nk)\binom{n}{k} is the number of ways to choose kk out of nn items. It equals n!k!(nk)!\frac{n!}{k!(n-k)!}.

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.