考天才的题目来了,请进来试试(答案见内)
(2011-04-15 10:19:03)
标签:
杂谈 |
分类: 各抒己见 |
一些不能在这贴出的文章已经在“海外艾园”贴出:http://aiyuan.wordpress.com/
我简单的翻译一下:
5个人被丢到了荒岛,只有椰子可以吃。
五个人一起采摘了很多的椰子,他们决定平分, 每个人拿到1/5的椰子。
夜幕降临,大伙都去睡了~~~~~
第一个人 起来了,然后呢他不相信其他几个人,决定先把自己那份椰子藏起来,可是他发现,把这些椰子平分为5分的话会有一个椰子剩下,刚巧一直猴子路过,他就把那一个椰子给了猴子,然后他把自己的那份椰子藏起来了。接着 继续去睡觉……
然后 过了一会儿第二个人醒了,他做了和第一个人一样的事情,他把剩下的那些椰子平均分为五分 还是有一个剩下,刚巧那猴子经过给了猴子,
接下来的人都做了同样的举动一直到第五个人
【提问】一开始最少数目的椰子有多少???
谢谢回答啊!
用 Chinese Reminder Theorem的话 我也不知道怎么 set up啊, 因为 每次的椰子数目变化了, CRT的话每次开始的数字都是一样的啊
----------------------------
答案by “junorquant”:
Brute force解得3121
假设第1,2,3,4,5人藏起来的数目是x1,x2,x3,x4,x5,
4*x1 = 5*x2+1 => x1 = 5/4*x2+1/4,迭代得到,
x1 = 625/256 * x5 + 625/256 – 1
=> 4^4 * (x1+1) = 5^4 * (x5+1)
=> x1+1比是625倍数,x5+1是256倍数.
=> (x1,x2,x3,x4,x5) = (624,499,399,319,255)
=> 最小总数是x1*5+1=3121
and PitBull’s answer:
如果一开始加四个的话,五次都能平分。
五次都能平分的数最小是5的5次方,所以一开始最少椰子数是:5^5-4=3121