Competition problem — Combinatorics

Library / /1 of 62

Combinatorics Difficulty 3.7 AMC 10/12 Find the answer Ukraine

Petro has to plant $8$ trees in a row: apple trees or oak trees. There is one restriction: there has to be no apple trees between any two oak trees. For example, such planting $AAOOAOAA$ or $OAOAAAAA$ are not allowed, and $AAOOAAAA$ is allowed. How many different plantings are possible?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Obviously, all oaks have to be planted together as one group no matter where this group will be situated. Let us count how many oaks can possibly be.

If there are no oak trees, then the option of planting is only one.

If there are $k$ oaks, $1 \leq k \leq 8$ , there are $9 - k$ options:

$OOOAAAAA$ , $AOOOAAAA$ , $\ldots$ , $AAAAAOOO$ .

Together we have $1 + 1 + 2 + 3 + \ldots + 8 = 37$ .

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.