1.4: Pruebas combinatorias

Template:MathJaxLevin

¡Investiga!

1. La Copa Stanley se decide en un torneo al mejor de 7 entre dos equipos. ¿De cuántas maneras puede ganar tu equipo? Respondamos a esta pregunta de dos maneras:
   1. ¿Cuántos de los 7 juegos necesita tu equipo para ganar? ¿De cuántas maneras puede suceder esto?
   2. ¿Y si el torneo va a los 7 juegos? Entonces ganas el último juego. ¿De cuántas formas pueden bajar los primeros 6 juegos?
   3. ¿Y si el torneo va solo 6 juegos? ¿De cuántas maneras puede suceder esto? ¿Qué pasa con 5 juegos? ¿4 juegos?
   4. ¿Cuáles son las dos formas diferentes de calcular la cantidad de formas en que tu equipo puede ganar? Anote una ecuación que involucre coeficientes binomiales (es decir,\({n \choose k}\)'s). ¿De qué patrón en el triángulo de Pascal es este un ejemplo?
2. Generalizar. ¿Y si cambiaban las reglas y jugaste lo mejor del\(9\) torneo (se requieren 5 victorias)? ¿Y si jugaste un torneo de\(n\) juego con\(k\) victorias requeridas para ser nombrado campeón?

Patrones en el Triángulo de Pascal

Vuelva a echar un vistazo al triángulo de Pascal. Olvídate por un momento de dónde viene. Basta con mirarlo como un objeto matemático. ¿Qué notas?

Hay muchos patrones escondidos en el triángulo, suficientes para llenar un libro de tamaño razonable. Estos son solo algunos de los más obvios:

1. Las entradas en el borde del triángulo son todas 1.
2. Cualquier entrada que no esté en la frontera es la suma de las dos entradas por encima de ella.
3. El triángulo es simétrico. En cualquier fila, las entradas del lado izquierdo están reflejadas en el lado derecho.
4. La suma de todas las entradas en una fila dada es una potencia de 2. (¡Deberías verificar esto!)

Nos gustaría exponer estas observaciones de una manera más precisa, para luego demostrar que son correctas. Ahora cada entrada en el triángulo de Pascal es de hecho un coeficiente binomial. El 1 en la parte superior del triángulo es\({0 \choose 0}\). La siguiente fila (a la que llamaremos fila 1, aunque no sea la fila más alta) consiste en\({1 \choose 0}\) y\({1 \choose 1}\). La fila 4 (la fila 1, 4, 6, 4, 1) consiste en los coeficientes binomiales

\ begin {ecuación*} {4\ elige 0} ~~ {4\ elige 1} ~~ {4\ elige 2} ~~ {4\ elige 3} ~~ {4\ elige 4}. \ end {ecuación*}

Dada esta descripción de los elementos en el triángulo de Pascal, podemos reescribir las observaciones anteriores de la siguiente manera:

1. \({n \choose 0} = 1\)y\({n \choose n} = 1\).
2. \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\).
3. \({n \choose k} = {n \choose n-k}\).
4. \({n\choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n\).

Cada uno de estos es un ejemplo de una identidad binomial: una identidad (es decir, ecuación) que involucra coeficientes binomiales.

Nuestro objetivo es establecer estas identidades. Deseamos demostrar que tienen para todos los valores de\(n\) y\(k\). Estas pruebas se pueden hacer de muchas maneras. Una opción sería dar pruebas algebraicas, usando la fórmula para\({n \choose k}\text{:}\)

\ comenzar {ecuación*} {n\ elige k} =\ frac {n!} {(n-k)! \, k!}. \ end {ecuación*}

Así es como podrías hacer eso para la segunda identidad anterior.

Ejemplo\(\PageIndex{1}\)

Dar una prueba algebraica para la identidad binomial

\ begin {ecuación*} {n\ elige k} = {n-1\ elige k-1} + {n-1\ elige k}. \ end {ecuación*}

Solución

Prueba

Por la definición de\({n \choose k}\), we have

\ begin {ecuación*} {n-1\ elige k-1} =\ frac {(n-1)!} {(n-1- (k-1))! (k-1)!} =\ frac {(n-1)!} {(n-k)! (k-1)!} \ end {ecuación*}

y

\ begin {ecuación*} {n-1\ elige k} =\ frac {(n-1)!} {(n-1-k)! k!}. \ end {ecuación*}

Así, comenzando por el lado derecho de la ecuación:

\ begin {alinear*} {n-1\ elige k-1} + {n-1\ elige k}\ amp =\ frac {(n-1)!} {(n-k)! (k-1)!} +\ frac {(n-1)!} {(n-1-k)! \, k!} \\\ amp =\ frac {(n-1)! k} {(n-k)! \, k!} +\ frac {(n-1)! (n-k)} {(n-k)! \, k!} \\\ amp =\ frac {(n-1)! (k+n-k)} {(n-k)! \, k!} \\ amp =\ frac {n!} {(n-k)! \, k!} \\\ amp = {n\ elige k}. \ end {align*}

La segunda línea (donde se encuentra el denominador común) funciona porque\(k(k-1)! = k!\) and \((n-k)(n-k-1)! = (n-k)!\).

\(\square\)

Esto es sin duda una prueba válida, pero también es del todo inútil. Aunque entiendas perfectamente la prueba, no te dice por qué la identidad es cierta. Un mejor enfoque sería explicar qué\({n \choose k}\) significa y luego decir por qué eso es también lo que\({n-1 \choose k-1} + {n-1 \choose k}\) significa. Veamos cómo funciona esto para las cuatro identidades que observamos anteriormente.

Ejemplo\(\PageIndex{2}\)

Explique por qué\({n \choose 0} = 1\) y\({n \choose n} = 1\).

Solución

¿Qué nos dicen estos coeficientes binomiales? Bueno,\({n \choose 0}\) gives the number of ways to select 0 objects from a collection of \(n\) objects. There is only one way to do this, namely to not select any of the objects. Thus \({n \choose 0} = 1\). Similarly, \({n \choose n}\) gives the number of ways to select \(n\) objects from a collection of \(n\) objects. There is only one way to do this: select all \(n\) objects. Thus \({n \choose n} = 1\).

Alternativamente, sabemos que\({n \choose 0}\) is the number of \(n\)-bit strings with weight 0. There is only one such string, the string of all 0's. So \({n \choose 0} = 1\). Similarly \({n \choose n}\) is the number of \(n\)-bit strings with weight \(n\). There is only one string with this property, the string of all 1's.

Otra manera:\({n \choose 0}\) gives the number of subsets of a set of size \(n\) containing 0 elements. There is only one such subset, the empty set. \({n \choose n}\) gives the number of subsets containing \(n\) elements. The only such subset is the original set (of all elements).

Ejemplo\(\PageIndex{3}\)

Explique por qué\({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\).

Solución

La forma más fácil de ver esto es considerar cadenas de bits. \({n \choose k}\) is the number of bit strings of length \(n\) containing \(k\) 1's. Of all of these strings, some start with a 1 and the rest start with a 0. First consider all the bit strings which start with a 1. After the 1, there must be \(n-1\) more bits (to get the total length up to \(n\)) and exactly \(k-1\) of them must be 1's (as we already have one, and we need \(k\) total). How many strings are there like that? There are exactly \({n-1 \choose k-1}\) such bit strings, so of all the length \(n\) bit strings containing \(k\) 1's, \({n-1 \choose k-1}\) of them start with a 1. Similarly, there are \({n-1\choose k}\) which start with a 0 (we still need \(n-1\) bits and now \(k\) of them must be 1's). Since there are \({n-1 \choose k}\) bit strings containing \(n-1\) bits with \(k\) 1's, that is the number of length \(n\) bit strings with \(k\) 1's which start with a 0. Therefore \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\).

Otra forma: considera la pregunta, cuántas formas puedes seleccionar\(k\) pizza toppings from a menu containing \(n\) choices? One way to do this is just \({n \choose k}\). Another way to answer the same question is to first decide whether or not you want anchovies. If you do want anchovies, you still need to pick \(k-1\) toppings, now from just \(n-1\) choices. That can be done in \({n-1 \choose k-1}\) ways. If you do not want anchovies, then you still need to select \(k\) toppings from \(n-1\) choices (the anchovies are out). You can do that in \({n-1 \choose k}\) ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are \({n-1 \choose k-1}+{n-1 \choose k}\). But wait. We answered the same question in two different ways, so the two answers must be the same. Thus \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\).

También puedes explicar (probar) esta identidad contando subconjuntos, o incluso caminos de celosía.

Ejemplo\(\PageIndex{4}\)

Demostrar la identidad binomial\[{n \choose k} = {n \choose n-k}. \nonumber\]

Solución

¿Por qué es esto cierto? \({n \choose k}\) counts the number of ways to select \(k\) things from \(n\) choices. On the other hand, \({n \choose n-k}\) counts the number of ways to select \(n-k\) things from \(n\) choices. Are these really the same? Well, what if instead of selecting the \(n-k\) things you choose to exclude them. How many ways are there to choose \(n-k\) things to exclude from \(n\) choices. Clearly this is \({n \choose n-k}\) as well (it doesn't matter whether you include or exclude the things once you have chosen them). And if you exclude \(n-k\) things, then you are including the other \(k\) things. So the set of outcomes should be the same.

Probemos el ejemplo de conteo de pizza como lo hicimos anteriormente. ¿Cuántas formas hay de elegir\(k\) toppings from a list of \(n\) choices? On the one hand, the answer is simply \({n \choose k}\). Alternatively, you could make a list of all the toppings you don't want. To end up with a pizza containing exactly \(k\) toppings, you need to pick \(n-k\) toppings to not put on the pizza. You have \({n \choose n-k}\) choices for the toppings you don't want. Both of these ways give you a pizza with \(k\) toppings, in fact all the ways to get a pizza with \(k\) toppings. Thus these two answers must be the same: \({n \choose k} = {n \choose n-k}\).

También puede probar (explicar) esta identidad usando cadenas de bits, subconjuntos o rutas de celosía. El argumento de cadena de bits es agradable:\({n \choose k}\) counts the number of bit strings of length \(n\) with \(k\) 1's. This is also the number of bit string of length \(n\) with \(k\) 0's (just replace each 1 with a 0 and each 0 with a 1). But if a string of length \(n\) has \(k\) 0's, it must have \(n-k\) 1's. And there are exactly \({n\choose n-k}\) strings of length \(n\) with \(n-k\) 1's.

Ejemplo\(\PageIndex{5}\)

Demostrar la identidad binomial\[{n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n. \nonumber\]

Solución

Prueba

Volvamos a hacer una “prueba de pizza”. Necesitamos encontrar una pregunta sobre los ingredientes de pizza que tiene\(2^n\) as the answer. How about this: If a pizza joint offers \(n\) toppings, how many pizzas can you build using any number of toppings from no toppings to all toppings, using each topping at most once?

Por un lado, la respuesta es\(2^n\). For each topping you can say “yes” or “no,” so you have two choices for each topping.

Por otro lado, dividir las posibles pizzas en grupos disjuntos: las pizzas sin coberturas, las pizzas con un topping, las pizzas con dos coberturas, etc. Si no queremos coberturas, sólo hay una pizza así (la pizza vacía, si se quiere) pero sería mejor pensar en ese número como \({n \choose 0}\) since we choose 0 of the \(n\) toppings. How many pizzas have 1 topping? We need to choose 1 of the \(n\) toppings, so \({n \choose 1}\). We have:

Pizzas con 0 coberturas:\({n \choose 0}\) Pizzas con 1 topping:\({n \choose 1}\) Pizzas con 2 coberturas:\({n \choose 2}\)

El número total de pizzas posibles será la suma de éstas, que es exactamente el lado izquierdo de la identidad que estamos tratando de demostrar.

Nuevamente, podríamos haber probado la identidad usando subconjuntos, cadenas de bits o rutas de celosía (aunque el argumento de ruta de celosía es un poco complicado).

• \(\vdots\)
• Pizzas con\(n\) toppings: \({n \choose n}\).

\(\square\)

Ojalá esto dé alguna idea de cómo pueden ir las pruebas explicativas de las identidades binomiales. Cabe señalar que las pruebas más tradicionales también pueden ser hermosas. ³ La mayoría de cada identidad binomial se puede probar usando inductio matemática n, usando la definición recursiva para\(n \choose k\). W e discutirá la indu ción en la Sección 2.5. Por ejemplo, considere la siguiente prueba bastante hálida de la última identidad.

Ampliar el binomio\((x+y)^n\text{:}\)

\ begin {ecuación*} (x + y) ^n = {n\ elige 0} x^n + {n\ elige 1} x^ {n-1} y + {n\ elige 2} x^ {n-2} y^2 +\ cdots + {n\ elige n-1} x\ cdot y^n + {n\ elige n} y^n.\ final {ecuación*}

Dejar\(x = 1\) y\(y = 1\). Obtenemos:

\ begin {ecuación*} (1 + 1) ^n = {n\ elige 0} 1^n + {n\ elige 1} 1^ {n-1} 1 + {n\ elige 2} 1^ {n-2} 1^2 +\ cdots + {n\ elige n-1} 1\ cdot 1^n + {n\ elige n} 1^n.\ end {ecuación*}

Por supuesto, esto simplifica para:

\ begin {ecuación*} (2) ^n = {n\ elige 0} + {n\ elige 1} + {n\ elige 2} +\ cdots + {n\ elige n-1} + {n\ elige n}. \ end {ecuación*}

Algo divertido para probar: Vamos\(x = 1\) y\(y = 2\). Bien, ¿eh?

Más pruebas

Las pruebas explicativas dadas en los ejemplos anteriores se denominan típicamente pruebas combinatorias. En general, para dar una prueba combinatoria de una identidad binomial, digamos\(A = B\) que haces lo siguiente:

1. Encuentra un problema de conteo que podrás responder de dos maneras.
2. Explique por qué una respuesta al problema del conteo es\(A\).
3. Explique por qué la otra respuesta al problema del conteo es\(B\).

Ya que ambos\(A\) y\(B\) son las respuestas a una misma pregunta, debemos tener\(A = B\).

Lo complicado es que se le ocurra la pregunta. Esto no siempre es obvio, pero se vuelve más fácil cuantos más problemas de conteo resuelvas. Comenzarás a reconocer tipos de respuestas como las respuestas a tipos de preguntas. Más a menudo lo que va a pasar es que vas a estar resolviendo un problema de conteo y pasa a pensar en dos formas diferentes de encontrar la respuesta. Ahora tienes una identidad binomial y la prueba está ahí mismo. La prueba es el problema que acabas de resolver junto con tus dos soluciones.

Por ejemplo, considere esta pregunta de conteo:

¿Cuántas palabras de 10 letras usan exactamente cuatro A, tres B, dos C y una D?

Tratemos de resolver este problema. Tenemos 10 spots para que las letras vayan. Cuatro de esos necesitan ser A's. Podemos elegir los cuatro puntos A de\({10 \choose 4}\) maneras. Ahora, ¿dónde podemos poner las B's? Pues solo quedan 6 spots, tenemos que escoger\(3\) de ellos. Esto se puede hacer de\({6 \choose 3}\) maneras. Las dos C necesitan ir en dos de los 3 spots restantes, así que tenemos\({3 \choose 2}\) formas de hacerlo. Eso deja solo una mancha de la D, pero podríamos escribir esa 1 elección como\({1 \choose 1}\). Así la respuesta es:

\ begin {equation*} {10\ choose 4} {6\ choose 3} {3\ choose 2} {1\ choose 1}. \ end {ecuación*}

Pero, ¿por qué parar ahí? Podemos encontrar la respuesta de otra manera también. Primero decidamos dónde poner el D: tenemos 10 spots, tenemos que elegir 1 de ellos, para que esto se pueda hacer de\({10 \choose 1}\) maneras. A continuación, elige una de las\({9 \choose 2}\) formas de colocar las dos C's. Ahora nos quedan\(7\) manchas, y tres de ellas necesitan ser llenadas con B's. Hay\({7 \choose 3}\) formas de hacer esto. Por último, las A se pueden colocar en\({4 \choose 4}\) (es decir, solo una) formas. Entonces otra respuesta a la pregunta es

\ begin {equation*} {10\ choose 1} {9\ choose 2} {7\ choose 3} {4\ choose 4}. \ end {ecuación*}

Interesante. Esto nos da la identidad binomial:

\ begin {equation*} {10\ choose 4} {6\ choose 3} {3\ choose 2} {1\ choose 1} = {10\ choose 1} {9\ choose 2} {7\ choose 3} {4\ choose 4}. \ end {ecuación*}

Aquí hay un par de otras identidades binomiales con pruebas combinatorias.

Ejemplo\(\PageIndex{6}\)

Demostrar la identidad

\ begin {ecuación*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1 = {n+2\ elige 3}. \ end {ecuación*}

Solución

Para dar una prueba combinatoria necesitamos pensar una pregunta que podamos responder de dos maneras: una forma necesita dar el lado izquierdo de la identidad, la otra debe ser el lado derecho de la identidad. Nuestra pista sobre qué pregunta hacer viene del lado derecho:\({n+2 \choose 3}\) counts the number of ways to select 3 things from a group of \(n+2\) things. Let's name those things \(1, 2, 3, \ldots, n+2\). In other words, we want to find 3-element subsets of those numbers (since order should not matter, subsets are exactly the right thing to think about). We will have to be a bit clever to explain why the left-hand-side also gives the number of these subsets. Here's the proof.

Prueba

Considera la pregunta “¿Cuántos subconjuntos de 3 elementos hay del conjunto?\(\{1,2,3,\ldots, n+2\}\text{?}\)” We answer this in two ways:

Respuesta 1: Debemos seleccionar 3 elementos de la colección de\(n+2\) elements. This can be done in \({n+2 \choose 3}\) ways.

Respuesta 2: Dividir este problema en casos por lo que es el número medio en el subconjunto. Digamos que cada subconjunto es\(\{a,b,c\}\) written in increasing order. We count the number of subsets for each distinct value of \(b\). The smallest possible value of \(b\) is \(2\), and the largest is \(n+1\).

Cuando\(b = 2\), there are \(1 \cdot n\) subsets: 1 choice for \(a\) and \(n\) choices (3 through \(n+2\)) for \(c\).

Cuando\(b = 3\), there are \(2 \cdot (n-1)\) subsets: 2 choices for \(a\) and \(n-1\) choices for \(c\).

Cuando\(b = 4\), there are \(3 \cdot (n-2)\) subsets: 3 choices for \(a\) and \(n-2\) choices for \(c\).

Y así sucesivamente. Cuando\(b = n+1\), there are \(n\) choices for \(a\) and only 1 choice for \(c\), so \(n \cdot 1\) subsets.

Por lo tanto, el número total de subconjuntos es

\ comenzar {ecuación*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1. \ end {ecuación*}

Ya que la Respuesta 1 y la Respuesta 2 son respuestas a la misma pregunta, deben ser iguales. Por lo tanto

\ begin {ecuación*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1 = {n+2\ elige 3}. \ end {ecuación*}

\(\square\)

Ejemplo\(\PageIndex{7}\)

Demostrar la identidad binomial

\ begin {ecuación*} {n\ elige 0} ^2 + {n\ elige 1} ^2 + {n\ elige 2} ^2 +\ cdots + {n\ elige n} ^2 = {2n\ elige n}. \ end {ecuación*}

Solución 1

Daremos dos pruebas distintas de este hecho. El primero será muy similar al ejemplo anterior (contando subconjuntos). La segunda prueba es un poco más slicker, usando caminos de celosía.

Prueba

Considera la pregunta: “Cuántas pizzas puedes hacer usando\(n\) toppings when there are \(2n\) toppings to choose from?”

Respuesta 1: Hay\(2n\) toppings, from which you must choose \(n\). This can be done in \({2n \choose n}\) ways.

Respuesta 2: Divide los ingredientes en dos grupos de\(n\) toppings (perhaps \(n\) meats and \(n\) veggies). Any choice of \(n\) toppings must include some number from the first group and some number from the second group. Consider each possible number of meat toppings separately:

0 carnes:\({n \choose 0}{n \choose n}\), since you need to choose 0 of the \(n\) meats and \(n\) of the \(n\) veggies.

1 carne:\({n \choose 1}{n \choose n-1}\), since you need 1 of \(n\) meats so \(n-1\) of \(n\) veggies.

2 carnes:\({n \choose 2}{n \choose n-2}\). Choose 2 meats and the remaining \(n-2\) toppings from the \(n\) veggies.

Y así sucesivamente. El último caso es\(n\) meats, which can be done in \({n \choose n}{n \choose 0}\) ways.

Así el número total de pizzas posibles es

\ begin {equation*} {n\ choose 0} {n\ choose n} + {n\ choose 1} {n\ choose n-1} + {n\ choose 2} {n\ choose n-2} +\ cdots + {n\ choose n} {n\ choose 0}. \ end {ecuación*}

Esto no es del todo del lado izquierdo... aún así. Observe que\({n \choose n} = {n \choose 0}\) and \({n \choose n-1} = {n \choose 1}\) and so on, by the identity in Example 1.4.4. Thus we do indeed get

\ begin {ecuación*} {n\ elige 0} ^2 + {n\ elige 1} ^2 + {n\ elige 2} ^2 +\ cdots + {n\ elige n} ^2. \ end {ecuación*}

Dado que estas dos respuestas son respuestas a una misma pregunta, deben ser iguales, y así

\ begin {ecuación*} {n\ elige 0} ^2 + {n\ elige 1} ^2 + {n\ elige 2} ^2 +\ cdots + {n\ elige n} ^2 = {2n\ elige n}. \ end {ecuación*}

\(\square\)

Para una prueba alternativa, utilizamos caminos de celosía. Esto es razonable de considerar porque el lado derecho de la identidad nos recuerda el número de caminos desde\((0,0)\) to \((n,n)\).

Prueba

Considera la pregunta: ¿Cuántos caminos de celosía hay desde\((0,0)\) to \((n,n)\text{?}\)

Respuesta 1: Debemos viajar\(2n\) steps, and \(n\) of them must be in the up direction. Thus there are \({2n \choose n}\) paths.

Respuesta 2: Tenga en cuenta que cualquier camino desde\((0,0)\) to \((n,n)\) must cross the line \(x + y = n\). That is, any path must pass through exactly one of the points: \((0,n)\), \((1,n-1)\), \((2,n-2)\), …, \((n, 0)\). For example, this is what happens in the case \(n = 4\text{:}\)

Cuantos caminos pasan\((0,n)\text{?}\) To get to that point, you must travel \(n\) units, and \(0\) of them are to the right, so there are \({n \choose 0}\) ways to get to \((0,n)\). From \((0,n)\) to \((n,n)\) takes \(n\) steps, and \(0\) of them are up. So there are \({n \choose 0}\) ways to get from \((0,n)\) to \((n,n)\). Therefore there are \({n \choose 0}{n \choose 0}\) paths from \((0,0)\) to \((n,n)\) through the point \((0,n)\).

What about through \((1,n-1)\). There are \({n \choose 1}\) paths to get there (\(n\) steps, 1 to the right) and \({n \choose 1}\) paths to complete the journey to \((n,n)\) (\(n\) steps, \(1\) up). So there are \({n \choose 1}{n \choose 1}\) paths from \((0,0)\) to \((n,n)\) through \((1,n-1)\).

In general, to get to \((n,n)\) through the point \((k,n-k)\) we have \({n \choose k}\) paths to the midpoint and then \({n \choose k}\) paths from the midpoint to \((n,n)\). So there are \({n \choose k}{n \choose k}\) paths from \((0,0)\) to \((n,n)\) through \((k, n-k)\).

All together then the total paths from \((0,0)\) to \((n,n)\) passing through exactly one of these midpoints is

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \end{equation*}

Since these two answers are answers to the same question, they must be equal, and thus

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}. \end{equation*}

\(\square\)