数学趣题/数学游戏 跟帖处

math618

In my gambling years, between the ages of eight and 12, I played roulette, poker, blackjack and any other game that had a three-cent ante. One of my favorite games, though, was one we called "Bluffhead." Each person takes a card from a shuffled deck and holds it, face out, to his or her forehead. In other words, players see everyone else's cards but not their own. The best card wins. Ace is high and suits don't matter, so ties are possible.
This puzzle has to do with inferring information about the cards people hold by hearing what the players say. To be concrete, suppose that we have three players. Caroline always speaks first, then David, then Jordan, and back to Caroline and so on. Each player makes one of the statements listed at the bottom right of this page. Assume the players are perfect logicians and reveal information only through these phrases; also, they say the strongest thing they can--that is, they choose the statement that is true and highest on the list.

To warm up, suppose Caroline says, "I don't know." Then David says, "I lose," and Jordan says, "I lose." Hearing all this, we (and the players) know Caroline must have an ace and the others do not. To understand why, see the illustration below.
Your Challenge: What can you infer about the cards from the following scenarios?

Game 1: Caroline says, "I don't know." David then says, "I don't win," and Jordan follows with, "I win."
Game 2: Caroline says, "I don't know." David then says, "I don't win," and Jordan follows with, "I tie as a winner."

Game 3: Caroline says, "I don't know." David then says, "I don't win," and Jordan follows with, "I don't win."

Game 4: Caroline says, "I don't know." David then says, "I don't know," and Jordan follows with, "I don't know." At the start of the next round, Caroline responds, "I lose." Can you predict what David and Jordan say next?

Game 5: Caroline, David and Jordan each say, "I don't know" in order, then say, "I don't know" in a second round. In the third round, Caroline and David say, "I don't know," but Jordan says, "I win." Which card does Jordan have, and what might he see?

wabadan

刚刚上来，还不知道什么什么的，请指教你的题目。

math618

<>[UseMoney=1000]</P>
<>1.Ramsey问题

    Ramsey问题可以看成是鸽巢原理的推广．下面举例说明Ramsey问题．

[例]　6 个人中至少存在３人相互认识或者相互不认识．
[证]　这个问题与K6的边２着色存在同色三角形等价．假定用红蓝着色． 设K6的顶点集为{v1 , v2 , ... , v6 }，dr(v)表 示与顶点 v 关联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数．在K6中，有 dr(v)＋ db(v)＝５，由鸽巢原理可知，至少有３条边同色．
　　现将证明过程用判断树表示如下：

2.若干推论

( a )　K6的边用红蓝任意着色，则至少有两个同色的三角形．

[证]　由前定理知，有同色三角形，不妨设 △v1v2v3是红色三角形 可由如下判断树证明．

( b )　K9 的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)．
[证]　设９个顶点为 v1 , v2 , ... , v9．对９个 顶点的完全图的边的红、蓝２着色图中， 必然存在 vi ，使得 dr(vi)≠3 ．否则， 红边数＝，这是不可能的．不妨设 dr(v1)≠3，可得如下判断树证明结论．

∴　K9的边红、蓝２着色，必有红色三角形或蓝色K4．
同理可证 K9的红、蓝２着色，必有蓝色三角形或红色K4 ．
  (红△ ∨ 蓝K4) ∧ (蓝△∨ 红K4)
＝存在同色K4或红△及蓝△
＝同色K4∨(红△∧蓝△)　

( c )　K18的边红，蓝２着色，存在红K4或蓝K4 ．
[证]　设18个顶点为v1 , v2 , ··· , v18 ．从v1引出的17条边 至少有９条是同色的，不妨先假定为红色．从而可得下面的判断树证明命题．


http://www.ekany.com/wdg98/zhsx/3/3_10.htm</P>
<>[/UseMoney]</P>

[此贴子已经被作者于2004-12-23 3:19:16编辑过]

math618

<>[UseMoney=1000]</P>
<>3.11 Ramsey数

    将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶 点的完全图的边任意红、蓝２着色，存在a个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如：
　　r ( 3 , 3 )＝6，r ( 3 , 4 )＝9，r ( 4 , 4 )＝18

1.Ramsey数的简单性质

[定理]　r ( a , b )＝ r ( b , a )；r ( a , 2 )＝a
[证]　Kr(a , b )的边红蓝２着色，有红Ka或蓝 Kb．将红蓝２色对换，就有红Kb或蓝Ka．
　  设r( a , b )＝r ，Kr的边任意红蓝２着色红蓝互换后仍是Kr的边的２着色，由r(a,b) 的定义，有红Ka或蓝Kb．再红蓝对换恢复原图有红Kb或蓝Ka．



[例]　K9的边任意红蓝２着色，有红三角形或蓝K4． 红蓝对换后，仍有红三角形或蓝K4，再对换一次，回到原来的着色方案， 有蓝三角形或红K4．
　　    第二个等式容易看出．Ka红蓝２着色若不全红(红Ka)， 则必有一条蓝边．

[定理]　当a , b ≥２时， r ( a , b )≤ r ( a －1 , b )＋ r ( a , b－1 )
[证]  对r ( a －1 , b )＋ r ( a , b－1 ) 个顶点 的完全图红蓝２着色．任取其中一点 v，有
dr(v) + db(v) = r( a －1 , b ) + r( a , b－1 )－1,从而可得判断树如下．


[定理]

2.Ramsey数的推广
　若将２着色改为k 着色，同色Ka或同色Kb改为同色 , i = 1 , 2 , … , k．即得Ramsey数r( a1 ,a2 ,… ,ak)． 对于给定的正整数 ai ( ai≥2) ，i = 1 , 2 , … , k．存在最小正整数r． 对Kr的边用k中颜色Ci( i = 1 , 2 , … , k)任意着色． 则存在 i ，出现全Ci色的．(即边都是Ci色的ai个顶点的完全图）； 这个最小正整数 r 用 r (a1 , … , ak)表示．

有 r(a1 , a2 , … , ak)≤ r(a1 , r( a2 , … , ak) )

[证]　设r(a1 ,r(a2 , … ,ak))=p， r(a2 , … , ak)=q；
对Kp的边２着色，出现第一色或第二色Kq， 用n－1中色对Kq的边着色，至少出现i色的ai点完全图， i = 2 , … , n．对Kp的边n 着色，将后n－1中色看作同一种色， 出现第一色或另一色(n－1种色看作另一色）的Kq．即出现第i色,，i = 2 , … , n. 故 r(a1 , a2 , … ,ak)≤p
[例]　r(3 ,3 ,3)=17
[证]　设三色为r ,b ,g．则对K17的任一顶点v ,有
　dr(v) + db(v) + dg(v) = 16；
因
故任一顶点与其他顶点的连线中，至少有６条同色．不妨设dr(v1)≥6, (v1v2)…(v1v7)都是红边．
从而可得如下判断树．


http://www.ekany.com/wdg98/zhsx/3/3_11.htm

Ramsey数的几个新下界公式</P>[/UseMoney]

[此贴子已经被作者于2004-12-23 3:20:06编辑过]

math618

《数学传播》中关于数学游戏的论文

amethyst

<><FONT size=2>回复21楼翻硬币（猜测）：   应该是可以复原的。   首先小于等于n是不行的，理由因为相临的2个肯定翻的次数相差1，因此有一个没复原。      如果是n+1 ，可以保证第A个和第A+1个翻的次数相同，但后面的不能保证，如果是n+2，可以保证A+1和A+2翻的次数相同，但A和A+1又不同了，所以要满足A，A+1，A+2翻的次数相同，必须是（n+1）*（n+2），依次类推要使n个翻的次数都相同，则需翻（n+1）*（n+2）*（n+3）……*（n+n）     又因为这个翻的次数是偶数，因此所有硬币都复原了。</FONT></P><><FONT size=2>本人能力有限，错误请指教，谢谢！</FONT></P><><FONT size=2></FONT> </P><P><FONT size=2> </FONT></P>

licannon

有这样一道题：

一辆汽车要通过一千公里的沙漠，这辆车的耗油量是1升/公里，汽车的载油量是500升。

求一个通过沙漠的方案，要求用油最省。

yushionly

<>对胡洁:  6-6;3-3;1-1</P><>就着样啊</P>

math618

<><b><FONT color=#0000ff>13人变12人！少的人哪去了？</FONT></b></P>
<> http://net.itdoor.net:88/uploads2/flash/shaoren.swf</P>

math618

<>一个过河问题</P>http://www.plastelina.net/games/logic3falls.swf