The gardener problem

Question

I tried to solve this, but I am unsure about my solution. I'm posting it here to see if I got it right. It is listed as multiple choice, but I am unsure about the quality of the puzzle creator, so don't limit yourself to the 5 provided answers.

The problem:

A gardener wants to plant 100 trees (oaks and birches) alongside a trail in a park. The number of trees between any two oaks must not be equal to five. What is the largest number of oaks that the gardener could plant?

A)48

B)50

C)52

D)60

E)80

My solution:

45 Oaks.

Planted in a pattern like this (O=Oaks, X = Birches), repeating to 100.

OXOXOXXOX

I'm quite certain there is a better way to solve this (and a better answer), so enlighten me on how to solve a problem like this.

Answer 1

Seems to me a greedy strategy can work.

As when you plant an oak at position $x$, position $x+6$ cannot be an oak, but position $x+12$ can be an oak, and position $x+18$ cannot, $\dots$

So my strategy is:

I plant oaks on position $1$ to $6$. This means positions $7$ to $12$ are birches, $13$ to $18$ are oaks, and so on.

As a result:

So for every $12$ consecutive trees, $6$ of them are oaks. The last $4$ (position $97$ to $100$) are also oaks. Hence the number of oaks is $52$.

Answer 2

Showing an answer x is correct requires two things:

1, Show x is feasible (can be achieved)

2, Show that y > x is infeasible (cannot be achieved)

For part 1, a greedy strategy works, as mentioned in previous answer. Place as many oaks in a row as possible (ie, six oaks) without having five trees in a row between two oaks; then place six birches; duplicate this pattern eight times; fill the last four places with oaks.

For part 2, we will assume a configuration C has at most 47 birches, and will show C is infeasible, as follows.

First, note that 100 = 8⅓ dozen. If at most 47 birches are placed somewhere in the first eight consecutive-dozens of a hundred, then at least one of those consecutive-dozens contains fewer than six birches (because 47/8 < 6).

Next, note that if a consecutive-dozen has fewer than six birches, then at least two oaks are separated by exactly five trees. This is because there are six ways to have five-separation, involving places 1+7; 2+8; 3+9; 4+10; 5+11; and 6+12. Five birches can block up at most five of those six ways; it takes at least six birches to block them all.

This shows that any configuration C with fewer than 48 birches is infeasible.