Hilbert's New Hotel

gracias · 发表于 2011-11-22 00:31:00

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

这是project euler上最新的一道题.不知大家有没有兴趣.题目是这样的 An infinite number of people (numbered 1, 2, 3, etc.) are lined up to get a room at Hilbert's newest infinite hotel. The hotel contains an infinite number of floors (numbered 1, 2, 3, etc.), and each floor contains an infinite number of rooms (numbered 1, 2, 3, etc.). Initially the hotel is empty. Hilbert declares a rule on how the nth person is assigned a room: person n gets the first vacant room in the lowest numbered floor satisfying either of the following: the floor is empty the floor is not empty, and if the latest person taking a room in that floor is person m, then m + n is a perfect square Person 1 gets room 1 in floor 1 since floor 1 is empty. Person 2 does not get room 2 in floor 1 since 1 + 2 = 3 is not a perfect square. Person 2 instead gets room 1 in floor 2 since floor 2 is empty. Person 3 gets room 2 in floor 1 since 1 + 3 = 4 is a perfect square. Eventually, every person in the line gets a room in the hotel. Define P(f, r) to be n if person n occupies room r in floor f, and 0 if no person occupies the room. Here are a few examples: P(1, 1) = 1 P(1, 2) = 3 P(2, 1) = 2 P(10, 20) = 440 P(25, 75) = 4863 P(99, 100) = 19454 Find the sum of all P(f, r) for all positive f and r such that f × r = 71328803586048 and give the last 8 digits as your answer. 我通过对一些小规模情况的考虑发现有以下规律(纯属猜测,不懂如何证明,因此也不知是否成立) 1 P(1 ,N) = N*(N+1) /2 ; 2 P(N ,1) = N^2 /2( N为偶数) P(N,1) =(N^2 - 1)/2(N为奇数) 3 P(N ,i+1) 是大于P(N,i)的最小的那个使得P(N,i) + P(N,i+1)为完全平方数的数即使以上三点成立,以我目前的能力也还是无法解决这个问题,因为计算量还是太大.不知各位是否有兴趣给出更好的解答方法建议.

mathe · 发表于 2011-11-22 09:19:39

写个程序计算出前5000个人的归属，很容易验证满足下面的规律对于任意给定的a,P(a,b+2)-P(a,b)是公差为2的等差数列。于是我们只需要再找出每一行的前两个数即可

gracias · 发表于 2011-11-22 09:35:24

谢谢mathe,你的解答已经帮我解过一道题了

mathe · 发表于 2011-11-22 09:38:30

继续分析可以看出除了前三行前两个数为 1 3 2 7 4 5 以外对于后面各行，第k+1行和第k行的差为 [(k+1)/2]*2 而第k行的前两个数的差在k为奇数时是1，k为偶数时是2k+1

gracias · 发表于 2011-11-22 11:34:32

，mathe你好，谢谢你的回复. 但你提到的这个规律我还是没明白如何用于快速求解呀. 利用你提到的规律可以快速求出 p(n ,i+2) - p(n ,i) 但是还是不能确定p(n ,i)呀 !

mathe · 发表于 2011-11-22 20:29:42

也就是每一行的偶数位置的数据可以写成i的二次多项式，同样奇数位置的数据也可以写成i的另外一个二次多项式

mathe · 发表于 2011-11-22 21:08:09

这些性质证明都不难

gracias · 发表于 2011-11-22 21:58:50

完全明白了,谢谢 A3 - A1 = P A4 - A2 = P + D A5 - A3 = P + 2D A6 - A4 = P + 3D ................... 所以: A3 = A1 +D A5 = A3 + P +2D = A1 + D +P +2D = A1 +P + 3D A7 = A5 + P +3D = A1 +P+ 3D +3D = A1 + P + 6D ........................

gracias · 发表于 2011-11-23 00:03:59

整天忙的人都晕了A3 -A1 ,A4-A2 ,A5 -A3 ......是等差数列,那么 A3 -A1 ，A5-A3 ，A7-A5也是等差数列这都忘了.

gracias · 发表于 2011-11-23 00:04:50

终于完成了

账号		自动登录	找回密码
密码			欢迎注册

[讨论] Hilbert's New Hotel

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。