Composiciones débiles, invariantes de bucle y trazado de diagramas de flujo
Introducido| English | Significado |
|---|---|
| stars and bars/stɑːz ænd bɑːz/ | estrellas y barras |
| complement/ˈkɒmplɪmənt/ | complemento |
| invariant/ɪnˈveərɪənt/ | invariante |
Fichas idénticas, cajas con nombre
- Once fichas de recompensa idénticas se colocan en cuatro cajas nombradas, sin límites de capacidad y permitiendo cajas vacías. El registro del resultado contiene únicamente las cuatro cantidades. Esto no es $4^{11}$: eso distinguiría las fichas.
- Usaremos el método de estrellas y barras, complementos y conteos exactos de cajas vacías, luego trazaremos un algoritmo de suma de cuadrados. Los invariantes de bucle conectan los valores en la traza con una demostración sobre cada pasada.
Establezca primero el modelo de asignación
- Sea $n\ge0$ y $k\ge1$ enteros. Objetos idénticos en $k$ cajas nombradas corresponden a conteos de enteros no negativos $x_1+\cdots+x_k=n$. No hay orden dentro de una caja y, para la fórmula básica, no hay capacidad superior.
- Si los objetos son distintos, cambiar qué objeto entra en una caja puede alterar el resultado. Si las cajas no están nombradas o se imponen capacidades, el conteo básico también cambia. Decida qué hace que dos resultados sean diferentes antes de elegir una fórmula.
Por qué estrellas y barras es una biyección
- Coloque $n$ estrellas y $k-1$ barras en una fila. Leyendo de izquierda a derecha, las barras separan los conteos para las cajas 1 a $k$. Las barras finales y adyacentes están permitidas: registran cajas vacías.
- Para seis tokens en cuatro cajas,
***||**|*representa $(3,0,2,1)$. Recíprocamente, cada tupla de conteos permitida construye exactamente una fila así. Elegir las posiciones de las barras entre $n+k-1$ lugares cuenta las asignaciones sin duplicación.
Cuentas soluciones no negativas
- El número de composiciones débiles es $\binom{n+k-1}{k-1}$. Para el original $x_1+x_2+x_3=8$, elija dos posiciones de barra entre diez: $\binom{10}{2}=45$. Para once tokens en cuatro cajas, el conteo es $\binom{14}{3}=364$.
- Los casos límite importan. Sin tokens hay una asignación, todos los conteos cero. Con una caja hay una asignación, todos los tokens en ella. La fórmula coincide en ambos casos; no requiere que todas las cajas se usen.
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 8$ have?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
There is exactly one tuple: (0,0,0,0). The stars-and-bars count is C(3,3)=1.
Elimine los límites inferiores mediante sustitución
- Si cada $x_i\ge1$, establezca $z_i=x_i-1\ge0$. Cuando $n\ge k$, el total residual es $n-k$ y el conteo es $\binom{n-1}{k-1}$. Si $n<k$, no hay tales asignaciones. Los cuatro conteos positivos originales que suman 9 dan $\binom83=56$.
- En general, para límites inferiores enteros $x_i\ge\ell_i\ge0$, reste todos los límites inferiores primero. Para $x_1+x_2+x_3=8$ con límites 2, 1 y 0, el total residual es 5, dando $\binom72=21$. Un residual negativo significa que no hay soluciones.
How many positive integer solutions does $x_1+x_2+x_3+x_4=9$ have?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Subtract lower bounds 2,1,0, leaving three nonnegative counts totaling 5. The count is C(7,2)=21.
Use un complemento para al menos una caja vacía
- Dentro del conjunto completo de asignaciones, el complemento de "al menos una caja está vacía" es "todas las cajas son no vacías." Para once tokens y cuatro cajas nombradas, las asignaciones positivas tienen un total de $\binom{10}{3}=120$.
- Así, $364-120=244$ asignaciones dejan al menos una caja vacía. Reste el complemento una vez; restar cuatro eventos de caja vacía individualmente por separado confundiría las asignaciones con varias cajas vacías.
Exactamente r cajas vacías es un evento diferente
- Para $n>0$ y exactamente $r$ cajas vacías, primero elija esas cajas de $\binom kr$ formas. Ponga conteos positivos en las otras $k-r$ cajas. Si $1\le k-r\le n$, el conteo es $\binom kr\binom{n-1}{k-r-1}$; de lo contrario es cero.
- Con once tokens y cuatro cajas, exactamente dos vacíos da $\binom42\binom{10}{1}=60$. Los conteos para cero, uno, dos y tres vacíos son 120, 180, 60 y 4, sumando 364. Para $n=0$, todas las $k$ cajas están vacías en la única asignación.
Eleven identical tokens go into four named boxes. How many allocations have exactly two empty boxes?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Verifique las condiciones de asignación o el punto de control exacto del bucle antes de comparar su respuesta.
Los límites superiores requieren correcciones por superposición
- Cuente $x_1+x_2+x_3=8$ con $0\le x_i\le3$. Comience con 45 asignaciones sin restricciones. Para una violación especificada $x_i\ge4$, reste 4 a esa coordenada: hay $\binom62=15$ tales asignaciones.
- Restar $3\cdot15$ elimina las violaciones por pares dos veces. Para cada uno de los tres pares, dos conteos de al menos 4 dejan un residuo cero, lo que da una asignación para sumar de nuevo. No cabe ninguna violación triple, por lo tanto la respuesta es $45-45+3=3$: las tres permutaciones 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?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Verifique las condiciones de asignación o el punto de control exacto del bucle antes de comparar su respuesta.
Los objetos distintos usan elecciones independientes
- Para $n$ objetos distintos y $k$ destinatarios nombrados, sin capacidades ni orden dentro de la colección de un destinatario, cada objeto elige un destinatario. El conteo es $k^n$. Cinco libros diferentes dados a tres estudiantes tienen por tanto $3^5=243$ asignaciones.
- Esto cuenta qué libros recibe cada estudiante, no el orden de entrega. Si cada estudiante debe recibir un libro, excluyan los eventos de estudiantes vacíos y sumen de nuevo sus superposiciones por pares: $3^5-3\cdot2^5+3=150$. Las estrellas y barras positivas no aplicarían a estos libros distintos.
¿Qué modelo de conteo coincide con las condiciones establecidas?
Usa la identidad del objeto y las restricciones de asignación, no solo una fórmula familiar.
Five different books are given to 3 students (a student may get none). How many ways?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Each distinct book picks a student.
Especifiquen el bucle de suma impar
- Sea la entrada $N$ un entero no negativo. Usen aritmética entera exacta y un bucle pre-test: prueben la condición antes del primer paso y antes de cada paso posterior. Aquí $m$ cuenta las sumas completadas, y $B$ almacena el siguiente sumando impar.
S ← 0
m ← 0
B ← 1
WHILE S < N
S ← S + B
m ← m + 1
B ← B + 2
ENDWHILE
- Las asignaciones se ejecutan en el orden escrito. Cada lado derecho usa los valores disponibles cuando se ejecuta ese enunciado; son actualizaciones secuenciales, no una reemplazo simultáneo de las tres variables.
Rastreen un enunciado a la vez
- Para $N=10$, el estado inicial es $(S,m,B)=(0,0,1)$ y la condición es verdadera. El primer paso cambia el estado de la siguiente manera; un valor permanece sin cambios hasta que un enunciado le asigna un nuevo valor.
| Enunciado ejecutado | S | m | B |
|---|---|---|---|
S ← S + B |
1 | 0 | 1 |
m ← m + 1 |
1 | 1 | 1 |
B ← B + 2 |
1 | 1 | 3 |
- La relación $S=m^2$ falla temporalmente después de la primera asignación, cuando $S=1$ y $m=0$. Reivindicaremos esta relación en la cabeza del bucle, tras la inicialización o un paso completo, en lugar de después de cada enunciado individual.
Resuman las pasadas completadas
- La tabla original muestra estados del cabezal de bucle, con la condición a evaluar. Para $N=10$, las sumas son 0, 1, 4, 9, 16; solo los primeros cuatro estados entran en otra iteración. A la salida, $S=16$, $m=4$ y $B=9$.
- Para el umbral original $N=30$, el bucle alcanza 25 después de cinco sumas, luego suma 11 para llegar a 36. Sale con $S=36$, $m=6$ y $B=13$. Mantengan el próximo sumando separado del último sumando utilizado.
Use the stated pre-test odd-sum loop with $S=0$, $m=0$, $B=1$ and threshold $N=30$. What is $S$ at exit?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Establecer y preservar el invariante
- En cada cabeza de bucle, el invariante es $S=m^2$ y $B=2m+1$, con $m\ge0$ un entero. La inicialización proporciona $S=0=0^2$ y $B=1$. Estos hechos no dependen del umbral.
- Supongan que el conteo anterior es $m$. Una pasada completa establece la suma en $m^2+(2m+1)=(m+1)^2$, el conteo en $m+1$, y el próximo sumando en $2m+3$. Así ambas relaciones vuelven a cumplirse en la siguiente cabeza. Esto es preservación, pero aún no una prueba de terminación.
Demostrar que el bucle se detiene
- Sea $q=\lceil\sqrt N\rceil$, utilizado únicamente para la demostración. En una cabeza de bucle con una condición verdadera, $m^2<N$, por lo tanto $m<q$. Cada paso aumenta $m$ exactamente en uno, haciendo que el entero no negativo $q-m$ disminuya en uno. Después de $q$ pasos, la condición es falsa.
- Esto demuestra la terminación y el conteo exacto de pasos $q$, incluyendo cero pasos para $N=0$. Simplemente decir que una cantidad aumenta es insuficiente: una secuencia creciente puede permanecer por debajo de un umbral. Aquí, el invariante proporciona el crecimiento cuadrático específico.
Usar el invariante en la salida
- Para $N>0$, la última condición verdadera y la primera condición falsa dan $(m-1)^2<N\le m^2$. Por lo tanto, $S$ es el cuadrado menor mayor o igual a N. Si $S=N$, la entrada es un cuadrado; si $S>N$, no lo es. Para $N=0$, el estado inicial ya proporciona el cuadrado correcto 0.
- La prueba de salida proporciona $S\ge N$; el invariante proporciona $S=m^2$. Ninguno de estos hechos por sí solo demuestra la afirmación completa. Reemplazar
<por≤devolvería en cambio el cuadrado menor estrictamente mayor que $N$, por lo que la condición forma parte de la especificación.
¿A qué parte de la prueba de suma impar corresponde esto?
Separar inicialización, preservación, terminación y razonamiento a la salida.
A loop invariant shows what is true when a loop ends, but termination needs a separate argument.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Verifique las condiciones de asignación o el punto de control exacto del bucle antes de comparar su respuesta.
Cambiar el orden de actualización cambia la secuencia
- Si
B ← B + 2se mueve antes deS ← S + B, el primer sumando se convierte en 3. Con los mismos valores iniciales, las sumas se convierten en 3, 8, 15, …, y después de $m$ pasos, la nueva relación es $S=m(m+2)$. - Esa relación se sigue de sumar $3+5+\cdots+(2m+1)$, pero no es el invariante original. Rastrear las asignaciones reales antes de aplicar una fórmula familiar; una demostración válida para un bucle no demuestra correcta a un bucle reordenado.
Moving B ← B+2 before S ← S+B preserves the original loop-head invariant $S=m^2$ with the same initialization.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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).
Restablecer cada estado usado por una ejecución fresca
- Para procesar umbrales 2 y 5 de forma independiente, colocar los tres inicializadores dentro del bucle exterior, antes de cada bucle de suma impar. Las ejecuciones devuelven 4 y 9. Restablecer solo $S$ deja el siguiente sumando y el contador antiguos en su lugar.
- Con $m=0,B=1$ inicializado solo una vez, la primera ejecución termina en $(S,m,B)=(4,2,5)$. Restablecer solo $S$ para el umbral 5, y la próxima adición es 5: la segunda ejecución devuelve 5, no 9. El invariante original ya no coincide con el estado restablecido.
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?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Verifique las condiciones de asignación o el punto de control exacto del bucle antes de comparar su respuesta.
Resumen: modelo y punto de control
- Contar los resultados deseados: verificar la identidad del objeto, las etiquetas de las cajas, los límites inferiores y las capacidades. Para un bucle, especificar inicialización, condición y orden de actualización, luego demostrar inicialización, preservación, terminación y la afirmación de salida en un punto de control declarado.
- estrellas y barras: Un método biyectivo para contar distribuciones enteras no negativas de objetos idénticos entre cajas nombradas sin capacidades superiores.
- complemento: Los resultados en un conjunto completo especificado que no pertenecen al evento considerado.
- invariante: Una propiedad que se cumple en un punto de control especificado antes del bucle y después de cada paso completo.