Problem 27 · 2009 Math Kangaroo
Stretch
Counting & Probability
careful-countingspatial-reasoning
A number of oranges, peaches, apples and bananas are placed in a row. What is the minimum number of fruits needed so that each kind of fruit lies next to each other kind at least once somewhere in the row?
Show answer
Answer: C — 8
Show hints
Hint 1 of 2
There are four fruit types, so 6 unordered pairs must each appear side by side somewhere.
Still stuck? Show hint 2 →
Hint 2 of 2
Think of fruits as dots and 'were neighbours' as edges of K₄; you want a near-Eulerian walk.
Show solution
Approach: cover all six pairs with the fewest neighbour-links
- With 4 types there are 6 pairs to realise as adjacencies; a row of n fruits has only n−1 adjacencies.
- Each type would need to touch the other three, but all four 'dots' have odd degree 3 in the pair-graph K₄.
- Repeating one link fixes the parity, giving 7 needed adjacencies, hence 8 fruits.
- A row such as orange-peach-apple-orange-banana-peach-apple-banana shows 8 works, so the answer is 8.
Mark:
· log in to save