操作不变量
追踪一步怎样变化,找到整个过程都不变的量。
下载视频 ↗
视频加载失败,请确认assets文件夹完整,或下载MP4。
01
总和明明在变,什么没有变?
桌上有标着1、2、3、4的四枚筹码。每次任选两枚,数字记作 a、b,取走它们并放回一枚标着 a+b+1 的筹码,直到只剩一枚。最后的数字会因选择顺序而不同吗?
固定示范路径:每次合并当前最左边两枚
第1步 / 共4步:初始状态
1234
先分别观察总和与数量,再把两者相加。
对应左侧四枚筹码
14
总和增加1,数量减少1。
所以 S+n 保持14;终态数量是1,最后的数为14−1=13。
动画只展示一种选法。下文用任意 a、b 的变化证明所有合法顺序都满足同一关系。筹码大小不代表数值大小。
02
学习准备:从状态到一步变化
学习目标:能写清操作规则,寻找和、差、奇偶或余数不变量;能证明每一步都保持该量;能用终态约束排除目标,并用合法构造证明可达。
必要前置:整数四则、奇偶性、带余除法、用字母表示数。余数部分允许负整数,例如 −1=3×(−1)+2,所以−1除以3的余数取2。本页约定除数为正、余数在0到除数减1之间。
S班是本项目教学深度编排,不代表已核实的官方分班或六上必学范围。所有例题与练习均为自拟教学题。
03
为什么一步的证明,能管住整个过程?
状态是当前全部数字或物品的安排。操作不变量(Invariant)是对所有合法操作都保持相同的量或性质。它可以是一个精确数,也可以是奇偶性、除以某数的余数。
设起点状态为 X₀,不变量为 I。若对任一合法一步 X→Y 都有 I(X)=I(Y),那么沿任何有限合法路径 X₀→X₁→…→Xₖ,逐次应用这个等式可得 I(Xₖ)=I(X₀)。只验证几组数字不够:必须覆盖每一种合法操作。
合并题:把两个变化抵消
设当前总和 S、数量 n≥2,任选数字 a、b:
因此不变量是 S+n,总和 S 本身不是不变量。每一步都减少一枚,初始 N 枚经过恰好 N−1 步一定剩一枚;只要剩至少两枚就总能任选两枚继续操作。若初始和为 S₀,最后的数 x 满足:
x+1=S₀+N,故 x=S₀+N−1。
寻找不变量的常见入口
| 一步发生什么 | 候选不变量 | 仍需核实 |
|---|
| 一个量加c,另一个减c | 二者的和 | 每种操作都这样变化吗? |
| 两个量都加c | 二者的差 | 加的是同一个c吗? |
| 总和只改变偶数 | 总和的奇偶性 | 不能据此说总和不变 |
| 整数只加减m的倍数 | 除以m的余数 | m固定且为正;不等于已经可达 |
适用边界:先明确所有合法操作、终止条件、是否允许负数及是否必须操作固定次数。不变量只约束这些规则下的路径;改了规则就要重新证明。
04
两道完整例题:算终值,判目标
例题一 · 任意顺序的合并
把1到20合成一个数
黑板上写有整数1、2、…、20。每次任取两个数 a、b,擦去它们并写入 a+b+1,直至只剩一个数。求最后的数,并说明是否与选取顺序有关。
- 初始数量 N=20,总和 S₀=20×21÷2=210。
- 任意一步使和增加1、数量减少1,因此 S+n 始终等于210+20=230。
- 终态只有一个数 x,满足 x+1=230,因此 x=229。
- 过程必定经过19次合并,每次使和加1,也可核对210+19=229。无论选择哪两个数,不变量和步数结论都适用,所以终值与顺序无关。
逆向拓展:若初始10个整数按同一规则合并,最后得到100,则初始总和为100−9=91。这只确定总和,不能据此确定原来10个数分别是多少。
例题二 · S班结构变式:余数筛选+构造
从2出发,加6或减9,能到21或20吗?
当前数始终为整数,每次可以加6或减9,允许负数,不限操作次数。分别判断目标21和20是否可达。
- 每次变化是3的倍数,所以除以3的余数不变。起点2的余数为2。
- 21除以3余0,与起点不同,故21不可达,无需尝试所有操作顺序。
- 20除以3余2,只通过了必要条件检查。给出路径:2→8→14→20,连续加6三次,每一步合法,故20可达。
- 用次数复核:若加6用了 p 次、减9用了 q 次,则目标 y=2+6p−9q,p、q为非负整数。y=20时取p=3、q=0,确实满足;y=21要求19是3的倍数,矛盾。
本题允许负数,例如2→8→−1也是合法路径。若新增“每一步非负”等限制,需要再次检查构造是否越界。
05
迁移练习:先写一步变化
练习一 · 总和变了,奇偶性还在
黑板上写1到8。每次任取两个数 a、b,擦去后写入 |a−b|(即大数减小数),直至剩一个数。最后能是1吗?能是0吗?允许0和重复数字。
展开完整解析
若a≥b,新和等于 S−a−b+(a−b)=S−2b;若b≥a,同理为S−2a。每次总和减少偶数,故总和的奇偶性不变,但总和通常不保持原值。
初始和1+…+8=36为偶数。终态的数必须为偶数,所以不能是1。
0通过奇偶检查,仍需构造。先分别把(1,2)、(3,4)、(5,6)、(7,8)合为1,得到[1,1,1,1];再把两对1各合成0,得到[0,0];最后|0−0|=0。共7次,全部合法,所以能是0。
练习二 · 操作常数改变,组合也要改变
有标着2、5、8、11的四枚筹码。每次任取 a、b 换成 a+b+2,直到剩一枚。求最后的数,并找出一个不变量。
展开完整解析
总和每次增加2,数量每次减少1,因此 S+2n 不变。初始和26、数量4,不变量为26+2×4=34。
终态一个数x满足x+2=34,故x=32。直接构造核查:2、5合成9;9、8合成19;19、11合成32。总和26加上3次的增量6也是32。
不能机械照抄S+n。一般换成a+b+c(c固定)时,S+cn不变;N枚最终为S₀+c(N−1)。这一公式仍需N是正整数且每次操作恰好两枚换一枚。
06
关键反例:通过筛选,不等于有路可走
改规则:从2开始,只允许加3,能到−1吗?2和−1除以3都余2,因此余数相同;但每次只会增加,所有可达数为2+3k(k为非负整数),始终不小于2。所以−1不可达。
余数不变给出的是必要条件。在这条新规则下,大小的限制进一步排除了目标;原例题的“减9”已不允许,不能借用2→8→−1。
证明不可达
找到任一真正不变量,起点与目标的值不同,就能断定不存在合法路径。
证明可达
写出全部合法的有限步骤,或给出覆盖目标的构造证明。不变量值相同本身通常不够。
“始终增加”叫单调性质,并不是不变量。本反例用单调限制补充余数筛选;两类工具可以配合,但名称和证明作用要分清。
07
易错与回顾
- 观察几个状态就宣布不变:用任意合法a、b算出一步变化,才能覆盖所有选法。
- 把总和不变和奇偶不变混同:差值操作中和可能改变,只有和除以2的余数不变。
- 忽略数量也在变:尝试把总和、数量用固定系数组合,抵消变化。
- 终值唯一等于每个状态唯一:合并中间的数字可能不同,但终态数可以相同。
- 余数相同就说可达:继续检查非负、大小、次数和顺序限制,给出合法路径。
四步检查:写清状态与规则 → 证明一步不变 → 比较起点和终点 → 区分排除结论与构造结论。
08
逐章回看
文字稿默认展开。点击章节标题,可定位到视频中的对应讲解。
桌上有一、二、三、四四枚数字筹码。每次取两枚,换成它们的和再加一。
先把一和二换成四。总和从十变成十一,筹码数从四变成三。
继续合并,和每次增加一,数量每次减少一。它们的和一直等于十四。
设当前总和为S,数量为n。合并任意两数,新总和是S加一,新数量是n减一。
因此,总和加数量保持不变。这证明了所有合法选法,不只是动画这一条。
最终只剩一枚,它的数值加一等于十四,所以必定是十三。
再看整数操作:从二开始,每次加六或减九,允许负数。除以三的余数始终是二。
二十一除以三余零,因此不可达。二十余二,还要另找路径:连加三次六就能到。
但如果只允许加三,从二到负一,余数虽然相同,数却只会增加,仍然到不了。
不变量不同,足以排除;不变量相同,只是通过筛选。证明可达,还需合法构造。
09
图示与学习说明
数字筹码为抽象数学对象;示范路径展示一种合法选法,普遍性依据任意a、b的一步推导。本页内容经自拟推导与独立整数核算,不援引未经查证的竞赛出处。
下载视频 · 下载完整离线包