发信人: hero080 (hero), 信区: BrainTeaser 标 题: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 17:08:23 2007), 转信 我自己都不记得答案了，先出出来大家讨论： 下五子棋时，有人会采用一种所谓的“八卦阵”防守，即让最近的子都成日字形， 这样另一方无论如何都不能连成5。为表述方便，现将棋盘上的点用二维平面上的 整点（X,Y坐标都是整数的点）表示，则防守的点是……（0,0），（0,5）， （0,10）……（1,2），（1,7），（1,12）……（2,－1），（2,4），（2,9）…… （3,1），（3,6），（3,11）……（4,3），（4,8），（4,13）…… 以上只指出了部分点，其它点按同样规律无穷延伸即可。 当然了，实际下棋时谁这么走多半是要挂的，不过仅从形式上看这样的“棋阵” 很漂亮，大家会发现如果假设棋盘无穷大，那么刚好1/5的位置被占，这显然是 阻止对方连成5的最低比例。我们称这样的棋阵为完美防御。 现在问题是，如果下的是N子棋，完美防御是什么样的？大家很快会发现，N为 1、2、3、4时这样的完美防御是不存在的。那对于其它的N呢？ -- ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 69.110.]
发信人: parachute (降落伞), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 17:26:00 2007), 转信 等我脑袋清醒的时候再来看 【 在 hero080 (hero) 的大作中提到: 】 : 我自己都不记得答案了，先出出来大家讨论： : 下五子棋时，有人会采用一种所谓的“八卦阵”防守，即让最近的子都成日字形， : 这样另一方无论如何都不能连成5。为表述方便，现将棋盘上的点用二维平面上的 : 整点（X,Y坐标都是整数的点）表示，则防守的点是……（0,0），（0,5）， : （0,10）……（1,2），（1,7），（1,12）……（2,－1），（2,4），（2,9）…… : （3,1），（3,6），（3,11）……（4,3），（4,8），（4,13）…… : 以上只指出了部分点，其它点按同样规律无穷延伸即可。 : 当然了，实际下棋时谁这么走多半是要挂的，不过仅从形式上看这样的“棋阵” : 很漂亮，大家会发现如果假设棋盘无穷大，那么刚好1/5的位置被占，这显然是 : 阻止对方连成5的最低比例。我们称这样的棋阵为完美防御。 : ................... -- To be without some of the things you want is an indispensable part of happiness. ※ 来源:·BBS 未名空间站 mitbbs.com·[From:69.111] ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 72.36.]
发信人: xixizi (西西子), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 17:39:41 2007) 题目好长啊 -- ※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 129.89.]
发信人: hero080 (hero), 信区: BrainTeaser 标 题: [贴个图]Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 17:47:01 2007) 这样可能会清楚一点。那一堆坐标不用读了。 【 在 xixizi (西西子) 的大作中提到: 】 : 题目好长啊 -- ※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 69.110.] 此主题相关图片如下：
发信人: Deling (流浪歌手-爬爬死爬腰酸), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 18:14:12 2007), 转信 问题简化一下就是：N x N 的grid，放N个棋子，要求每行一个，每列一个，没条对角 线一个(对角线需要wrap) 【 在 hero080 (hero) 的大作中提到: 】 : 我自己都不记得答案了，先出出来大家讨论： : 下五子棋时，有人会采用一种所谓的“八卦阵”防守，即让最近的子都成日字形， : 这样另一方无论如何都不能连成5。为表述方便，现将棋盘上的点用二维平面上的 : 整点（X,Y坐标都是整数的点）表示，则防守的点是……（0,0），（0,5）， : （0,10）……（1,2），（1,7），（1,12）……（2,－1），（2,4），（2,9）…… : （3,1），（3,6），（3,11）……（4,3），（4,8），（4,13）…… : 以上只指出了部分点，其它点按同样规律无穷延伸即可。 : 当然了，实际下棋时谁这么走多半是要挂的，不过仅从形式上看这样的“棋阵” : 很漂亮，大家会发现如果假设棋盘无穷大，那么刚好1/5的位置被占，这显然是 : 阻止对方连成5的最低比例。我们称这样的棋阵为完美防御。 : ................... -- 夢後樓台高鎖，酒醒簾幕低垂。去年春恨卻來時，落花人獨立，微雨燕雙飛。 記後小蘋初見，兩重心字羅衣。琵琶絃上說相思。當時明月在，曾照彩雲歸。 ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 24.16.]
发信人: froogle (向意神医致敬), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 18:36:41 2007) 难得啊,有题目还没有人解答的 等我昨晚手上的功课来看 -- ※ 来源:·BBS 未名空间站 http://mitbbs.com·[FROM: 71.232.]
发信人: Deling (流浪歌手-爬爬死爬腰酸), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 18:50:28 2007), 转信 N如果是奇数，并且>3，挑一个i, such that i is an even number, 0 < i < N-1 在每个N*N的grid里面这样摆放N个棋子： (0,0) (1,i mod N) (2, 2i mod N) ... 然后重复这个N*N的grid N如果是偶数，这样的防御不存在。 证明过程待会再写 【 在 hero080 (hero) 的大作中提到: 】 : 我自己都不记得答案了，先出出来大家讨论： : 下五子棋时，有人会采用一种所谓的“八卦阵”防守，即让最近的子都成日字形， : 这样另一方无论如何都不能连成5。为表述方便，现将棋盘上的点用二维平面上的 : 整点（X,Y坐标都是整数的点）表示，则防守的点是……（0,0），（0,5）， : （0,10）……（1,2），（1,7），（1,12）……（2,－1），（2,4），（2,9）…… : （3,1），（3,6），（3,11）……（4,3），（4,8），（4,13）…… : 以上只指出了部分点，其它点按同样规律无穷延伸即可。 : 当然了，实际下棋时谁这么走多半是要挂的，不过仅从形式上看这样的“棋阵” : 很漂亮，大家会发现如果假设棋盘无穷大，那么刚好1/5的位置被占，这显然是 : 阻止对方连成5的最低比例。我们称这样的棋阵为完美防御。 : ................... -- __("< \__/ ^^ One small step for BSD, One giant step for PCs. ※ 修改:·Deling 于 Mar 29 18:51:17 修改本文·[FROM: 24.16.] ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 24.16.]
发信人: Deling (流浪歌手-爬爬死爬腰酸), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Thu Mar 29 19:16:33 2007), 转信 我把坐标起始改成0，这样方便一点。证明一下： 因为需要守所有N条纵边，所以没有两个棋子在同列。 suppose 这N个棋子的坐标为(0,x0), (1,x1) ... (n-1,x_{N-1}) 类似，没有两个棋子在同行，所以x0..x_{N-1}互不相等 另外，没有两个棋子在同一对角线。 主对角线(x+y=constant)：S1={x0,x1+1,x2+2, ... x_{N-1} + N-1} 副对角线(x-y=constant): S2={x0,x1-1,x2-2, ... x_{N-1} - (N-1)} S1,S2分别是mod N完全同余类。 S1求和=(N-1)*N S1所有数取mod N求和 = (N-1)*N/2 因为 (N-1)*N = (N-1)*N/2 mod N,所以，N是奇数。 Now, since i is an even #, 0 < i < N-1, so, i-1和i+1都和N互质， therefore, {0, i+1, 2(i+1), 3(i+1) ... }是mod N的完全同余类 {0, i-1, 2(i-1) ....}也是 so, let x0=0,x1=i,x2=2i ... 【 在 Deling (流浪歌手-爬爬死爬腰酸) 的大作中提到: 】 : N如果是奇数，并且>3，挑一个i, such that i is an even number, 0 < i < N-1 : 在每个N*N的grid里面这样摆放N个棋子： : (0,0) (1,i mod N) (2, 2i mod N) ... : 然后重复这个N*N的grid : N如果是偶数，这样的防御不存在。 : 证明过程待会再写 -- ((`'-"``""-'`)) ) - - ( / (o _ o) \ \ ( 0 ) / _'-.._'='_..-'_ ※ 修改:·Deling 于 Mar 29 19:59:29 修改本文·[FROM: 24.16.] ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 24.16.]
发信人: hero080 (hero), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Fri Mar 30 00:36:47 2007), 转信 哈哈，赞！ 不过还是有一点小问题。比方说N=9,i=7，那i-1=6就不会N=9互质啊。 【 在 Deling (流浪歌手-爬爬死爬腰酸) 的大作中提到: 】 : 我把坐标起始改成0，这样方便一点。证明一下： : 因为需要守所有N条纵边，所以没有两个棋子在同列。 : suppose 这N个棋子的坐标为(0,x0), (1,x1) ... (n-1,x_{N-1}) : 类似，没有两个棋子在同行，所以x0..x_{N-1}互不相等 : 另外，没有两个棋子在同一对角线。 : 主对角线(x+y=constant)：S1={x0,x1+1,x2+2, ... x_{N-1} + N-1} : 副对角线(x-y=constant): S2={x0,x1-1,x2-2, ... x_{N-1} - (N-1)} : S1,S2分别是mod N完全同余类。 : S1求和=(N-1)*N : S1所有数取mod N求和 = (N-1)*N/2 : ................... -- ※ 来源:·BBS 未名空间站 mitbbs.com·[FROM: 24.7.]
发信人: mirazhaojing (Mira), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Sun Mar 15 19:01:14 2009) @@ 【 在 hero080 (hero) 的大作中提到: 】 : 我自己都不记得答案了，先出出来大家讨论： : 下五子棋时，有人会采用一种所谓的“八卦阵”防守，即让最近的子都成日字形， : 这样另一方无论如何都不能连成5。为表述方便，现将棋盘上的点用二维平面上的 : 整点（X,Y坐标都是整数的点）表示，则防守的点是……（0,0），（0,5）， : （0,10）……（1,2），（1,7），（1,12）……（2,－1），（2,4），（2,9）…… : （3,1），（3,6），（3,11）……（4,3），（4,8），（4,13）…… : 以上只指出了部分点，其它点按同样规律无穷延伸即可。 : 当然了，实际下棋时谁这么走多半是要挂的，不过仅从形式上看这样的“棋阵” : 很漂亮，大家会发现如果假设棋盘无穷大，那么刚好1/5的位置被占，这显然是 : 阻止对方连成5的最低比例。我们称这样的棋阵为完美防御。 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 127.0.]
发信人: lordofwar (warlord), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Sat May 2 01:25:25 2009) 他不是说了i选一个偶数吗，总能找到这样的偶数使得i-1,i+1和N互质 【 在 hero080 (hero) 的大作中提到: 】 : 哈哈，赞！ : 不过还是有一点小问题。比方说N=9,i=7，那i-1=6就不会N=9互质啊。 -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 68.83.]
发信人: lordofwar (warlord), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Sat May 2 01:27:35 2009) ft，才发现，这是07年的帖子，楼上的证法还是很赞的 【 在 lordofwar (warlord) 的大作中提到: 】 : 他不是说了i选一个偶数吗，总能找到这样的偶数使得i-1,i+1和N互质 -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 68.83.]
发信人: hero080 (APM=080), 信区: BrainTeaser 标 题: Re: 大家这么热闹，出个稍有难度的老题 发信站: BBS 未名空间站 (Tue May 5 16:13:54 2009), 转信 为啥总能找到？还有i自己也必须和N素质的。你试试对N=9找找看。 【 在 lordofwar (warlord) 的大作中提到: 】 : 他不是说了i选一个偶数吗，总能找到这样的偶数使得i-1,i+1和N互质 -- ※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 99.139.]
网站地图 - 联系我们 - 服务条款 - 隐私权政策 版权所有，未名空间 - 中国大陆站（mitbbs.cn），since 1996
