Compositions faibles, invariants de boucle et traçage de diagrammes de flux
Introduit| English | Sens |
|---|---|
| stars and bars/stɑːz ænd bɑːz/ | étoiles et barres |
| complement/ˈkɒmplɪmənt/ | complémentaire |
| invariant/ɪnˈveərɪənt/ | invariant |
Jetons identiques, boîtes nommées
- Onze jetons identiques sont placés dans quatre boîtes nommées, sans limites de capacité et avec des boîtes vides autorisées. Le résultat ne conserve que les quatre comptes. Ce n'est pas $4^{11}$ : cela distinguerait les jetons.
- Nous utiliserons étoiles et barres, compléments et comptes exacts de boîtes vides, puis tracerons un algorithme de somme de carrés. Les invariants de boucle relient les valeurs d'un tracé à une preuve sur chaque passe.
Énoncer d'abord le modèle d'allocation
- Soient $n\ge0$ et $k\ge1$ des entiers. Des objets identiques dans $k$ boîtes nommées correspondent à des comptes entiers positifs ou nuls $x_1+\cdots+x_k=n$. Il n'y a pas d'ordre à l'intérieur d'une boîte et, pour la formule de base, aucune capacité supérieure.
- Si les objets sont distincts, changer quel objet entre dans une boîte peut modifier le résultat. Si les boîtes ne sont pas nommées ou si des capacités sont imposées, le décompte de base change également. Décidez ce qui rend deux résultats différents avant de choisir une formule.
Pourquoi étoiles et barres est une bijection
- Placez $n$ étoiles et $k-1$ barres dans une ligne. En lisant de gauche à droite, les barres séparent les comptes pour les boîtes 1 à $k$. Les barres extrêmes et adjacentes sont autorisées : elles signalent les boîtes vides.
- Pour six jetons dans quatre boîtes,
***||**|*représente $(3,0,2,1)$. Réciproquement, chaque tuple de comptes autorisé construit exactement une telle ligne. Choisir les positions des barres parmi $n+k-1$ emplacements permet donc de compter les allocations sans doublon.
Compter les solutions positives ou nulles
- Le nombre de compositions faibles est $\binom{n+k-1}{k-1}$. Pour le $x_1+x_2+x_3=8$ original, choisir deux positions de barre parmi dix : $\binom{10}{2}=45$. Pour onze jetons dans quatre boîtes, le décompte est $\binom{14}{3}=364$.
- Les cas aux bornes comptent. Sans jeton, il y a une seule allocation, tous les comptes étant zéro. Avec une seule boîte, il y a une seule allocation, tous les jetons dedans. La formule correspond dans les deux cas ; elle ne nécessite pas que chaque boîte soit utilisée.
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 8$ have?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
There is exactly one tuple: (0,0,0,0). The stars-and-bars count is C(3,3)=1.
Supprimer les bornes inférieures par substitution
- Si chaque $x_i\ge1$, poser $z_i=x_i-1\ge0$. Lorsque $n\ge k$, le total résiduel est $n-k$ et le décompte est $\binom{n-1}{k-1}$. Si $n<k$, il n'y a pas d'allocations de ce type. Les quatre comptes positifs originaux s'additionnant à 9 donnent $\binom83=56$.
- Plus généralement, pour des bornes inférieures entières $x_i\ge\ell_i\ge0$, soustraire d'abord toutes ces bornes. Pour $x_1+x_2+x_3=8$ avec des bornes 2, 1 et 0, le total résiduel est 5, donnant $\binom72=21$. Un résidu négatif signifie qu'il n'y a pas de solutions.
How many positive integer solutions does $x_1+x_2+x_3+x_4=9$ have?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Subtract lower bounds 2,1,0, leaving three nonnegative counts totaling 5. The count is C(7,2)=21.
Utiliser un complément pour au moins une boîte vide
- Dans l'ensemble complet des distributions, le complémentaire de « au moins une boîte est vide » est « chaque boîte est non vide ». Pour onze jetons et quatre boîtes nommées, le nombre de distributions strictement positives est $\binom{10}{3}=120$.
- Ainsi, $364-120=244$ distributions laissent au moins une boîte vide. On soustrait le complémentaire une fois ; soustraire séparément les quatre événements d'une seule boîte vide entraînerait une double décompte pour les distributions comportant plusieurs boîtes vides.
L'événement « exactement r boîtes vides » est distinct
- Pour $n>0$ et exactement $r$ boîtes vides, choisir d'abord ces boîtes en $\binom kr$ manières. Placer des comptes positifs dans les $k-r$ autres boîtes. Si $1\le k-r\le n$, le compte est $\binom kr\binom{n-1}{k-r-1}$ ; sinon il est zéro.
- Avec onze jetons et quatre boîtes, exactement deux vides donne $\binom42\binom{10}{1}=60$. Les comptes pour zéro, une, deux et trois vides sont 120, 180, 60 et 4, totalisant 364. Pour $n=0$, toutes les $k$ boîtes sont vides dans la unique distribution.
Eleven identical tokens go into four named boxes. How many allocations have exactly two empty boxes?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Vérifiez les conditions d'allocation ou le point de contrôle exact de la boucle avant de comparer votre réponse.
Les bornes supérieures nécessitent des corrections de chevauchement
- Compter $x_1+x_2+x_3=8$ avec $0\le x_i\le3$. Commencer par 45 distributions sans restriction. Pour une violation spécifiée $x_i\ge4$, soustraire 4 à cette coordonnée : il y a $\binom62=15$ telles distributions.
- La soustraction de $3\cdot15$ retire les violations paires deux fois. Pour chacun des trois paires, deux comptes d'au moins 4 laissent un résidu nul, donnant une distribution à réintégrer. Aucune triple violation n'est possible, donc la réponse est $45-45+3=3$ : les trois permutations de $(3,3,2)$.
How many integer solutions of $x_1+x_2+x_3=8$ satisfy $0\le x_i\le3$ for every i?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Vérifiez les conditions d'allocation ou le point de contrôle exact de la boucle avant de comparer votre réponse.
Les objets distincts utilisent des choix indépendants
- Pour $n$ objets distincts et $k$ destinataires nommés, sans capacités et sans ordre à l'intérieur de la collection d'un destinataire, chaque objet choisit un destinataire. Le dénombrement est $k^n$. Cinq livres différents distribués à trois élèves ont donc $3^5=243$ allocations.
- Cela compte quels livres chaque élève reçoit, pas l'ordre de remise. Si chaque élève doit recevoir un livre, exclure les événements d'élèves vides et réintégrer leurs chevauchements paires : $3^5-3\cdot2^5+3=150$. Les étoiles et barres positives ne s'appliquent pas à ces livres distincts.
Quel modèle de comptage correspond aux conditions énoncées ?
Utiliser l'identité des objets et les contraintes d'allocation, pas seulement une formule familière.
Five different books are given to 3 students (a student may get none). How many ways?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Each distinct book picks a student.
Spécifier la boucle à somme impaire
- Soit l'entrée $N$ un entier non négatif. Utiliser une arithmétique entière exacte et une boucle pré-test : tester la condition avant la première itération et avant chaque itération suivante. Ici $m$ compte les additions complétées, et $B$ stocke le prochain additeur impair.
S ← 0
m ← 0
B ← 1
WHILE S < N
S ← S + B
m ← m + 1
B ← B + 2
ENDWHILE
- Les affectations s'exécutent dans l'ordre écrit. Chaque côté droit utilise les valeurs disponibles au moment où cette instruction s'exécute ; ce sont des mises à jour séquentielles, pas un remplacement simultané des trois variables.
Suivre une instruction à la fois
- Pour $N=10$, l'état initial est $(S,m,B)=(0,0,1)$ et la condition est vraie. La première itération modifie l'état comme suit ; une valeur reste inchangée jusqu'à ce qu'une instruction lui attribue une nouvelle valeur.
| Instruction exécutée | S | m | B |
|---|---|---|---|
S ← S + B |
1 | 0 | 1 |
m ← m + 1 |
1 | 1 | 1 |
B ← B + 2 |
1 | 1 | 3 |
- La relation $S=m^2$ est temporairement fausse après la première affectation, lorsque $S=1$ et $m=0$. Nous affirmerons sa validité à la tête de boucle, après l'initialisation ou une itération complète, plutôt qu'après chaque instruction individuelle.
Résumer les itérations complétées
- Le tableau original montre les états à la tête de boucle, avec la condition sur le point d'être testée. Pour $N=10$, les sommes sont 0, 1, 4, 9, 16 ; seuls les quatre premiers états entrent dans une autre itération. À la sortie, $S=16$, $m=4$ et $B=9$.
- Pour le seuil initial $N=30$, la boucle atteint 25 après cinq additions, puis ajoute 11 pour atteindre 36. Elle se termine avec $S=36$, $m=6$ et $B=13$. Gardez le prochain additif séparé du dernier additif utilisé.
Use the stated pre-test odd-sum loop with $S=0$, $m=0$, $B=1$ and threshold $N=30$. What is $S$ at exit?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Établir et préserver l'invariant
- À chaque tête de boucle, l'invariant est $S=m^2$ et $B=2m+1$, avec $m\ge0$ un entier. L'initialisation donne $S=0=0^2$ et $B=1$. Ces faits ne dépendent pas du seuil.
- Supposons que le compteur actuel soit $m$. Un passage complet définit la somme à $m^2+(2m+1)=(m+1)^2$, le compteur à $m+1$, et le prochain additif à $2m+3$. Ainsi, les deux relations sont vérifiées à nouveau à l'en-tête suivant. Il s'agit d'une préservation, mais pas encore d'une preuve d'arrêt.
Prouver que la boucle s'arrête
- Soit $q=\lceil\sqrt N\rceil$, utilisé uniquement pour la preuve. Sur un en-tête avec une condition vraie, $m^2<N$, donc $m<q$. Chaque passage augmente $m$ d'exactement une unité, ce qui fait diminuer de une l'entier non négatif $q-m$. Après $q$ passages, la condition devient fausse.
- Cela prouve l'arrêt et le nombre exact de passages $q$, y compris zéro passage pour $N=0$. Dire simplement qu'une quantité augmente est insuffisant : une séquence croissante peut rester en dessous d'un seuil. Ici, l'invariant fournit la croissance carrée spécifique.
Utiliser l'invariant à la sortie
- Pour $N>0$, le dernier test de condition vrai et le premier faux donnent $(m-1)^2<N\le m^2$. Par conséquent, $S$ est le plus petit carré supérieur ou égal à N. Si $S=N$, l'entrée est un carré ; si $S>N$, ce n'est pas le cas. Pour $N=0$, l'état initial donne déjà le bon carré 0.
- Le test de sortie fournit $S\ge N$ ; l'invariant fournit $S=m^2$. Aucun de ces faits seul ne prouve l'affirmation complète. Remplacer
<par≤retournerait plutôt le plus petit carré strictement supérieur à $N$, donc la condition fait partie de la spécification.
Laquelle des étapes de la preuve par somme impaire correspond à ceci ?
Séparer l'initialisation, la préservation, la terminaison et le raisonnement à la sortie.
A loop invariant shows what is true when a loop ends, but termination needs a separate argument.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Vérifiez les conditions d'allocation ou le point de contrôle exact de la boucle avant de comparer votre réponse.
Changer l'ordre des mises à jour modifie la séquence
- Si
B ← B + 2est déplacé avantS ← S + B, le premier additif devient 3. Avec les mêmes valeurs initiales, les sommes deviennent 3, 8, 15, …, et après $m$ passages, la nouvelle relation est $S=m(m+2)$. - Cette relation découle de l'addition de $3+5+\cdots+(2m+1)$, mais elle n'est pas l'invariant original. Suivez les affectations réelles avant d'appliquer une formule familière ; une preuve valide pour une boucle ne prouve pas la correction d'une boucle dont l'ordre a été réordonné.
Moving B ← B+2 before S ← S+B preserves the original loop-head invariant $S=m^2$ with the same initialization.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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).
Réinitialiser tous les états utilisés par une exécution fraîche
- Pour traiter les seuils 2 et 5 indépendamment, placez les trois initialisations dans la boucle extérieure, avant chaque boucle de somme impaire. Les exécutions retournent 4 et 9. Ne réinitialiser que $S$ laisse l'ancien prochain additif et le compteur en place.
- Avec $m=0,B=1$ initialisé une seule fois, la première exécution se termine à $(S,m,B)=(4,2,5)$. Ne réinitialiser que $S$ pour le seuil 5, et la prochaine addition est 5 : la deuxième exécution retourne 5, et non 9. L'invariant original ne correspond plus à l'état réinitialisé.
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Vérifiez les conditions d'allocation ou le point de contrôle exact de la boucle avant de comparer votre réponse.
Résumé : modèle et point de contrôle
- Comptez les résultats attendus : vérifiez l'identité des objets, les étiquettes des boîtes, les bornes inférieures et les capacités. Pour une boucle, spécifiez l'initialisation, la condition et l'ordre des mises à jour, puis prouvez l'initialisation, la préservation, l'arrêt et l'affirmation de sortie à un point de contrôle énoncé.
- étoiles et barres : Méthode bijective pour dénombrer les allocations d'objets identiques dans des boîtes nommées sans capacités maximales.
- complément : Les issues d'un ensemble complet spécifié qui ne figurent pas dans l'événement considéré.
- invariant : Propriété valide à un point de contrôle spécifique avant la boucle et après chaque passage complet.