返回题库

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

HMMT November 2019 — THM Round — Problem 5

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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?
解析

英文解析

  1. 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.