T.11 · Weak compositions, loop invariants and flowchart tracing
GRE Subject Test · GRE Mathematics Topic 26 3:02 English narration · English + 中文 subtitles burned in
Chapters
Transcript
This unit counts indistinguishable allocations with nonnegative or positive constraints, traces a flowchart in statement order with correct resets, and uses a loop invariant and a progress measure to justify an algorithm.
本单元在非负或正的约束下计数不可区分对象的分配，按语句顺序追踪流程图并正确处理重置，并用循环不变量和进展量证明算法正确。
Represent n identical stars split into k named boxes by k minus 1 bars; adjacent bars and end bars allow zero entries.
把 n 个相同的星号用 k − 1 根竖线分进 k 个有名称的盒子；相邻竖线或末端竖线表示空盒。
So nonnegative solutions number n plus k minus 1 choose k minus 1.
所以非负解的个数是 C(n + k − 1, k − 1)。
Distinct tokens would be assigned independently instead.
若对象互不相同，则每个对象独立分配。
For positive allocations put z i equals x i minus 1; the total drops to n minus k, giving n minus 1 choose k minus 1.
对正的分配，令 zᵢ = xᵢ − 1；总数减为 n − k，得 C(n − 1, k − 1)。
At least one zero is the complement of all positive.
“至少一个为零”是“全为正”的补。
Subtracting each empty-box case independently double-counts their overlaps.
逐个减去空盒情形会重复计算它们的重叠部分。
Trace one executed statement at a time; the right side of an assignment uses the old value.
一次追踪一条执行的语句；赋值右边用的是旧值。
Adding 1, 3, 5 from zero keeps S equal to m squared, since m squared plus 2m plus 1 is m plus 1 squared.
从零开始加 1、3、5……使 S 保持为 m²，因为 m² + 2m + 1 = (m + 1)²。
An invariant alone does not prove termination: S must also grow to reach N.
仅有不变量不能证明终止：S 还必须增长直到达到 N。
Eleven identical tokens in 4 named boxes: 364 nonnegative allocations, 120 all positive, so 244 have an empty box.
11 个相同的代币放入 4 个有名称的盒子：非负分配 364 种，全为正 120 种，所以有空盒的有 244 种。
For the odd-sum test with N=10, S progresses 0, 1, 4, 9, 16: it overshoots and rejects 10.
对 N = 10 的奇数和检验，S 依次为 0、1、4、9、16：超过后拒绝 10。
For N=9 it exits at S=9 after three additions.
对 N = 9，三次相加后在 S = 9 处退出。
Identical objects and distinct objects use different models.
相同对象与不同对象使用不同的模型。
At least one empty box is not the same as exactly one.
“至少一个空盒”不同于“恰好一个空盒”。
In a flowchart, keep the update order and reset only the variables the executed path resets.
在流程图中，保持更新顺序，只重置实际执行路径所重置的变量。
Put u equals a minus 2: then u plus b plus c equals 6 has 28 solutions.
令 u = a − 2：则 u + b + c = 6 有 28 个解。
Requiring b and c positive leaves total four, 15 solutions.
要求 b、c 为正，剩下总数 4，有 15 个解。
So 13 have b or c zero, matching 7 plus 7 minus the 1 counted twice.
所以 b 或 c 为零的有 13 个，与 7 + 7 − 1（重复计算的 1 个）相符。
After m iterations S is m squared and k is 2m plus 1.
m 次迭代后 S = m²，k = 2m + 1。
The pairs run 0, 1; 1, 3; 4, 5; 9, 7; 16, 9.
数对依次为 (0, 1)、(1, 3)、(4, 5)、(9, 7)、(16, 9)。
So 15 is rejected by overshoot and 16 accepted.
所以 15 因超过而被拒绝，16 被接受。
The sum grows without bound, so the loop ends; for N equals 0 it is skipped and equality holds.
和无限增长，所以循环会结束；N = 0 时循环被跳过，等式成立。
Check yourself.
自我检测。
364 nonnegative allocations, 120 positive.
非负分配 364 种，全正 120 种。
The odd-sum loop keeps S equal to m squared.
奇数和循环保持 S = m²。
An invariant alone does not prove termination.
仅有不变量不能证明终止。
And 15 is rejected.
15 被拒绝。