Competition problem — Combinatorics

Library / /143 of 377

Combinatorics Difficulty 5.0 AIME Find the answer United States

Problem:

Trodgor the dragon is burning down a village consisting of 90 cottages. At time $t=0$ an angry peasant arises from each cottage, and every 8 minutes (480 seconds) thereafter another angry peasant spontaneously generates from each non-burned cottage. It takes Trodgor 5 seconds to either burn a peasant or to burn a cottage, but Trodgor cannot begin burning cottages until all the peasants around him have been burned. How many seconds does it take Trodgor to burn down the entire village?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: 1920

We look at the number of cottages after each wave of peasants. Let $A_{n}$ be the number of cottages remaining after $8n$ minutes. During each 8 minute interval, Trodgor burns a total of $480 / 5 = 96$ peasants and cottages. Trodgor first burns $A_{n}$ peasants and spends the remaining time burning $96 - A_{n}$ cottages. Therefore, as long as we do not reach negative cottages, we have the recurrence relation $A_{n+1} = A_{n} - (96 - A_{n})$ , which is equivalent to $A_{n+1} = 2A_{n} - 96$ .

Computing the first few terms of the series, we get that $A_{1} = 84$ , $A_{2} = 72$ , $A_{3} = 48$ , and $A_{4} = 0$ . Therefore, it takes Trodgor 32 minutes, which is 1920 seconds.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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