📄 博弈.asp.htm
字号:
二堆保持为第一堆的两倍。证毕。<br> 本以为此题就这么简简单单完了，但是
我突然发现，当第一堆2颗，第二堆4颗时，从第二堆中取出3颗石子的话第二堆的确无法保持为第一堆的两倍，但第一堆会变成第二堆的两倍，基于此，整个猜想
被彻底推翻。<br> 于是我反转思路，干脆从性质入手。<br> 我们令必败二元组为（a,b)形式，并令a<b。<br> 根据性质三，有这样两个推论：<br> 推论一：对于任意两个的必败二元组(a1,b1)，(a2,b2)，有a1<>a2,b1<>b2,a1<>b2,a2<>b1。<br> 推论二：对于任意两个的必败二元组(a1,b1)，(a2,b2)，有b1-a1<>b2-a2。<br> 利用性质和该推论，我们证明如下结论：“将必败二元组按首元为关键字排序，每个必败二元组中首元为未在前面的必败二元组中出现的最小正整数，并且第N组中两个数差为N”。<br> 利用数学归纳法证明：<br> 第一组为(1，2)，满足题意。<br> 若前N组满足题意，则有：<br> 设为在前N组中出现的最小正整数为M，则对于二元组（M，M+N+1）有： <br> 如果从数量为M的堆中取了石子，不妨设变成了(K,L)，则L-K>N，这样就有一个包含K，且不与前面N组任何一组相同的二元组，根据推论一，这个二元组一定不是必败二元组。<br> 如果只从数量为M+N+1的堆中取，不妨设剩下K颗，又分三种情况：<br> K>M，则N+1>K-M>0，根据推论二，这个二元组一定不是必败二元组。<br> K=M或0，显然不是必败二元组。<br> 0<K<M，则（K，M）为包含K，且不与前面N组任何一组相同的二元组，根据推论一，这个二元组一定不是必败二元组。<br> 综上，根据性质三，（M，M+N+1）为必败二元组，又根据排序的法则，（M，M+N+1）一定是数列的第（N+1）项。证毕。<br> 这样利用性质和性质得出的推论，此题的必败态也完美的找出了。</p><br>
<p> 从上面的例子可以看出，利用寻找必败态的思路解题对猜想和数学证明的能力要求很高，对思维的训练有很大好处，同时编程复杂度相当低，也不失为一种好的解题方法。</p> <br>
</blockquote>
<!--－广告-AD--->
<center>
<script type="text/javascript"><!--
google_ad_client = "pub-9190785958461047";
google_alternate_ad_url = "http://www.mydrs.org/banner.gif";
google_ad_width = 468;
google_ad_height = 60;
google_ad_format = "468x60_as";
google_ad_channel ="";
google_color_border = "E0FFE3";
google_color_bg = "E0FFE3";
google_color_link = "0000CC";
google_color_url = "008000";
google_color_text = "000000";
//--></script>
<script type="text/javascript" src="%B2%A9%DE%C4.asp_files/show_ads">
</script><iframe name="google_ads_frame" src="%B2%A9%DE%C4.asp_files/ads.htm" marginwidth="0" marginheight="0" vspace="0" hspace="0" allowtransparency="true" frameborder="0" height="60" scrolling="no" width="468"><img></iframe>
</center><br><br>
<!--广告-AD--->
<table width="100%">
<tbody><tr>
<td bgcolor="#ffffff" valign="top" width="50%">
<table align="center" border="0" cellpadding="0" cellspacing="0" width="80%">
<tbody><tr>
<td>
<p align="left">
作 者：只影 <br>
来 源：论坛精华<br>
共有62位读者阅读过此文
</p></td>
</tr>
</tbody></table></td>
<td bgcolor="#ffffff" valign="top" width="50%">
<p>
</p><li><font color="#0772b1">上篇文章</font>：<a href="http://www.mydrs.org/program/list.asp?id=583">nlogn的最长子序列算法[ZJU1986]</a>
<br>
</li><li><font color="#0772b1">下篇文章</font>：已经没有了
<br>
<a href="http://www.mydrs.org/program/sendmail.asp?id=584" target="_blank"><img src="%B2%A9%DE%C4.asp_files/mail.gif" border="0" height="16" width="16">推荐给好友</a>
<a style="" onclick="document.execCommand('SaveAs',false,'C:\My Documents\\寻找必败态:博弈问题的快速解法.htm')"><img src="%B2%A9%DE%C4.asp_files/save.gif" border="0" height="16" width="16">保存本页</a>
<a href="javascript:window.print()"><img src="%B2%A9%DE%C4.asp_files/print.gif" border="0" height="14" width="16">打印本页</a>
<a href="http://bbs.mydrs.org/list.asp?boardid=4"><img src="%B2%A9%DE%C4.asp_files/bbs.gif" border="0" height="16" width="13">到论坛讨论</a>
</li></td>
</tr>
<tr>
<td colspan="2" bgcolor="#ffffff" height="8" valign="top"></td>
</tr>
</tbody></table>
</td>
</tr>
<tr>
<td bgcolor="#a9d46d" height="21" width="50%">□-
近期热门文章 </td>
<td bgcolor="#a9d46d" height="21" width="50%">□-
相关文章 </td>
</tr>
<tr>
<td bgcolor="#ffffff" valign="top" width="50%">
1.<a href="http://www.mydrs.org/program/list.asp?id=550" title="第九届信息学分区联赛一等奖名单" target="_top">
第九届信息学分区联赛一等奖名单
</a>[<font color="red">27707</font>]<br>
2.<a href="http://www.mydrs.org/program/list.asp?id=566" title="第十届分区联赛提高组参考答案" target="_top">
第十届分区联赛提高组参考答案
</a>[<font color="red">10985</font>]<br>
3.<a href="http://www.mydrs.org/program/list.asp?id=567" title="第十届分区联赛普及组试题" target="_top">
第十届分区联赛普及组试题
</a>[<font color="red">7763</font>]<br>
4.<a href="http://www.mydrs.org/program/list.asp?id=565" title="小议竞赛的准备和考试技巧" target="_top">
小议竞赛的准备和考试技巧
</a>[<font color="red">6481</font>]<br>
5.<a href="http://www.mydrs.org/program/list.asp?id=564" title="信息学分区联赛复赛备赛建议" target="_top">
信息学分区联赛复赛备赛建议
</a>[<font color="red">6312</font>]<br>
6.<a href="http://www.mydrs.org/program/list.asp?id=556" title="PC Logo for Win 研砉汉化版" target="_top">
PC Logo for Win 研砉...
</a>[<font color="red">5046</font>]<br>
7.<a href="http://www.mydrs.org/program/list.asp?id=570" title="【推荐】NOIP2004官方测试数据" target="_top">
【推荐】NOIP2004官方测试数据
</a>[<font color="red">4200</font>]<br>
8.<a href="http://www.mydrs.org/program/list.asp?id=559" title="NOI2004各省参赛队介绍" target="_top">
NOI2004各省参赛队介绍
</a>[<font color="red">4098</font>]<br>
9.<a href="http://www.mydrs.org/program/list.asp?id=560" title="NOI2004竞赛活动日程安排" target="_top">
NOI2004竞赛活动日程安排
</a>[<font color="red">4069</font>]<br>
10.<a href="http://www.mydrs.org/program/list.asp?id=571" title="NOIP2004提高组复赛试题" target="_top">
NOIP2004提高组复赛试题
</a>[<font color="red">4039</font>]<br>
</td>
<td bgcolor="#ffffff" valign="top" width="50%">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tbody><tr>
<td>
<a href="http://www.mydrs.org/program/list.asp?id=584">寻找必败态:博弈问题的快速解法</a><br>
</td>
<td width="160"> </td>
</tr>
</tbody></table>
</td>
</tr>
</tbody></table>
</td>
</tr>
</tbody>
</table>
<center>
<p style="font-size: 9pt;" face="宋体"><a href="http://www.mydrs.org/about.asp">关于本站</a> | <a href="http://www.mydrs.org/about.asp#3">访问方式</a>
| <a href="http://www.mydrs.org/about.asp#4">版权声明</a> | <a href="http://www.mydrs.org/contact.asp">联系方法</a><br>
<strong><a href="http://www.mydrs.org/"><font color="#00bb00" face="宋体">大榕树</font></a></strong>版权所有
<font arial="" helvetica="" sans-serif="" face="Arial," size="2">©2000-2004
<a href="http://www.mydrs.org/">www<font color="#cc0000">.MyDrs.Org</font></a>
<a href="mailto:mydrs@mydrs.org">MyDrs@MyDrs.org</a></font>
<script language="JavaScript">
var __cc_uid="drs";
</script>
<script language="JavaScript" src="%B2%A9%DE%C4.asp_files/count.js">
</script><a href="http://www.mydrs.org/count/supervise/index.asp?uid=drs" target="_blank"><img src="%B2%A9%DE%C4.asp_files/default.htm" alt="COCOON Counter 6" border="0" height="18" width="18"></a>
<iframe id="counter" border="0" vspace="0" hspace="0" marginwidth="0" marginheight="0" framespacing="0" src="%B2%A9%DE%C4.asp_files/index.htm" frameborder="0" height="0" scrolling="no" width="0">
</iframe>
</p>
</center>
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -