标题: 塌先生2005系列问题46 [打印本页]

---

作者: 塌鼻子先生    时间: 2005-9-6 17:17

这道题上次出过，因论坛故障丢失了。可惜的是几位朋友的回帖我还没看就不见了。再发一次吧，希望上次回帖的朋友也再回一次。

桌面上有2005堆火柴，根数分别为1，2，…，2005。二人参加游戏。规则是：二人轮流从中取出火柴，每次限制只能在其中一堆中取出任意根，不能同时在两堆中取（当然轮到你取时也不能不取，这其实与“不能同时在两堆中取”是等价条件）。谁取到最后一根谁获胜（Last Player Winning，简称LPW）。你为了保证获胜，应选择先取还是后取？如果你先取，第一次应在第几堆中取几根？当对方取了下一步后，你又应相应地采取什么策略？

如果将规则改为谁取到最后一根谁输（Last Player Losing，简称LPL），保证获胜的策略又相应有什么改变？

---

作者: 天宫公主    时间: 2005-9-7 01:36

对于LPW的战术想出来了, 此战术对小数实验几次基本无误, 其存在性也"基本"可以证明出来... 但对2005的具体计算麻烦一些(今天晚了, 不算了).

令在T步时, 每堆的个数为A_{T,1}, A_{T,2}, ... , A_{T,2005}.

把它们的二进位展开写出, 并且按二进位把全部数的单位相加(不进位的), 得K. 如果K=0, 则先走者必败, 如果非零, 先走必胜.

例1: (1,2,3,4) - 必胜
100
011
010
001
----
100 = K

例2: (1,2,3) - 必败
11
10
01
00
---
00 = K

证明(暂不完善): 假设(1,1), 显然先走必败. 假设任意K不等于零的情况, 先走方(甲)永远可以从一堆里取出若干根, 造成新局面的K等于零(我觉得这个不难证明, 但一时没完全想好). 因为火柴数一直在下降, 而对于乙K一直呆在零. 这样早完乙会面对(1,1)的必败局势.

---

作者: 天宫公主    时间: 2005-9-7 01:38

如果是LPL, 则应该按以上游戏的战术, 让对方走时的K保持在全1.

---

作者: 塌鼻子先生    时间: 2005-9-7 09:34

下面对本问题深入讨论中所需的数学概念做点解释。

每堆不超过七根的三堆火柴的制胜局势是：

（011）（022）（033）（044）（055）（066）（077）
（123）（145）（167）（246）（257）（347）（356）

并且制胜策略与“谁取最后一根谁输”（Last Player Losing，简称LPL）与“谁取最后一根谁赢”（Last Player Winning，简称LPW）无关，或者说LPL与LPW是博弈同构的。

“（123）（145）（167）（246）（257）（347）（356）”
叫做斯坦纳（Steiner）三元系。它的特征是括号内三个数的二进制表示的布尔和为0。

所有具有这个性质的博弈称为零和博弈。

斯坦纳三元系的性质被发现后，传统的Nim博弈的趣味顿时索然，所以人们管斯坦纳叫“游戏谋杀犯”（Games Killer）。“游戏”与“博弈”在英文中是同一个词：Games。这在数学史上是有名的掌故。

对两个N元组P：（a1，a2，…，aN）和Q：（b1，b2，…，bN），如果满足条件：
a1>b1，a2=b2，…，aN=bN
或a1=b1，a2>b2，…，aN=bN
……
或a1=b1，a2=b2，…，aN>bN
则称Q是P的后继N元组。

对全体N元组的集合U，如果它的一个子集K满足条件：
对任一P1属于K，它所有的后继N元组P2都不属于K；
对任一Q1不属于K，存在一个它的后继N元组Q2属于K，
这样的子集K叫U的“核”。

由此可知斯坦纳三元系就形成一个核。

下面再考察一个有序三元组（P，L，E），此处P和L是两个不相交的集合，而E是P×L的子集。
称P（POINT）中的元素为“点”，称L（LINE）中的元素为“线”。
E是关联关系，意义是指：如果对于点x∈P，线l∈L，有（ x，l）∈E，则称点x在线l上，或说线l经过点x，记为x∈l。
如果线l含有两点x，y，也称线l为线xy。
如果不同的三点x，y，z在一条线l上，则称x，y，z三点共线。

如果三元组（P，L，E）满足下列三条公理，则称这个三元组为“射影平面”：
（1）任意两个不同的点，恰好在一条线上；
（2）任意两条不同的线，恰好有一个公共点；
（3）存在四个点，它们之中任意三点不共线。

最简单的非平凡的射影平面，叫做法诺形（FANO）。它的点集P={x1,x2…,x7}，线集L={l1,l2…,l7}，每条线上所包含的点分别形成P的子集：
（x1,x2,x3），（x1,x4,x5），（x1,x6,x7），（x2,x4,x6），
（x2,x5,x7），（x3,x4,x7），（x3,x5,x6）
不难验证它们满足射影平面的公理（1），（2）和（3）。

显然法诺形就是斯坦纳三元系的几何解释。

我在这里详细解释一下射影几何学的基本概念，是为了说明，以下四个表面看上去截然不同的问题，在射影几何思想下实质是同一问题。

1.象棋残局：http://218.1.231.240/iqbbs/showimg.asp?BoardID=16&filename=2005-2/2005224161949629.jpg

2. 种7棵树，种成6行，每行3棵。

3. 3堆火柴，每堆不超过7根的NIM博弈。

4.  塌鼻子公司有七名保安：小安（A）、小毕（B）、小陈（C）、小邓（D）、小鄂（E）、小冯（F）和小郭（G）。每晚要派三人值夜班。请你排出一星期（七天）的值班表，满足以下两个条件：
（1）每人在一星期内恰好值班三次；
（2）任意两人恰好相遇一次。
这个问题在数学中叫平衡不完全区组设计（Balanced Incomplete Block Designs，简称BIBD）。

最简单的非平凡的射影平面法诺形有7个点，7=2^3-1. 如果谁能画出第二简单的有15个点的射影平面（15=2^4-1），就算牛B了。那就是著名的“寇克曼女生问题”。

---

作者: 金圭子    时间: 2005-9-7 10:03

图：
http://218.1.231.240/iqbbs/showimg.asp?Boa...24161949629.jpg
无效，内容为智星的字样？

---

作者: 天宫公主    时间: 2005-9-7 17:49

塌鼻子先生: 为什么制胜策略与“LPL”与“LPW”无关?

最简单的反例: (1,0,0,...) 对LPW是胜态, 对LPL是败态. 同理, (1,1,0,...)对LPW是败态, 对LPL是胜态.

---

作者: 塌鼻子先生    时间: 2005-9-7 19:17

回公主：

每堆不超过七根的三堆火柴的LPW制胜局势（Steiner三元系）是：
{（011）（022）（033）（044）（055）（066）（077）
（123）（145）（167）（246）（257）（347）（356）}

每堆不超过七根的三堆火柴的LPL制胜局势（Steiner三元系）是：
{（111）（022）（033）（044）（055）（066）（077）
（123）（145）（167）（246）（257）（347）（356）}

可以看出把LPW换成LPL，只要将第一个三元组（011）改成（111），其余13个三元组都不变。通常我们把除边际状态外博弈局势完全相同的两个博弈，称为同构的博弈。因此我们说NIM博弈与LPW或LPL的约定无关。

再举个极简单的巴什博弈（Bush Game）做例子。桌上有一堆N根火柴，两人轮流取，每次限取1~K（K<N）根。如果约定谁取到最后一根谁胜（LPW），则显然先取者的必胜策略是取N除以K+1的余数根。如果约定改为谁取到最后一根谁输（LPL），先取者的必胜策略是取N-1除以K+1的余数根。LPW（N）与LPL（N-1）等价，就说这两个博弈变换同构。

---

作者: 天宫公主    时间: 2005-9-7 20:00

那么2005元系呢?

P.S. 我第一贴的那个LPW方法应该对任意多堆的火柴都管用的... 不仅仅是三元系喔~~

---

作者: 凤凰涅槃    时间: 2005-10-21 22:02

射影几何这么难。。。。。。。。怪不得有一个数学家说射影几何就是全部的几何学。。。。。

---

作者: 凤凰涅槃    时间: 2005-10-23 11:16

原来是用到了四元组的制胜局势有如：
(2k,2k+1,2m,2m+1)或(k+1,k+1,m+1,m+1)或(0,1,2k,2k+1)或(0,0,k+1,k+1)形势，其中k,m为自然数
而(2k,2k+1,2m,2m+1)构成4元组的一个核

---

欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/)

Powered by Discuz! 5.0.0