魔方吧·中文魔方俱乐部

标题: N个硬币的最大切点总数 [打印本页]

作者: 金眼睛 时间: 2009-9-12 16:59:40 标题: N个硬币的最大切点总数

好久没来了，出道小题大家来做做，也不知道是否有人出过，O(∩_∩)O~

桌面上随意放着N个大小一样的硬币，则硬币间的切点总数存在下限0，上限N*(N-1)/2，应该有个最大值Pmax(N)，求Pmax(N)的表达式！

相当于平面上有N个半径相同且两两不相交的圆，问最大切点总数Pmax(N)的表达式。

作者: superacid 时间: 2009-9-12 18:29:37

有难度

作者: lulijie 时间: 2009-9-12 19:10:11

Pmax(1)=0
Pmax(2)=1
Pmax(3)=3
Pmax(4)=5
......
Pmax(n)=2n-3?
------------------------------
Pmax(7)=12 多了一个

[ 本帖最后由 lulijie 于 2009-9-12 19:15 编辑 ]

作者: lulijie 时间: 2009-9-12 20:26:14

Pmax(1)=0
Pmax(2)=1
Pmax(3)=3
Pmax(4)=5
Pmax(5)=7
Pmax(6)=9
Pmax(7)=12
Pmax(8)=14
Pmax(9)=16
Pmax(10)=19
Pmax(11)=21
Pmax(12)=24
Pmax(13)=26
Pmax(14)=29
Pmax(15)=31
Pmax(16)=34
Pmax(17)=36
Pmax(18)=39
Pmax(19)=42
......

设  d(1)=Pmax(1)
   d(n)=Pmax(n)-Pmax(n-1) n>=2
那么以下是d(n)的变化情况：为了表示它的规律性，特意将有些分开、有些合拢写。
                     0 1 2 2 2 2    3
               2 23  23  23  23  23 3
         23 233  233 233  233 233 3
   233 2333  2333  2333  2333  2333 3
2333 23333  23333  23333  23333  23333 3
...................

Pmax(n)就等上述数列的前n个数字的和。
比如求Pmax(12) ，因为第一行有7个数字，所以将第一行的7个数字相加，再加上第二行的前5个数字，结果等于24。

作者: kexin_xiao 时间: 2009-9-12 20:49:19

我是来打酱油了，LZ别找我做题啊

作者: superacid 时间: 2009-9-12 20:52:00

数学区终于又大欣然的身影了

作者: noski 时间: 2009-9-12 21:17:03

哈哈，做一下试试：
对于形如 3k(k+1)+1 这样的数，恰好可以拼成正六边形，而拼成正六边形，就是最大切点数的情况。
那么，对于每个k＝0, 1, 2, 3, ...
硬币数N(k) = 3k(k+1) +1
最大切点数P(k) = 9k^2 + 3k
而对于硬币数不能拼成正六边形的情况，只要从上述可以拼成正六边形的数中，从外围往下拆硬币即可。。
具体拆法是先拆一个角，再连续的拆一圈，表达式还没有推导。。

作者: superacid 时间: 2009-9-12 21:22:59

关键是证明...

作者: lulijie 时间: 2009-9-12 22:57:21

d(n)的结果
                  0 1 2 2 2 2    3
               2 23  23  23  23  23 3
         23 233  233 233  233 233 3
   233 2333  2333  2333  2333  2333 3
2333 23333  23333  23333  23333  23333 3
........
设d(n)位于上述表的第k行第p个位置
那么
k=[sqrt((4n-5)/12)+1/2]       sqrt()表示开根号，[] 表示取整。
p=n-1-3k(k-1)
设p'=n-1-3k(k+1)
   若p'=0 (表示位于k行的最后一个数)    那么 Pmax(n)=9k^2+3k
   若p'不等于0                                     那么 Pmax(n)=3n+2-6k-[p/k]

作者: lulijie 时间: 2009-9-12 23:43:14

总结上述的结果： k=[sqrt((4n-5)/12)+1/2]       sqrt()表示开根号，[] 表示取整。
                              p=n-1-3k(k-1)
Pmax(1)=0
Pmax(n)=9k^2+3k             n=3k(k+1)+1
Pmax(n)=3n+2-6k-[p/k]    n<3k(k+1)+1

作者: 金眼睛 时间: 2009-9-21 09:55:25

原帖由 kexin_xiao 于 2009-9-12 20:49 发表
我是来打酱油了，LZ别找我做题啊

欣然，你也太谦虚了吧，呵呵！还是一如既往的勤奋啊！

lulijie和noski的观察能力还是那么强大啊，呵呵！

superacid说得很对，这道题关键是如何证明，如何描述这种“收缩”，O(∩_∩)O~

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)