Problem 29 · 2013 Math Kangaroo
Stretch
Counting & Probability
caseworkcareful-counting
100 trees (oaks and birches) are standing in a row. The number of trees between any two oaks is never equal to 5. What is the maximum number of the 100 trees that can be oaks?
Show answer
Answer: B — 52
Show hints
Hint 1 of 2
Two oaks may not be 6 positions apart (that is 5 trees between them); link positions whose numbers differ by 6.
Still stuck? Show hint 2 →
Hint 2 of 2
Split positions 1–100 by their remainder mod 6 into chains, then pick the most from each chain with no two neighbours.
Show solution
Approach: independent set on residue-mod-6 chains
- Positions that differ by 6 cannot both be oaks; grouping 1–100 by remainder mod 6 gives six chains.
- Each chain is a row where no two adjacent positions may both be oaks, so pick about half of each: the ceiling of (chain length) / 2.
- Summing over the six chains gives a maximum of 52 oaks.
Mark:
· log in to save