一道小学奥数题，有没有更好的算法？

天山草

小学奥数题：
常昊与古力两人进行围棋“棋圣”冠军争霸赛，7局4胜制。谁先胜4局即获得比赛的胜利。请问：比赛过程共有多少种不同的方式？  

我的解答如下：

先假定是常昊获胜。
如果共赛了7场，那么其中常昊必须胜4场。计算这7场的可能比赛过程数目，相当于有4白3黑共7个小球（白球表示胜，黑球表示负）进行排列，且已知最后一个球是白球（由于前面已假定是常昊获胜，所以最后一场比赛应是常昊胜，无论是比赛几场都有这个结论），有几种排列方法？
既然已知7个球中最后一个是白球，那就只须对3白3黑进行排列即可。如果6个球是各不相同的，排列数目等于 6!=1×2×3×4×5×6，现在是其中的3个元素相同，另外3个也相同，排列数目就减少为 6!/(3!×3!)=(3!×4×5×6)/(3!×(1×2×3))=(4×5×6)/(1×2×3)=20 种。
如果共赛了6场，相当有4白2黑共6个球排列，已知最后一个球是白球。于是只须对3白2黑进行排列，共有 5!/(3!×2!)=(3!×4×5)/(3!×(1×2))=(4×5)/(1×2)=10 种情况。
如果共赛了5场，相当有4白1黑共5个球排列，已知最后一个球是白球。于是只须对3白1黑进行排列，共有  4!/(3!×1!)=(3!×4)/(3!×1)=4 种情况。
如果共赛了4场，这4场常昊必须全胜。只有这1种情况。
因此常昊获胜共有20+10+4+1=35种可能的比赛情况。
同样，古力获胜也有35种可能的比赛情况。所以共有70种情况。

天山草

搜一下网上对此题的答案，没有上面这样做的。都是直接给出答案：



上面这个答案是怎样来的？

天山草

上面这个答案是怎样来？不知道呀。

我只知道主帖的方法可以通过下面这个恒等式变成楼上的做法：



但是如果不通过上述恒等式，又如何知道 2# 楼的做法呢？

elim

4胜之局次有C(7,4)=35种安排,谁胜有两种安排. 共 2*C(7,4)=70 种安排.

elim

4胜之局次有C(7,4)=35种安排,谁胜有两种安排. 共 2*C(7,4)=70 种安排.

王守恩

elim 发表于 2017-5-30 22:27
4胜之局次有C(7,4)=35种安排,谁胜有两种安排. 共 2*C(7,4)=70 种安排.

7个不同盒子装3个球（每个盒子装0个或1个）+7个不同盒子装4个球（每个盒子装0个或1个）
=3个苹果，4个李的排列+4个苹果，3个李的排列
=C(7,3)+C(7,4)=2*C(7,3)=2*C(7,4)=C(8,4)

天山草

     先假定是常昊获胜，也可以画出下面这个方格阵图计算：



     从左下角开始向右边的红线走，走到红线即获胜，只能向右、向上走。向右走一格表示这一局是常昊胜，向上走一格表示这一局是古力胜。在方格每个交叉点上写一个数字，其值等于左边数字与下边数字之和（红线上的数字，只能等于左边的数字，不要加下面的数字。因为到达红线以后就不再往上走了）。最下面一行表示常昊4局全胜；从下往上数第二行，表示古力胜了一局，常昊胜了四局，共有4种情况；余类推。所以红线上的各个数字相加的和即是常昊获胜时的所有可能过程，共有35种。古力获胜也可以画同样的图，也有35种情况，所以共有70种情况。

       那么，有没有办法不对每个格点都进行计数，而直接算出从左下 角走到右边红线有几种走法呢？

天山草

用 mathematica 编程计算:

1. a = Permutations[{1, 1, 1, 1, 2, 2, 2},
   
2.    7];   (*常昊和古力 7 局 4 胜比赛，常昊最终获胜的所有可能过程。1 表示常昊胜，2 表示常昊败。 *)
   
3. LL = Length[a]; (* 1,1,1,1,2,2,2 这七个数字，可能的排列有多少种？包括空集在内 *)
   
4. n = 0; (* 常昊最终获胜的所有可能过程共有多少种？ *)
   
5. i = 1; While[i <= LL,
   
6. s = Count[a[[i]], 1]; (* 上述第 i 个排列中，其中的 1 有几个？ *)
   
7. L = Length[a[[i]]]; (* 上述第 i 个排列的长度是几，也就是打了几局？ *)
   
8. b = a[[i]];  (* 取出上述第 i 个排列 *)
   
9. If[s == 4 && b[[-1]] == 1 && 4 <= L <= 7 , n = n + 1;
   
10.   Print[n, "----- ", a[[i]]]];
    
11. (* 共赛4局至7局，常昊都胜4局且最后一局也胜。这些就是常昊最终获胜的所有可能过程。 *)
    
12. i++
    
13. ];

复制代码

程序运行结果：
1----- {1,1,1,1}

2----- {1,1,1,2,1}

3----- {1,1,2,1,1}

4----- {1,2,1,1,1}

5----- {2,1,1,1,1}

6----- {1,1,1,2,2,1}

7----- {1,1,2,1,2,1}

8----- {1,1,2,2,1,1}

9----- {1,2,1,1,2,1}

10----- {1,2,1,2,1,1}

11----- {1,2,2,1,1,1}

12----- {2,1,1,1,2,1}

13----- {2,1,1,2,1,1}

14----- {2,1,2,1,1,1}

15----- {2,2,1,1,1,1}

16----- {1,1,1,2,2,2,1}

17----- {1,1,2,1,2,2,1}

18----- {1,1,2,2,1,2,1}

19----- {1,1,2,2,2,1,1}

20----- {1,2,1,1,2,2,1}

21----- {1,2,1,2,1,2,1}

22----- {1,2,1,2,2,1,1}

23----- {1,2,2,1,1,2,1}

24----- {1,2,2,1,2,1,1}

25----- {1,2,2,2,1,1,1}

26----- {2,1,1,1,2,2,1}

27----- {2,1,1,2,1,2,1}

28----- {2,1,1,2,2,1,1}

29----- {2,1,2,1,1,2,1}

30----- {2,1,2,1,2,1,1}

31----- {2,1,2,2,1,1,1}

32----- {2,2,1,1,1,2,1}

33----- {2,2,1,1,2,1,1}

34----- {2,2,1,2,1,1,1}

35----- {2,2,2,1,1,1,1}

天山草

阿瓜和阿呆今天又来看帖。
阿呆对阿瓜说：瓜哥，我今天总算弄明白了，这个问题的最简计算方法，为什么是 C(7,4) 组合。
阿瓜说：噢，呆子，我这几天也一直在想这个事，还没有想通，你倒先清醒了，真的假的？
阿呆：你听我慢慢道来。假如是常昊最终获胜，对于每一种可能的比赛过程，你说会不会有一种是常昊胜了 5 局或是胜了 3 局？
阿瓜：那当然不会，7 局 4 胜么，没有胜够 4 局就得继续下，够了 4 局战斗就结束了，不用再下了。
阿呆：比如说一共下了 5 局，常昊胜了 4 局, 输了1局，那 2 局不下的话，能不能算是这 2 局古力赢？
阿瓜：我觉得可以。因为即使算古力赢，他也只是胜了 3 局，不会动摇常昊获胜这个结论。
阿呆：对呀，也不会影响比赛过程有多少种可能性的答案。
阿瓜：那又怎样？
阿呆：如果我有 7 个小球，其中 4 个是白球， 3 个是黑球，把它们放进一个口袋里。每次从袋里摸出一个球，放在桌子上，然后再摸一个，放在前面小球的后面，一直到摸出桌上有 4 个白球为止。这时候记录下桌子上黑白球的次序，如果白球代表赢，黑球代表输，你说，桌子上的这个黑白球次序算不算是一种可能的比赛过程？
阿瓜：那还用说，是其中的一种么。
阿呆：这时候袋子里是不是没有白球了？还要把袋子里剩余的黑球拿出来，排在桌子上其它小球的后面吗？
阿瓜：那随便，拿不拿出来都无所谓了。
阿呆：那我就把剩下的黑球都拿出来，这样好算账。
阿瓜：算什么账？
阿呆：4 白 3 黑进行全排列，有多少种可能的不同排列情况？
阿瓜：噢，也就是常昊获胜有多少种可能的不同过程。
阿呆：如果换成 4 黑 3 白进行全排列，黑代表古力赢棋，也应该有相同的结果吧？
阿瓜：那当然，所以总的获胜过程数目就等于 4 白 3 黑这 7 个小球全排列数目的 2 倍。
阿呆：怎样计算这个全排列，小学生五年级奥数讲过，大概小朋友们都忘记了，叫做“有重复元素的排列计算”，公式是 7!/(4!3!)。如果 7 个元素各不相同，全排列数目是 7 的阶乘，没有那个分母了。
阿瓜：你上面那个有分母的公式，我看着跟计算组合的公式很像啊。7个元素各不相同，从中取出 4 个，有多少种可能的组合方式？公式是 C(7,4)=7!/(4!(7-4)!)=7!/(4!3!)，跟你上面的公式一模一样哈。
阿呆：没错，这不就是本帖 2# 楼那个网上的解法吗？
阿瓜：我算算，结果是7!/(4!3!)=35，再乘以2得70。这就是所谓的最简单算法了。
阿呆：这都不算啥，3# 那个恒等式，我也明白为什么成立了。
阿瓜：是的，那个恒等式，不用数学归纳法，从这个方面着手，也可以证明了。

elim

1. 如果一定要打够 7 局，再判定胜 4 局者获胜，可以这样做。但实际上也许只打 5 局就已决出胜负了呢？

复制代码

7 恰取 4 为胜排除了不必要的赛局.

换句话说，选手甲胜的可能安排与他赢局的分布是一一对应的．