发信人: 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