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, ifshe has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integerd > 1 for which she can group the rice into equal groups of size d with none left over. She then groupsthe 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, ifshe has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integerd > 1 for which she can group the rice into equal groups of size d with none left over. She then groupsthe 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
Note that 2401 = 7 . Also, note that the operation is equivalent to replacing n grains of rice with 4
p − 1
n · grains of rice, where p is the smallest prime factor of n .
Now, suppose that at some moment Alison has 7 grains of rice. After each of the next fourkpk − 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 takesher 4 steps to decrease the number of grains of rice by a factor of 7 given that she starts at a power of 7.
Thus, it will take 4 · 4 = 16 steps to reduce everything to 7 = 1 grain of rice, after which it 0
will take one step to eat it. Thus, it takes a total of 17 steps for Alison to eat all of the rice.