Weak compositions, loop invariants and flowchart tracing
Introduced| English | Meaning |
|---|---|
| stars and bars/stɑːz ænd bɑːz/ | A bijective method for counting nonnegative integer allocations of identical objects among named boxes without upper capacities. |
| complement/ˈkɒmplɪmənt/ | The set of elements in a specified universal set that do not belong to the given set. |
| invariant/ɪnˈveərɪənt/ | A quantity or property that remains unchanged throughout a specified process or transformation. |
Identical tokens, named boxes
- Eleven identical reward tokens go into four named boxes, with no capacity limits and empty boxes allowed. The outcome records only the four counts. It is not $4^{11}$: that would distinguish the tokens.
- We will use stars and bars 隔板法, complements 补集 and exact empty-box counts, then trace a square-sum algorithm. Loop invariants 不变量 connect the values in a trace to a proof about every pass.
State the allocation model first
- Let $n\ge0$ and $k\ge1$ be integers. Identical objects in $k$ named boxes correspond to nonnegative integer counts $x_1+\cdots+x_k=n$. There is no order inside a box and, for the basic formula, no upper capacity.
- If the objects are distinct, changing which object enters a box can change the outcome. If boxes are unnamed or capacities are imposed, the basic count also changes. Decide what makes two outcomes different before choosing a formula.
Why stars and bars is a bijection
- Place $n$ stars and $k-1$ bars in one row. Reading left to right, the bars separate the counts for boxes 1 through $k$. End bars and adjacent bars are allowed: they record empty boxes.
- For six tokens in four boxes,
***||**|*represents $(3,0,2,1)$. Conversely, each allowed count tuple builds exactly one such row. Choosing the bar positions among $n+k-1$ places therefore counts allocations without duplication.
Count nonnegative solutions
- The number of weak compositions is $\binom{n+k-1}{k-1}$. For the original $x_1+x_2+x_3=8$, choose two bar positions among ten: $\binom{10}{2}=45$. For eleven tokens in four boxes, the count is $\binom{14}{3}=364$.
- Boundary cases matter. With no tokens there is one allocation, all counts zero. With one box there is one allocation, all tokens in it. The formula agrees in both cases; it does not require every box to be used.
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 8$ have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Stars and bars: 8 stars and 2 bars, so C(8 + 2, 2) = C(10, 2) = 45 non-negative solutions.
How many allocations put zero identical tokens into four named boxes, with empty boxes allowed?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
There is exactly one tuple: (0,0,0,0). The stars-and-bars count is C(3,3)=1.
Remove lower bounds by substitution
- If each $x_i\ge1$, set $z_i=x_i-1\ge0$. When $n\ge k$, the residual total is $n-k$ and the count is $\binom{n-1}{k-1}$. If $n<k$, there are no such allocations. The original four positive counts summing to 9 give $\binom83=56$.
- More generally, for integer lower bounds $x_i\ge\ell_i\ge0$, subtract all the lower bounds first. For $x_1+x_2+x_3=8$ with bounds 2, 1 and 0, the residual total is 5, giving $\binom72=21$. A negative residual means no solutions.
How many positive integer solutions does $x_1+x_2+x_3+x_4=9$ have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Set yᵢ = xᵢ − 1 ≥ 0, so y₁ + … + y₄ = 5. Stars and bars: C(5 + 3, 3) = C(8, 3) = 56.
Count integer solutions of $x_1+x_2+x_3=8$ with $x_1\ge2$, $x_2\ge1$, $x_3\ge0$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Subtract lower bounds 2,1,0, leaving three nonnegative counts totaling 5. The count is C(7,2)=21.
Use a complement for at least one empty box
- Within the full set of allocations, the complement of “at least one box is empty” is “every box is nonempty.” For eleven tokens and four named boxes, all-positive allocations number $\binom{10}{3}=120$.
- Thus $364-120=244$ allocations leave at least one box empty. Subtract the complement once; subtracting four single-empty-box events separately would mishandle allocations with several empty boxes.
Exactly r empty boxes is a different event
- For $n>0$ and exactly $r$ empty boxes, first choose those boxes in $\binom kr$ ways. Put positive counts in the other $k-r$ boxes. If $1\le k-r\le n$, the count is $\binom kr\binom{n-1}{k-r-1}$; otherwise it is zero.
- With eleven tokens and four boxes, exactly two empty gives $\binom42\binom{10}{1}=60$. The counts for zero, one, two and three empty are 120, 180, 60 and 4, summing to 364. For $n=0$, all $k$ boxes are empty in the single allocation.
Eleven identical tokens go into four named boxes. How many allocations have exactly two empty boxes?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Choose the two empty boxes in C(4,2)=6 ways. Split 11 positively between the remaining two in C(10,1)=10 ways. Multiply to obtain 60.
Twelve identical tokens go into four named boxes, each receiving at least two. Count all such allocations, then count those with at least one box receiving exactly two.
Check the allocation conditions or the exact loop checkpoint before comparing your answer.
Upper bounds require overlap corrections
- Count $x_1+x_2+x_3=8$ with $0\le x_i\le3$. Start with 45 unrestricted allocations. For a specified violation $x_i\ge4$, subtract 4 from that coordinate: there are $\binom62=15$ such allocations.
- Subtracting $3\cdot15$ removes pairwise violations twice. For each of the three pairs, two counts at least 4 leave residual zero, giving one allocation to add back. No triple violation fits, so the answer is $45-45+3=3$: the three permutations of $(3,3,2)$.
How many integer solutions of $x_1+x_2+x_3=8$ satisfy $0\le x_i\le3$ for every i?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Only the three permutations of (3,3,2) fit. Inclusion-exclusion gives C(10,2)-3C(6,2)+3C(2,2)=45-45+3=3.
Count integer solutions of $x_1+x_2+x_3=7$ with $0\le x_i\le3$. Use overlap counting and check by listing the possible count patterns.
Check the allocation conditions or the exact loop checkpoint before comparing your answer.
Distinct objects use independent choices
- For $n$ distinct objects and $k$ named recipients, with no capacities and no order inside a recipient's collection, each object chooses one recipient. The count is $k^n$. Five different books given to three students therefore have $3^5=243$ allocations.
- This counts which books each student gets, not the order of handing them out. If every student must receive a book, exclude empty-student events and add back their pair overlaps: $3^5-3\cdot2^5+3=150$. Positive stars and bars would not apply to these distinct books.
Which counting model matches the stated conditions?
Use object identity and allocation constraints, not just a familiar formula.
Five different books are given to 3 students (a student may get none). How many ways?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each distinct book picks a student.
Specify the odd-sum loop
- Let the input $N$ be a nonnegative integer. Use exact integer arithmetic and a pre-test loop: test the guard before the first pass and before each later pass. Here $m$ counts completed additions, and $B$ stores the next odd addend.
S ← 0
m ← 0
B ← 1
WHILE S < N
S ← S + B
m ← m + 1
B ← B + 2
ENDWHILE
- The assignments execute in the written order. Each right side uses the values available when that statement runs; these are sequential updates, not a simultaneous replacement of all three variables.
Trace one statement at a time
- For $N=10$, the initial state is $(S,m,B)=(0,0,1)$ and the guard is true. The first pass changes the state as follows; a value stays unchanged until a statement assigns to it.
| Executed statement | S | m | B |
|---|---|---|---|
S ← S + B |
1 | 0 | 1 |
m ← m + 1 |
1 | 1 | 1 |
B ← B + 2 |
1 | 1 | 3 |
- The relation $S=m^2$ fails temporarily after the first assignment, when $S=1$ and $m=0$. We will claim it at the loop head, after initialization or a complete pass, rather than after every individual statement.
Summarize completed passes
- The original table shows loop-head states, with the guard about to be tested. For $N=10$, the sums are 0, 1, 4, 9, 16; only the first four states enter another pass. At exit, $S=16$, $m=4$ and $B=9$.
- For the original threshold $N=30$, the loop reaches 25 after five additions, then adds 11 to reach 36. It exits with $S=36$, $m=6$ and $B=13$. Keep the next addend separate from the last addend used.
Use the stated pre-test odd-sum loop with $S=0$, $m=0$, $B=1$ and threshold $N=30$. What is $S$ at exit?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The loop-head sums are 0,1,4,9,16,25,36. Since 25<30≤36, it exits after six additions with S=36, m=6 and next addend B=13.
Establish and preserve the invariant
- At every loop head, the invariant is $S=m^2$ and $B=2m+1$, with $m\ge0$ an integer. Initialization gives $S=0=0^2$ and $B=1$. These facts do not depend on the threshold.
- Suppose the old count is $m$. One complete pass sets the sum to $m^2+(2m+1)=(m+1)^2$, the count to $m+1$, and the next addend to $2m+3$. Thus both relations hold again at the next head. This is preservation, not yet a termination proof.
Prove that the loop stops
- Let $q=\lceil\sqrt N\rceil$, used only for the proof. At a head with a true guard, $m^2<N$, so $m<q$. Every pass increases $m$ by exactly one, making the nonnegative integer $q-m$ decrease by one. After $q$ passes the guard is false.
- This proves termination and the exact pass count $q$, including zero passes for $N=0$. Merely saying a quantity increases is insufficient: an increasing sequence can remain below a threshold. Here the invariant gives the specific square growth.
Use the invariant at exit
- For $N>0$, the last true guard and first false guard give $(m-1)^2<N\le m^2$. Therefore $S$ is the least square at least N. If $S=N$, the input is a square; if $S>N$, it is not. For $N=0$, the initial state already gives the correct square 0.
- The exit test supplies $S\ge N$; the invariant supplies $S=m^2$. Neither fact alone proves the full claim. Replacing
<by≤would instead return the least square strictly greater than $N$, so the guard is part of the specification.
Which part of the odd-sum proof is this?
Separate initialization, preservation, termination and reasoning at exit.
A loop invariant shows what is true when a loop ends, but termination needs a separate argument.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An established and preserved invariant, combined with a false guard, proves the exit claim if the loop stops. A separate argument, such as the decreasing nonnegative integer ceil(sqrt(N))-m here, proves that it does stop.
Use the stated pre-test odd-sum loop with threshold $N=0$. What is $S$ at exit?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The initial guard 0<0 is false, so the body runs zero times and S stays zero.
For the stated pre-test odd-sum loop, give S, m and B at exit for N=50 and for N=49. Justify both the pass count and the square test.
Check the allocation conditions or the exact loop checkpoint before comparing your answer.
Changing update order changes the sequence
- If
B ← B + 2moves beforeS ← S + B, the first addend becomes 3. With the same initial values, the sums become 3, 8, 15, …, and after $m$ passes the new relation is $S=m(m+2)$. - That relation follows from summing $3+5+\cdots+(2m+1)$, but it is not the original invariant. Trace the actual assignments before applying a familiar formula; a valid proof for one loop does not prove a reordered loop correct.
Moving B ← B+2 before S ← S+B preserves the original loop-head invariant $S=m^2$ with the same initialization.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first complete pass then gives S=3, m=1, B=3. The original equation S=m² already fails; the new sum is m(m+2).
Reset every state used by a fresh run
- To process thresholds 2 and 5 independently, put all three initializations inside the outer loop, before each odd-sum loop. The runs return 4 and 9. Resetting only $S$ leaves the old next addend and count in place.
- With $m=0,B=1$ initialized only once, the first run ends at $(S,m,B)=(4,2,5)$. Reset only $S$ for threshold 5, and the next addition is 5: the second run returns 5, not 9. The original invariant no longer matches the reset state.
Reset S=0, m=0 and B=1 before each run of the stated odd-sum loop. Which outputs correspond to thresholds 2 and 5?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first squares at least 2 and 5 are 4 and 9. The output 5 on the second run would result from retaining B=5 after resetting only S.
Process thresholds 2, 5 and 10 in order. Compare outputs when all three state variables reset before each run with outputs when m=0 and B=1 are initialized once and only S resets between runs. Explain the difference.
Check the allocation conditions or the exact loop checkpoint before comparing your answer.
Recap: model and checkpoint
- Count the intended outcomes: check object identity, box labels, lower bounds and capacities. For a loop, specify initialization, guard and update order, then prove initialization, preservation, termination and the exit claim at a stated checkpoint.
- stars and bars: A bijective method for counting nonnegative integer allocations of identical objects among named boxes without upper capacities.
- complement: The outcomes in a specified full set that are not in the event being considered.
- invariant: A property that holds at a specified checkpoint before the loop and after every complete pass.