N个硬币的最大切点总数

金眼睛

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

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

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

superacid

有难度

lulijie

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

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

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

superacid

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

noski

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

superacid

关键是证明...

lulijie

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

总结上述的结果：    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