HMMT 十一月 2019 · THM 赛 · 第 5 题

HMMT November 2019 — THM Round — Problem 5

Alison is eating 2401 grains of rice for lunch. She eats the rice in a very peculiar manner: every step, if she has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integer d > 1 for which she can group the rice into equal groups of size d with none left over. She then groups the rice into groups of size d , eats one grain from each group, and puts the rice back into a single pile. How many steps does it take her to finish all her rice?

解析

Alison is eating 2401 grains of rice for lunch. She eats the rice in a very peculiar manner: every step, if she has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integer d > 1 for which she can group the rice into equal groups of size d with none left over. She then groups the rice into groups of size d , eats one grain from each group, and puts the rice back into a single pile. How many steps does it take her to finish all her rice? Proposed by: Carl Schilkraut Answer: 17 4 Note that 2401 = 7 . Also, note that the operation is equivalent to replacing n grains of rice with p − 1 n · grains of rice, where p is the smallest prime factor of n . p k Now, suppose that at some moment Alison has 7 grains of rice. After each of the next four k − 1 k − 1 k − 1 k − 1 steps, she will have 6 · 7 , 3 · 7 , 2 · 7 , and 7 grains of rice, respectively. Thus, it takes her 4 steps to decrease the number of grains of rice by a factor of 7 given that she starts at a power of 7. 0 Thus, it will take 4 · 4 = 16 steps to reduce everything to 7 = 1 grain of rice, after which it will take one step to eat it. Thus, it takes a total of 17 steps for Alison to eat all of the rice.