永发信息网

抓三堆问题可以用二进制方法来解决么

答案:1  悬赏:0  手机版
解决时间 2021-12-05 00:06
抓三堆问题可以用二进制方法来解决么
最佳答案
能 二进制法解“抓三堆”问题抓三堆
有三堆谷粒(例如100粒、200粒、300粒),甲、乙轮流抓,每次只能从一堆中抓,最少抓1粒,可抓任意多粒;甲先抓,规定谁抓到最后一把谁赢。问:甲应该如何抓?为什么?
分析:问题特殊化
1、只有一堆时,即状况为(a , 0 , 0),此时先抓者必胜
2、只有两堆时,即状况为(a , b , 0)
(1)若b = a , 即状况为(a , a , 0),此时后抓者必胜。因为
对方先抓后,结果或剩一堆,成为(a , 0 , 0)的状况,
一把可抓完;或剩两堆,你抓后,又成为新的(d , d , 0)
的状况,且d < a , 继续由对方抓。
(2)若b ≠ a ,不妨设b > a ,即状况为(a , b , 0), 此时先抓
者必胜。因为先抓者可以把第二堆抓掉b – a个,使状况
转化为(a , a , 0), 成为新的“状况(1)”。
3、三堆都有,且其中两堆相等,即状况为
(a , a , c),此时先抓者必胜。因为先抓者可以把
第三堆全抓完,使状况转化为(a , a , 0),成为新
的“状况 2)(1)”。
4、三堆都有,且其中任意两堆都不相等,即状况为(a , b , c), 且不妨设a < b < c ,此时情况比较复杂。
为了下面表述得清楚,我们把前面的一个结论用“反面说法”,总结为
“把两堆相等的状况留给对方,自己可以取胜。”
然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。
(1)a = 1 时,即状况为(1 , b , c)。
下面再对 b 分情况讨论。
(2)a = 2 时,即状况为(2 , b , c)。
下面再对 b 分情况讨论。
(3)a = 3 时,即状况为(3 , b , c)。
下面再对 b 分情况讨论。
(4)a = 4 时,即状况为(4 , b , c)。
下面再对 b 分情况讨论。
然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。
(1)a = 1 时,即状况为(1 , b , c)。
下面再对 b 分情况讨论。
(2)a = 2 时,即状况为(2 , b , c)。
下面再对 b 分情况讨论。
(3)a = 3 时,即状况为(3 , b , c)。
下面再对 b 分情况讨论。
(4)a = 4 时,即状况为(4 , b , c)。
下面再对 b 分情况讨论。
(1)a = 1 时,即状况为(1 , b , c)。下面再对 b 分情况。
由于a < b < c ,即 a、b、c “前小后大”,因此 b最小为2,于是起始情况是(1 , 2 , 3)。经用“穷举法”分析,该情况下后抓者胜;或用“反面说法”说成,“把(1 , 2 , 3)的状况留给对方,自己可以取胜”。
下一个情况是(1 , 2 , c), c > 3 。此时必先抓者胜。因为先抓者只要把第三堆抓剩3个,就转化成(1 , 2 , 3)的状况,从而必胜。
下一个情况是(1 , 3 , c), c > 3。此时必先抓者胜。因为先抓者只要把第三堆抓剩2个,就转化成(1, 3 , 2)的状况,也即(1, 2 , 3)的状况,从而必胜。
下一个情况是(1 , 4 , c), c > 4。起始情况是(1 , 4 , 5)。经用“穷举法”分析,该情况下后抓者胜;或用“反面说法”说成,
“把(1 , 4 , 5)的状况留给对方,自己可以取胜”。
这样类似地分析下去,逐渐可以得到结论:
把(1 , 2 , 3)的状况留给对方,自己可以取胜。
把(1 , 4 , 5)的状况留给对方,自己可以取胜。
把(1 , 6 , 7)的状况留给对方,自己可以取胜。
把(1 , 8 , 9)的状况留给对方,自己可以取胜。
这样类似地分析下去,逐渐可以得到结论:
把(1 , 2 , 3)的状况留给对方,自己可以取胜。
把(1 , 4 , 5)的状况留给对方,自己可以取胜。
把(1 , 6 , 7)的状况留给对方,自己可以取胜。
把(1 , 8 , 9)的状况留给对方,自己可以取胜。
于是归纳、抽象、猜测:把(1 , 2m , 2m+1)的状况留给对方,自己可以取胜。
然后用数学归纳法可以证明,这一结论是正确的。【自己证明】
这样,就把 a = 1 时的情况,全搞清楚了。
(2)a = 2 时,即状况为(2 , b , c)。
下面再对 b 分情况。
由于a < b < c , 即a、b、c “前小后大”,因此 b最小为3,于是起始情况是(2 , 3 , c)。c > 3。
此时必先抓者胜。因为先抓者只要把第三堆抓剩1个,就转化成(2 , 3 , 1)的状况,也即(1 , 2 , 3)的状况,从而必胜。
下一个情况是(2 , 4 , c), c > 4。起始情况是(2 , 4 , 5)。此时必先抓者胜。因为先抓者只要
把第一堆抓剩1个,就转化成(1 , 4 , 5)的状况,从而必胜。
下一个情况是(2 , 4 , 6)。经用“穷举法”分析,该情况下后抓者胜;或用“反面说法”说成,“把(2 , 4 , 6)的状况留给对方,自己可以 取胜”。
这样类似地分析下去,逐渐可以得到结论:
把(2 , 4 , 6)的状况留给对方,自己可以取胜。
把(2 , 5 , 7)的状况留给对方,自己可以取胜。
把(2 , 8 , 10)的状况留给对方,自己可以取胜。
把(2 , 9 , 11)的状况留给对方,自己可以取胜。
于是归纳、猜测:把(2 , 4m , 4m+2)或(2 , 4m+1 , 4m+3)的状况留给对方,自己可以取胜。然后用数学归纳法可以证明,这一结论是正确的。
这样,就把a = 2 时的情况,全搞清楚了。
(3)a = 3 时,即状况为(3 , b , c)。
下面再对b分情况。类似地分析下去,逐渐可以得到结论:
把(3 , 4 , 7)的状况留给对方,自己可以取胜。
把(3 , 5 , 6)的状况留给对方,自己可以取胜。
把(3 , 8 , 11)的状况留给对方,自己可以取胜。
把(3 , 9 , 10)的状况留给对方,自己可以取胜。
于是归纳、猜测:
把(3 , 4m , 4m+3)或(3 , 4m+1 , 4m+2)的状况留给对方,自己可以取胜。然后用数学归纳法可以证明,这一结论是正确的。这样,就把a = 3 时的情况,全搞清楚了。
为了赢律更大,还需研究 a =4 时的情况,a = 5 时的情况
例如a = 4 时的情况,经过研究可以得到结论:
把(4 , 8 , 12)的状况留给对方,自己可以取胜。
把(4 , 9 , 13)的状况留给对方,自己可以取胜。
把(4 , 10 , 14)的状况留给对方,自己可以取胜。
把(4 , 11 , 15)的状况留给对方,自己可以取胜。
把(4 , 16 , 20)的状况留给对方,自己可以取胜。
把(4 , 17 , 21)的状况留给对方,自己可以取胜。
把(4 , 18 , 22)的状况留给对方,自己可以取胜。
把(4 , 19 , 23)的状况留给对方,自己可以取胜。
于是归纳、猜测:
把(4 , 8m , 8m+4)或(4 , 8m+1 , 8m+5)或(4 , 8m+2 , 8m+6)或(4 , 8m+3 , 8m+7)的状况留给对方,自己可以取胜。
然后用数学归纳法可以证明,这一结论是正确的。
这样,用“数列通项公式”的方法,继续研究
下去,也能得出取胜的策略,但表达起来会很繁琐。
因为已经看到,在(a , b , c),a < b < c的
规定下,
a = 1 时,有一种表达式(1 , 2m , 2m+1)的状况留给对方,自己可以取胜。
a = 2 时,有二种表达式(2 , 4m , 4m+2)或(2 , 4m+1 , 4m+3)的状况留给对方,自己可以取胜。
a = 3 时,有二种表达式(3 , 4m 4m+3)或(3 , 4m+1 , 4m+2)的状况留给对方,自己可以取胜。
a = 4 时,有四种表达式(4 , 8m , 8m+4)或(4 , 8m+1 , 8m+5)或(4 , 8m+2 , 8m+6)或
(4 , 8m+3 , 8m+7)的状况留给对方,自己可以 取胜。
可以猜测,a = 4、5、6、7这四种情况时,都分别有四种通项表达式的状况留给对方,自己可以取胜。
a =8、9、10、11、12、13、14、15这八种情况时,都分别有八种通项表达式的状况留给对方,自己可以取胜。
…………
a = 2k ,2k+1,2k +2,…,2k+1-1 ,这 2k种情况时,都分别有 2k种通项表达式的状况留给对方,自己可以取胜。
“抓三堆”的二进制解法
用二进制表示这三堆谷粒数,写成三行,并上下对齐,各列相加,列的加法定义为0+0=0;0+1=1;1+0=1;1+1=1.
这就是模2加法。(只要是有2的倍数,就都可以作为0)
关于模2加法,可以推广;比如推广为模7加法:
例1:如果1号是星期一,问 27号是星期几?
解答:27号与1号相差26天,因为 26=7*3+5. ,说明过去3个7天之后,再过5 天,这样27号这天就是星期一再加上5天,即星期六。(事实上,这里只要是有7的倍数,就都可以作为0。)
例2:如果1号是星期三,问 27号是星期几?(答:星期一)
我们断言:把三堆谷粒数均表为二进制,写成三行,将位数对齐,各列“模2相加”,若各列的和全为0,则后抓者有必胜策略; 若和中出现1,则先抓者有必胜策略。
和中出现1时,先抓者的具体策略是:先抓者从最左边的1所在的列,寻找某堆的谷粒数中相应的列也有1,就从该堆中抓走适当个数,使得抓完后各列的和(模2)为0。
一、由于谷粒数越来越少,最后,先抓者可以使得后抓者始终面临各列模2之和为(0,0,…,0)状态,这意味着先抓者获胜。
二、后抓者只要抓,谷粒就将减少,因此该行中至少有一个1变为0(如果1都不变为0,只会使谷粒数增加或不变),从而该列模2之和将为1。于是先抓者就不会面临(0,0,…, 0)状态。
三、先抓者的正确抓法,应使得各列模2之和均为0。即,先抓者应总是抓成(0,0,…, 0)状态。
例1:设原始状态(2,3,4),则先抓者胜。
例2:设原始状态(5,8,13),则后抓者胜。
例3:设原始状态(5,12,13),则先抓者胜。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
华硕的ASUS WebStorage账号密码在哪里
excel怎么就只是在单元格里面写出范围,并设
1987年4月1月阴历属什么星座
数据清楚和数据删除的区别是什么?
用完瘦咖会反弹吗?
ups联合包裹(环城路368号附近ups联合包裹)地
饥荒海难棕榈叶棚有什么用
淘宝商城卖gxg都的九型人格是正品吗
佳明gps手表 forerunner和fenix3 哪个好
一百个蜂窝大概取多少克毒?蜂毒大概多少钱一
There________nothingbuttwoloomsin
百度君是什么?
易经中同一个卦象的上卦下卦有什么位置上的含
《秋思》《逢入京使》《子夜吴歌》《 山居秋
谁说后妈都是恶毒的,那只是你们身边没有好的
推荐资讯
甘草霜涂脸可以去斑吗
科二科三买过多少钱
临时身份证明可以选日子吗?可以提前办理吗?
观察下列各数:2,5,10,17,26.
阜宁县施庄派出所地址有知道的么?有点事想过
我在网上被骗子骗了一万四千多块钱,我想去报
求28岁未成年电视剧百度云,谢谢
以前在爱奇艺里面下载了一个游戏,现在爱奇艺
怎样练好说话能力,以及为人处世,本人嘴笨,
康明斯发动机故障代码1682
国海证券公司怎么样
总裁老婆等等我(gl)全文+番外
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?