中秋节，姥姥做了5张童年味儿的大饼
教育
教育
2024-09-16 12:03
海南
昍爸的数学思维课(第三期）已上线，目前有首发特惠团购活动，详情见：
我的家乡在江苏南部，儿时中秋不吃月饼，而是吃烤饼。
家乡有个传统习俗，每到中秋，家家户户都要做一些圆形的烤饼，各种馅料，有芝麻馅、豆沙馅、青菜馅、韭菜馅.....饼上洒上芝麻，放在刷上油的锅里烤熟，那阵阵香味，勾着人的味蕾。夜晚，一家人在葡萄架下支起桌椅，看着满天繁星，边吃饼边赏月聊天。两张大饼加两碗大麦粥，就是我童年中秋节的味道。现在虽然有各式各样的月饼，但是烤饼情结依然无法替代。两娃听了也垂涎欲滴，一再要求姥姥做几张香喷喷的烤饼给他吃。姥姥说，这烤饼的手艺也该传授给昍妈了。这不，她俩今天一大早就起来忙活了，洗豆沙、切韭菜、拌芝麻......先做了5种口味的大饼各一张。烤饼，现烤现吃最香。由于锅子小，每次只能烤一张。烤完一张，就放到盘子里，每次都放在盘子的最上面。每一次，孩子都是拿厨房盘子里最上面的那张饼，到餐桌上和大家一起分享吃完，然后再去厨房取。姥姥烤饼的速度时快时慢，孩子开始拿第一张饼的时间随机，大伙吃饼的速度也时快时慢。那么问题就来了：吃这五张饼的顺序一共有多少种不同的可能呢？一边吃烤饼和赏月，一边跟孩子探讨一下这个问题，会不会别有一番乐趣呢？其实，这对应于计算机里的栈。所谓栈，就是先放进盘子里的饼是后被拿出来的，你不能从底下抽出一张饼来吃。刚开始，有人可能会认为所有的顺序都可以，因此有5！=120种可能的顺序。如果有两块饼，编号分别为1、2，那么吃饼的顺序可以是1-2和2-1；如果有三块饼，编号分别为1、2、3，那么吃饼的顺序可以是1-2-3, 2-1-3, 1-3-2, 2-3-1, 3-2-1。注意，3-1-2这个吃饼顺序不可能。为什么呢？因为这个顺序表明，3号饼是第一个被吃的，此时，1号和2号饼都在盘子里，按放入的顺序，应该是1号在底下，2号在上面，那吃完3号饼后，应该吃2号饼才对。由此可见，有些顺序是不可能的！可如果饼的数量比较多，那怎么才能确定所有可能的顺序呢？对于n块饼的情况，假设总共的吃法数为f(n), 如果我们考虑最后一块吃的是哪一块饼，那可以分成n种情况：case 1: 最后吃的是1号饼，那表示1号饼一直位于盘子最底下，问题就变成了2~n这n-1块饼有多少种不同的吃法，吃完后再吃1号饼，总共的吃法数可以表示为f(n-1)；case 2: 最后吃的是2号饼，那表示在放入2号饼之前1号饼已经被吃掉了，而编号为3~n的这n-2块饼则是在放入2号饼之后到最后吃2号饼之前被吃掉的，这n-2块饼有f(n-2)种吃法；根据乘法原理，共有f(1)×f(n-2)种方法；case i：最后吃的是i号饼，那表示在第i号饼放入之前就吃完了1~i-1号饼，有f(i-1)种吃法，而i+1~n号饼则是在放入i号饼之后到吃i号饼之前被吃完，这n-i块饼有f(n-i)种吃法；根据乘法原理，共有f(i-1)×f(n-i)种吃法；
case n: 最后吃的是n号饼，那表示1~n-1号饼在放入n号饼之前已经被吃完了，对应于f(n-1)种吃法；f(n)=f(n-1)+f(1)f(n-2)+...f(i-1)f(n-i)+...+f(n-1)如果我们定义f(0)=1, 那么就有下面的递推关系：f(3)=f(0)f(2)+f(1)f(1)+f(2)f(0)=5f(4)=f(0)f(3)+f(1)f(2)+f(2)f(1)+f(3)f(0)=14
f(5)=f(0)f(4)+f(1)f(3)+f(2)f(2)+f(3)f(1)+f(4)f(0)=42
我们可以把这个问题进行转化。我们把放一张烤饼看成是横着走一步，吃一块烤饼看成是竖着走一步，那么最后问题就变成了从5×5方格的(0,0)点开始，第一步向右走，最后走到(5,5)，期间不穿过蓝色对角线（但可以碰到），一共有多少种不同的走法？我们可以首先考虑所有的走法，也就是不管穿不穿过对角线，也不限定第一步的方向，一共有多少种走法？这等价于从10步中选择5步向右走，共有C(10,5)种走法。然后，我们再去掉穿过对角线的走法即可（我们将第一步向上走也看成是穿过对角线）。我们将格子向左多画一列，同时将对角线向左平移一格，从而穿过蓝色对角线就等价于与红色线相交（碰到或穿过）。我们考虑（0，0）点关于红色线的对称点(-1, 1)。从(-1, 1）走到(5, 5)一共有C(10, 4)种走法（10步中选择4步向上），并且每一种走法都穿越红色线。对于每一条从(-1, 1)到(5,5)的路线，我们都可以将其映射成一条从(0,0)到(5,5)的路线。例如上图中绿色实线的路径，我们假设路径与红线的第一个交点为P。我们将从(-1, 1)到P的路线沿着红线做对称，也就是图中绿色虚线部分，然后将绿色虚线与P点到(5,5)的绿色实线连在一起，就得到了一条从(0, 0)到(5, 5)的路径，而且这条路径一定与红色线相交。可以看到，这种对应是一对一的。因此，所有满足条件的路线总数为：C(10,5)-C(10,4)=42种。假设烤饼先后出锅的编号顺序为1,2,3,4,5，那么下面哪些是不可能的吃饼顺序？作者：昍爸，中国科学院计算机博士，大学教授，博士生导师。主持国家自然科学基金4项，在国内外高水平期刊和会议发表论文60余篇。曾获初中和高中全国数学奥林匹克联赛一等奖，江苏赛区第一名，高考数学满分。著有畅销书《写给孩子的数学之美》、《搞定平面几何：辅助线是怎么想出来的》、《给孩子的数学思维课》与《给孩子的数学解题思维课》。关于昍（xuan)爸的其它课程介绍，请看下面几篇文章：
