HMMT 二月 2012 · TEAM2 赛 · 第 3 题
HMMT February 2012 — TEAM2 Round — Problem 3
题目详情
- [ 10 ] Mac is trying to fill 2012 barrels with apple cider. He starts with 0 energy. Every minute, he may rest, gaining 1 energy, or if he has n energy, he may expend k energy (1 ≤ 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?
解析
- [ 10 ] Mac is trying to fill 2012 barrels with apple cider. He starts with 0 energy. Every minute, he may rest, 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 energy immediately 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 not change the total amount of time. Furthermore, this does not affect the amount of energy Mac has remaining afterward. We may thus assume that Mac first rests for a (not necessarily fixed) period of time, 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, 1 then spends k energy, and next rests for n minutes and spends k energy. It is again not difficult to 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. Iterating this operation, we can reduce our problem to the case in which Mac first rests for n minutes, then spends n energy filling all of the barrels. We need n ( n + 1) ≥ 2012, so n ≥ 45, and Mac needs a minimum of 46 minutes.