HMMT 十一月 2015 · GEN 赛 · 第 3 题
HMMT November 2015 — GEN Round — Problem 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?
解析
- 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 his weight, and purple pills, which increase his weight by a pound, and he wished to reduce his weight to one pound. It is clear that, if Neo were able to find such a sequence of pills in the case where he goes from 2015 pounds to 1 pound, he can perform the sequence in reverse (replacing green pills with red pills and purple pills with blue pills) to achieve the desired weight, so this problem is equivalent to the original. Suppose at some point, Neo were to take two purple pills followed by a green pill; this changes his weight from 2 k to k + 1. However, the same effect could be achieved using less pills by first taking a green pill and then taking a purple pill, so the optimal sequence will never contain consecutive purple pills. As a result, there is only one optimal sequence for Neo if he is trying to lose weight: take a purple pill 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.