¿Cómo verificar si estás contando correctamente?

Question

La combinatoria es "difícil" incluso a nivel elemental en el sentido de que verificar respuestas se vuelve extremadamente complicado. Mientras que en álgebra, una solución a una ecuación como $$x^2+4x+3=0$$ es deseada, la solución se puede obtener y puede ser verificada al sustituir la respuesta de nuevo en la ecuación.

Considera por ejemplo, este problema.

Encuentra el número de formas de crear $5$ grupos de exactamente dos entre $10$ personas de manera que ninguna persona pertenezca a dos grupos.

Una solución incorrecta: Primero selecciona un grupo de dos personas de las $10$ personas. Hay ${10 \choose 2}$ formas de hacer esto. El siguiente grupo puede ser seleccionado en ${8 \choose 2}$ formas y así sucesivamente. Así que por el principio de multiplicación, el número total de formas es igual al valor del siguiente producto.

$${10 \choose 2} \times {8 \choose 2} \times {6 \choose 2} \times {4 \choose 2}$$

La idea en la siguiente (incorrecta) solución es crear una biyección entre el número de permutaciones de las personas paradas en una fila y el número de grupos que se pueden formar. Aunque es la misma idea que una posible solución correcta utiliza, los grupos están contados en exceso.

Solución incorrecta-2: Hay $10!$ formas en las cuales las $10$ personas pueden pararse en una fila. La primera y la segunda persona, la tercera y la cuarta y así sucesivamente se colocan en un único grupo. Dado que intercambiar la primera y segunda posición dará otra permutación pero los mismos grupos, necesitamos dividir entre $2$. De manera similar, intercambiar la tercera y cuarta posición dará una permutación diferente pero los mismos grupos. Por lo tanto, en última instancia, el número total de formas de formar los $5$ grupos será $$\frac{10!}{2^{5}}$$

La solución que arroja la respuesta correcta es la siguiente

Solución correcta-2: Hay $10!$ formas en las cuales las $10$ personas pueden pararse en una fila. La primera y la segunda persona, la tercera y la cuarta y así sucesivamente se colocan en un único grupo. Dado que intercambiar la primera y segunda posición dará otra permutación pero los mismos grupos, necesitamos dividir entre $2$. De manera similar, intercambiar la tercera y cuarta posición dará una permutación diferente pero los mismos grupos. También considera el siguiente hecho. Si las personas (indicadas por letras) están dispuestas en una permutación de la siguiente manera, ABCDEFGHIJ entonces la permutación CDABIJGHEF también corresponde al mismo conjunto de grupos, por eso es necesario dividir entre $5!$ ya que hay $5!$ formas de hacerlo
Por lo tanto, en última instancia, el número total de formas de formar los $5$ grupos será $$\frac{10!}{2^{5}\times5!}$$

Las preguntas sobre la corrección de un procedimiento de conteo adoptado son bastante comunes en este foro. (Añadiré algunos enlaces si crees que es necesario). Esta es una razón por la cual esta pregunta, aunque subjetiva, ha sido formulada. Además, no he encontrado ningún texto que aborde cómo evitar subcontar o sobrecontar. Cualquier discusión sobre técnicas para evitar subcontar/sobrecontar o cómo verificar el conteo será muy apreciada.

Nota:

1. Los problemas a los que me refiero cuando menciono problemas de combinatoria son problemas de combinatoria enumerativa. Esto limitará considerablemente el alcance de la discusión.
   2. Aunque contar de dos formas es a veces una forma útil de verificar si la solución obtenida es correcta, se necesita mucha ingeniosidad para enumerar la respuesta a cada problema de dos formas. Por eso, cualquier respuesta a esta pregunta puede evitar esa técnica y también no incluir enumerar todas las posibilidades.

Answer 1

La verificación del conteo puede ser más difícil que la de la aritmética, pero las dos soluciones incorrectas no pueden atribuirse a esta diferencia. Son interpretaciones incorrectas de un problema de palabras. Esto puede ocurrir de la misma manera en un problema de palabras de álgebra. No está claro si podemos hacer algo mejor que heurísticas como "¿Dónde importa el orden?", "¿Están esas cosas etiquetadas o no?" o "¿He contado de más?" En la práctica, las sugerencias en los comentarios son buenos diagnósticos para las personas que resuelven problemas de conteo.

En principio, sin embargo, la verificación es posible. Supongamos que estamos de acuerdo en que el conjunto en cuestión está mejor formalizado por un conjunto $A$ especificado matemáticamente. Entonces podemos formalizar nuestras soluciones y verificarlas.

Específicamente, verificamos respuestas con pruebas biyectivas. Esto consiste en construir dos conjuntos $A$ y $B$ y una biyección $f:A \rightarrow B$. Luego demostramos que $f$ es una biyección. Una vez establecido, hemos verificado que $|A| = |B|$.

Para problemas de conteo elementales, generalmente aplicamos los principios de multiplicación o adición a fórmulas de conteo ya establecidas, las cuales a su vez pueden establecerse con estos mismos principios. La versión más formal de aplicar el principio de multiplicación es proporcionar una biyección $f:A \rightarrow B \times C$ donde $A,B,C$ son conjuntos. Por ejemplo, si construyes un conjunto $A$ y crees que tiene $2^3 \cdot 3!$ elementos, puedes verificar esto construyendo una biyección de $A$ a $B_3 \times S_3$.

(En caso de que no estés familiarizado, $S_3$ es el conjunto de permutaciones de un conjunto de 3 elementos y $B_3$ es el conjunto de todos los subconjuntos de $\{1,2,3\}$.)

Para el problema en cuestión, podríamos (de manera descuidada) formalizar el conjunto como $$A = \{\{G_1,G_2,\ldots,G_5\}: G_i \subseteq \{P_1,\ldots,P_{10}\}, |G_i| = 2, |G_i \cap G_j| = \emptyset \}$$

Si estamos de acuerdo en que esta es una traducción aceptable, entonces podemos verificar que hay una biyección $f:A \times B_5 \times S_5 \rightarrow S_{10}$. También podemos verificar que una función específica $f:A \times B_5 \rightarrow S_{10}$ no es una biyección. O, si se prefiere, las divisiones pueden ser capturadas con relaciones de equivalencia y proceder de nuevo a construir funciones y verificar.

Aunque esto no es tan simple como sustituir un valor propuesto en $x^2 + 4x + 3$ para verificar, las pruebas pueden ser tan formales que se convierten en cálculos verificables. Parece que el documento "Tests and Proofs for Enumerative Combinatorics" sigue este camino con asistentes de prueba computacionales.

Answer 2

Muchos problemas de palabras son de la siguiente forma: "Un objeto $x$ tiene las propiedades $P_i(x)={\rm true}$ $(1\leq i\leq n)$. ¿Qué es $x$?"

Las condiciones dadas definen un conjunto $$S:=\{x\in X\>|\>P_i(x)\ (1\leq i\leq n)\}\ ,$$ donde el "universo" $X$ de posibles $x$ se entiende según el contexto del problema. Al resolver este tipo de problema, se establece una cadena (o incluso un grafo dirigido) de razonamiento del siguiente tipo:

$$x\in S\Rightarrow\ldots\Rightarrow\ldots\Rightarrow\ldots\Rightarrow x\in\{x_1,x_2,\ldots x_r\}\ ,$$ o similar. A menos que se tenga una "teoría general" para este tipo especial de problemas, que garantice "exactamente $r$", o, por ejemplo, un "espacio vectorial de dimensión $r$" de soluciones, se debe probar cada candidato $x_i$, $1\leq i\leq r$, para verificar si $x_i$ es realmente una solución del problema original.

Ahora, los problemas de conteo son de una naturaleza diferente. Se define un cierto conjunto $X$, para que todos lo vean, y se afirma que este conjunto tiene cierta propiedad, por ejemplo, que tiene $9!$ elementos. Tal vez tengas una "prueba supuesta" para esta afirmación; pero definitivamente no hay una "verificación fácil". Cabe mencionar que no hay una prueba fácil para afirmar que los ceros no triviales de la función zeta se encuentran en la línea crítica.

Answer 3

Esto me recuerda a esta pregunta que respondí recientemente.

Sí, validar tu respuesta no es fácil cuando se trata de preguntas de combinatoria o probabilidad. No hay un método genérico que se pueda seguir "automáticamente".

La simulación de Monte Carlo o el cálculo por fuerza bruta pueden ayudar, siempre y cuando hayas entendido la pregunta correctamente y tu modelo/programa sea correcto. Ten en cuenta que algunas preguntas son más fáciles de validar con este método porque tienen un modelo de simulación/cómputo directo, mientras que otras son más difíciles porque el modelo no es evidente o es difícil de programar (y luego te preocupas por validar tu programa :)).

Por ejemplo, piensa en esta pregunta: Tres personas lanzan un par de dados cada una. ¿Cuál es la probabilidad de que una persona haya sacado al menos un $1$, mientras que las otras dos no tengan un dado con un $3$ o menos? Esto sería relativamente fácil de modelar y simular. Simulas muchos lanzamientos de tres pares de dados y verificas si estas condiciones se cumplen en cada intento. Cuentas las veces que se cumplieron y las divides entre el número total de intentos.

Por otro lado, ¿cómo simularías/calculrías el problema en cuestión (contando las agrupaciones)? Puedo pensar en el siguiente enfoque de cálculo por fuerza bruta: listar todas las permutaciones de 10 personas, agrupándolas cada vez en pares (el primero y segundo es un par, el tercero y cuarto es otro, etc). Si una permutación resulta en una configuración de agrupaciones que ya hemos encontrado entonces no la contamos. Ciertamente se puede hacer, pero hay mucho margen para errores de programación al intentar determinar si dos agrupaciones de pares son iguales. Además, si tuviéramos 100 personas en lugar de 10, el tiempo de cálculo explotaría usando este método. El mensaje clave es que aunque la simulación o el cálculo por fuerza bruta pueden ayudar en algunos casos, no son una cura para todo.

Probar tu solución con valores pequeños también puede ayudar. Pero ten cuidado. A veces las fórmulas incorrectas dan la respuesta correcta para números pequeños. Para nuestra pregunta específica, este no es el caso (la fórmula incorrecta produce resultados incorrectos incluso para valores pequeños) así que podríamos haber recibido ayuda si hubiéramos probado este método. Digamos que tenemos $4$ personas en lugar de $10$. El primer (es decir, incorrecto) método daría ${4 \choose 2} = 6$, pero cuando intentamos enumerar todas las agrupaciones posibles manualmente, obtenemos solo $3$ formas. Al investigar esto podemos obtener una idea de cómo estamos contando doble.

Pero ¿cómo sabemos que solo hay $3$ formas de agrupar $4$ elementos? ¿Qué pasa si cometimos un error en nuestro conteo manual? Una forma de sentirnos más seguros sobre nuestro resultado es darse cuenta de que una vez que elegimos un elemento y creamos todas las posibles agrupaciones con los otros 3 elementos restantes, entonces el último par se 've obligado' a formarse. Esto me lleva al quid de la cuestión de la validación.

Lo más útil es pensar en diferentes maneras de resolver el problema. En la pregunta que enlazas, esto es lo que ha hecho el autor. Se han dado cuenta de que pueden ver el problema de esta manera: Elige una persona y luego tienes $9$ posibilidades de agruparla con alguien. Este es nuestro primer par. Luego elige otra persona (no importa quién) y tienen $7$ posibilidades de ser emparejados. Y así sucesivamente con el resto. Por lo tanto, las agrupaciones posibles deberían ser: $9\cdot 7\cdot 5\cdot 3 = 945$. En la pregunta, no está claro que vieron el conflicto con el resultado de la primera fórmula (parece que no calcularon el resultado de la primera fórmula) pero podrían haberlo hecho fácilmente. Esto les podría haber dado alguna idea sobre el problema. Una vez que encuentres una discrepancia, puedes empezar a preguntarte por qué. Es posible que un método de solución sea más intuitivo para ti (por ejemplo, el método que acabo de describir me parece más intuitivo que pensar en combinaciones), por lo que esto puede guiarte para encontrar el error en la otra forma. En cualquier caso, puedes atacar el problema desde diferentes ángulos y pensar en lo que tus soluciones hacen en problemas pequeños para tener claridad sobre lo que está sucediendo.

No hay garantía de que encuentres un error, pero atacar el problema desde muchos ángulos es la mejor manera que conozco. Un gran efecto secundario de este proceso es que gradualmente obtienes más perspicacia sobre los errores que tú y otras personas cometen, y te vuelves más seguro sobre tus soluciones en problemas futuros.