HMMT 二月 2008 · 冲刺赛 · 第 8 题

HMMT February 2008 — Guts Round — Problem 8

[ 6 ] 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?

解析

[ 6 ] 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? Answer: 1920 We look at the number of cottages after each wave of peasants. Let A be the n number of cottages remaining after 8 n minutes. During each 8 minute interval, Trodgor burns a total of 480 / 5 = 96 peasants and cottages. Trodgor first burns A peasants and spends the remaining n time burning 96 − A cottages. Therefore, as long as we do not reach negative cottages, we have the n recurrence relation A = A − (96 − A ), which is equivalent to A = 2 A − 96. Computing the n +1 n n n +1 n first few terms of the series, we get that A = 84, A = 72, A = 48, and A = 0. Therefore, it takes 1 2 3 4 Trodgor 32 minutes, which is 1920 seconds.