Track / Stage 3 / 206 of 260 #206 of 2000

Problem 206

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

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 and solution reproduced as published; topic, difficulty and ordering added by this site.