Author Topic: 每周一题: 赌博加倍 (9/6/04 -- 9/12/04)  (Read 8180 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 赌博加倍 (9/6/04 -- 9/12/04)
« on: 九月 06, 2004, 06:41:19 pm »
上周题目讨论:

上周的题目由方信做出来。我出它的原因是因为他的最简单解就是构造一个边长为
K的全等三角形,然后取离各顶点距离为A,B,C各点,则不等式右边相当于大
三角形的面积,左面相当于三个小三角形的面积。一道代数题被简化成几何题,正
好接上我们前面的那些几何题。

前几次的题目都相对简单一些。这次来一个难一点的。其实说难也不是很难,只要
想对了思路还是很清楚的。

本周题目:

三个人进行赌博。规则很简单,每次由两人比钱,钱少的那个人可以从钱多的那个
人那里拿钱使自己的钱加倍。如果两人钱相等,则用投硬币决定。比如,甲有X块
钱,乙有Y块钱,X〈=Y,赌一轮下来,甲便有2X块钱,乙剩下Y-X块钱。
试证明,不管各人口袋中初始钱的数量如何,他们都可以通过这种赌法使一个人输
光。假设有人输光以后对大家都有好处,比如可以提前睡觉,所以他们总是努力想
法缩短赌博时间,我们的问题是他们是不是总能让一个人的钱输光。

方信

  • Newbie
  • *
  • Posts: 15
每周一题: 赌博加倍 (9/6/04 -- 9/12/04)
« Reply #1 on: 九月 09, 2004, 08:58:45 pm »
证明思路如下

引理一:如果两个人的数目是一奇一偶,而且互质的话,在一定数目的比较之后,总可以使其中任意一个的数目变为一。也就是说有限次比较后,我们可以表示两个人的数字为 1, 2n

证明:注意到每次交换之后,总有
      2x = 2 * x (mod x+y)
     y-x = 2 * y (mod x+y)

也就是说每次比较使得双方的数目翻倍,在模总和的基础上。

设s是两个人的总数目, 两个人之间的每次比较保持总和不变。而且每次比较后,两个人的数字保持互质, 且和总和互质。

由于x 和 s 互质,且2和s互质,存在 k 使 2^k * x = 1 or -1 (mod s) 成立。

(我开始觉得很显然,后来发现我证明不了,:( 万教授,这个是不是成立啊?)

引理二:如果两个人的总和是2^n * (2k+1), 那么在有限次地交换之后,两个人的数目总是可以表示成 2^n * x, 2^n * y and x+y = 2k+1

引理三:两个人在有限次之后,总可以使其中一人的数字为零,或者一人是另一人的倍数。
约掉共因子, 再根据引理一和二可以得到引理三。


如果上面三个引理都成立的话,我们可以按照下述方法归纳证明总有一系列的交换方法,使得最后总有人的数目为零。也就是说,总可以想着法子让人输光。


如果有一人为零,则命题成立, 

otherwise
如果任两人的数字相等的话,则两人交换之后有人为零

otherwise

如果三人的数目有公因子的话,可以将每个人的数字约掉公因子再进行相同的交换。

otherwise

如果三人总数是偶数,而且有两个是奇数的话,可以让两个奇数的人先交换,这样三个人的数度是偶数,这样三个有公因子。

otherwise
如果一个人的数是奇数,而且其他两个都是偶数。

让奇数的人和其中一个偶数的人比较, 根据引理三,在有限次比较后,我们有
两个人的数字会成为, n, 2k*n, 而且n 是奇数

现在在让拿n 的人再和第三人比较。n 和第三人互质,否则可以约掉共因子。


根据引理一, 我们可以让其中的一人数字变为 1。

再让另外两人交换,则有限次比较之后,根据引理三,一人的数字将是另一人的倍数。设为, k, nk

再让 1 and nk 比。1-> 2, nk -> nk-1

在让 k and nk-1 比, 由于k and nk-1 互质,他们在有限次比较后, 有人将变为1, 再比一次有人变为2.

再让2和2比,有人变为零。


不知道对不对,或者更简单的方法

sean

  • Jr. Member
  • **
  • Posts: 86
"Lemma 1" does not hold
« Reply #2 on: 九月 09, 2004, 11:14:52 pm »
5, 12
    10, 7
    3, 14
    6, 11
    12, 5

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 赌博加倍 (9/6/04 -- 9/12/04)
« Reply #3 on: 九月 10, 2004, 09:34:58 am »
Hint: There's a reason that this is a 3 people game, don't get stuck on two people exchanges.

方信

  • Newbie
  • *
  • Posts: 15
每周一题: 赌博加倍 (9/6/04 -- 9/12/04)
« Reply #4 on: 九月 10, 2004, 10:20:31 am »
Thanks Sean for the example.

Lemma 1 was the foundation of my thinking. Seems I stuck in the wrong direction.

sean

  • Jr. Member
  • **
  • Posts: 86
依万教授提示做出 (详细解说)
« Reply #5 on: 九月 13, 2004, 01:35:10 am »
上周贴出解答的时候, 是根据万教授在另一个贴子中对这题的提示做的.  我没有把该提示引在这里, 可能使解答思路显得不是很清楚.  当时我觉得有他的提示后, 问题已经很简单了. 修改如下.

"提示:如A,B,C三人中A的钱最 少,则可以通过一系列B,C往A上输钱使B所剩的钱数少于A的初始钱数。以此类推,可以把最小钱数变成零。"

[我现在给出算法来完成这一步骤]


假设A, B, C 分别有钱X, Y, Z 元, 并不妨假设 0<X<=Y<=Z.   可以找到正整数U 和非负整数W,  使得W<X 并且 Y=X*U+W.  我们的目标是把X*U 从Y 中去掉,  从而使 min{X, Y, Z}=W, 小于最先的X.  算法如下:
   
            当 U>0 时重复以下操作:
            1)  如果 U 是奇数: 令 Y:=Y-X,  X:=X+X,  U:=(Y-W)/X;
            2)  如果 U 是偶数: 令 Z:=Z-X, X:=X+X,  U:=(Y-W)/X;
 
         
因为 X 不断增大,  Y 没有增大, 所以 U 值不断减小,  最终为零.  实际上, 每经过一次 1) 或 2) 的操作, 当前的U 值变为前一个U值的一半的整数部分(U_new=[U_old/2]).  需要说明的是,  当 U 大于 1 时,  当前的 Y 和 Z 值都比当前的 X 值大,  所以 无论 1) 还是 2) 里的操作都没有问题.  当 U 等于 1  时,  需要执行 1),  这时候 Y>=X, 仍 没有问题.  最终 Y=W, 而 W<X, 所以我们把min{X, Y, Z}   变小了.  

下面就是对新的X, Y, Z 值重新按大小排序,  再计算 新的U, W,  再用以上算法缩小 min{X, Y, Z}.  经过有限步后,  min{X, Y, Z}=W=0, 有人输光.

比如说,   (X, Y, Z)=(4, 39, 41), 那么 35=4*9+3, U=9, W=3. 变换过程是 (X, Y, Z, U, W)=(4, 39, 41, 9, 3) => (8, 35, 41, 4, 3) =>(16, 35, 33, 2, 3) => (32, 35, 17, 1, 3)=>(64, 3, 17, 0, 3).  在这个过程中,  U 不断减小, X 不断加倍, Y 不断减少.  

现在{ X, Y, Z}={64, 3, 17},  经过重新排序后,  X=3, Y=17, Z=64.  因为 17=3*5+2, U=5, W=3.  再经过以上类似操作,  
(X, Y, Z, U, W)=>* (24, 2, 58, 0, 2).  现在min{X, Y, Z}=W=2,  再经过最后一次类似操作即可让一人输光.