找回密码
 欢迎注册
楼主: 056254628

[讨论] 雷区布雷的最小值

[复制链接]
发表于 2009-9-10 19:44:04 | 显示全部楼层
本帖最后由 wayne 于 2009-9-10 19:48 编辑 我穷举法能验证楼上的n<7的那些值是可以实现的 到了n=7,我就有点力不从心了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-9-10 23:44:13 | 显示全部楼层
本帖最后由 056254628 于 2009-9-10 23:57 编辑 接10楼: 我有一种构造方法,是否是最小值有待确定。 ---------------------------------------------- 对于3*m,可以用以下方法构造: 0表示空格,1表示地雷格 0000......0000 1111......1111 0000......0000 一共用到$m$个地雷。 --------------------------------- 对于2*m,可以用以下方法构造: 0表示空格,1表示地雷格 m mod 3=0 010010...010010 010010...010010 一共用到$2/3*m$个地雷。 m mod 3=2 010010...01001 010010...01001 一共用到$2/3*(m+1)$个地雷。 m mod 3=1 010010...0101 010010...0101 一共用到$2/3*(m+2)$个地雷。 ----------------------------------- 对于1*m,可以用以下方法构造: 0表示空格,1表示地雷格 m mod 4=0 01100110...0110 一共用到$m/2$个地雷。 m mod 4=1 01100110...01111 一共用到$(m+3)/2$个地雷。 m mod 4=2 01100110...011011 一共用到$(m+2)/2$个地雷。 m mod 4=3 01100110...0110110 一共用到$(m+1)/2$个地雷。 ------------------- 所以对于n*n 可以每3行一组,每组需要n个地雷。 剩下的再按照1*m或2*m来布雷。 用g(n,m)表示用上述方法所需的地雷数。 (n*m雷区) ------------ 那么$g(3k,3k)=3*k^2$ $g(3k+1,3k+1)=k*(3k+1)+g(1,3k+1)$ $g(3k+2,3k+2)=k*(3k+2)+g(2,3k+2)$ g(2,2)=2/3*(2+1)=2 g(3,3)=3*1^2=3 g(4,4)=4+g(1,4)=6 g(5,5)=5+g(2,5)=9 g(6,6)=3*2^2=12 g(7,7)=2*7+g(1,7)=18 g(8,8)=2*8+g(2,8)=22 g(9,9)=3*3^2=27 ------------- n<6时,g(n,n)=f(n) n>=6时,g(n,n)都小于随机法求出的值。 但是不是g(n,n)都等于f(n)呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-9-11 06:58:48 | 显示全部楼层
可以查看第40届IMO第三题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-9-11 07:08:09 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-9-11 20:39:33 | 显示全部楼层
本帖最后由 056254628 于 2009-9-11 20:43 编辑 按照第40届IMO第三题的解题精神: n为偶数,$f(n)=(n*(n+2))/4$。 当n为奇数,f(3)=3 f(5)=9 f(7) 我能给出的最小值为16 f(9) 我能给出的最小值为25 ...... $ f(n)=(n+1)^2/4?$ n为大于3的奇数 ------------------------ 上述对奇数的计算公式是否成立呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-29 09:54 , Processed in 0.024153 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表