HMMT 二月 2012 · TEAM2 赛 · 第 3 题

英文解析

3. [ 10 ] Mac is trying to fill 2012 barrels with apple cider. He starts with 0 energy. Every minute, he mayrest, gaining 1 energy, or if he has n energy, he may expend k energy (0 ≤ k ≤ n ) to fill up to n ( k + 1)
   barrels with cider. What is the minimal number of minutes he needs to fill all the barrels?
   Answer: 46 First, suppose that Mac fills barrels during two consecutive minutes. Let his energyimmediately before doing so be n , and the energy spent in the next two minutes be k , k , respectively.
   1 2
   It is not difficult to check that he can fill at least as many barrels by spending k + k + 1 energy and
   1 2
   resting for an additional minute before doing so, so that his starting energy is n + 1: this does notchange the total amount of time. Furthermore, this does not affect the amount of energy Mac hasremaining afterward. We may thus assume that Mac first rests for a (not necessarily fixed) period oftime, then spends one minute filling barrels, and repeats this process until all of the barrels are filled.
   Next, we check that he only needs to fill barrels once. Suppose that Mac first rests for n minutes,
   then spends k energy, and next rests for n minutes and spends k energy. It is again not difficult to 1
   1 2 2
   check that Mac can instead rest for n + n + 1 minutes and spend k + k + 1 energy, to increase the
   1 2 1 2
   number of barrels filled, while not changing the amount of time nor the energy remaining. Iteratingthis operation, we can reduce our problem to the case in which Mac first rests for n minutes, thenspends n energy filling all of the barrels.
   We need n ( n + 1) ≥ 2012, so n ≥ 45, and Mac needs a minimum of 46 minutes.