Track / Stage 3 / 158 of 260 #798 of 2604

Problem 798

AMC 10/12, early questions

Combinatorics Difficulty 3.7 Find the answer UkraineMO · 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.

Official 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$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.