HMMT 十一月 2015 · GEN 赛 · 第 3 题

英文解析

3. Neo has an infinite supply of red pills and blue pills. When he takes a red pill, his weight will double,
   and when he takes a blue pill, he will lose one pound. If Neo originally weighs one pound, what is the minimum number of pills he must take to make his weight 2015 pounds?
   Proposed by: Alexander Katz
   Answer: 13
   Suppose instead Neo started at a weight of 2015 pounds, instead had green pills, which halve hisweight, and purple pills, which increase his weight by a pound, and he wished to reduce his weight toone pound. It is clear that, if Neo were able to find such a sequence of pills in the case where he goesfrom 2015 pounds to 1 pound, he can perform the sequence in reverse (replacing green pills with redpills and purple pills with blue pills) to achieve the desired weight, so this problem is equivalent to theoriginal.
   Suppose at some point, Neo were to take two purple pills followed by a green pill; this changes hisweight from 2 k to k + 1. However, the same effect could be achieved using less pills by first taking agreen pill and then taking a purple pill, so the optimal sequence will never contain consecutive purplepills. As a result, there is only one optimal sequence for Neo if he is trying to lose weight: take a purplepill when his weight is odd, and a green pill when his weight is even. His weight thus becomes
   2015 → 2016 → 1008 → 504 → 252 → 126 → 63
   → 64 → 32 → 16 → 8 → 4 → 2 → 1
   which requires a total of 13 pills. Reversing this sequence solves the original problem directly.