PUMaC 2008 · 团队赛 · 第 6 题
PUMaC 2008 — Team Round — Problem 6
题目详情
- (4 points) The seven dwarves are at work on day when they find a large pile of diamonds. They want to split the diamonds evenly among them, but find that they would need to take away one diamond to split into seven equal piles. They are still arguing about this when they get home, so Snow White sends them to bed without supper. In the middle of the night, Sneezy wakes up and decides that he should get the extra diamond. So he puts one diamond aside, splits the remaining ones in to seven equal piles, and takes his pile along with the extra diamond. Then, he runs off with the diamonds. His sneeze wakes up Grumpy, who, thinking along the same lines, removes one diamond, divides the remainder into seven equal piles, and runs off. Finally, Sleepy, for the first time in his life, wakes up before sunrise and performs the same operation. When the remaining four dwarves arise, they find that the remaining diamonds can be split into 5 equal piles. Doc suggests that Snow White should get a share, so they have no problem splitting the remaining diamonds. Happy, Dopey, Bashful, Doc, and Snow White live happily ever after. What’s the smallest possible number of diamonds that the dwarves could have started out with?
解析
- The seven dwarves are at work on day when they find a large pile of diamonds. They want to split the diamonds evenly among them, but find that they would need to take away one diamond to split into seven equal piles. They are still arguing about this when they get home, so Snow White sends them to bed without supper. In the middle of the night, Sneezy wakes up and decides that he 1 Team should get the extra diamond. So he puts one diamond aside, splits the remaining ones in to seven equal piles, and takes his pile along with the extra diamond. Then, he runs off with the diamonds. His sneeze wakes up Grumpy, who, thinking along the same lines, removes one diamond, divides the remainder into seven equal piles, and runs off. Finally, Sleepy, for the first time in his life, wakes up before sunrise and performs the same operation. When the remaining four dwarves arise, they find that the remaining diamonds can be split into 5 equal piles. Doc suggests that Snow White should get a share, so they have no problem splitting the remaining diamonds. Happy, Dopey, Bashful, Doc, and Snow White live happily ever after. What’s the smallest possible number of diamonds that the dwarves could have started out with? ( ANS: 337 We have N = 7 k + 1. After Sneezy, 6 k remain. We see 6 k ≡ 1 mod 7, so k = 7 q + 6. Thus there are 42 q + 35 + 1 diamonds. Then remaining are 36 q + 30 diamonds after Grumpy takes his. We see 36 q + 30 ≡ 1 mod 7, so q ≡ − 1 mod 7, so q = 7 a + 6. Thus there are 252 a + 216 + 30 diamonds, and Sleepy takes this minus one divided by seven, leaving 6(252 a + 245) / 7 diamonds remaining. This is (1512 a + 1470) / 7 = 216 a + 210 diamonds remaining. This is divisible by 5. Thus we see 5 divides a . Thus a = 0 is the lowest possible. In summary, we have a = 0, q = 6, k = 48, so N = 337. CB: TL, JVP)