En la combinatoria, ¿por qué el preguntar el problema opuesto muchas veces es más fácil?

Question

Considerar el problema del cumpleaños. Dado $N$ de las personas, ¿cuántas maneras hay de que exista algún par de personas con el mismo cumpleaños?

La enumeración de las posibilidades que rápidamente se convierte en tedioso

Sin embargo, el complemento problema (Da $N$ de las personas, ¿cuántas maneras hay para no tener el mismo cumpleaños?) es trivial.

En campos como el de la probabilidad, esto tiene obvias aplicaciones, debido a que el "complemento de la ley":

si $A \cup A^c = S$ donde $S$ es la totalidad del espacio muestral, entonces $$P(A) + P(A^c) = 1 \implies P(A) = 1 - P(A^c)$$

En general, este patrón es muy común. Intuitivamente, sentido:

• de alguna manera, el complemento problema es pedir mucho menos información

• si uno tiene algo así como el "complemento de la ley" en la probabilidad, entonces, en algunos ámbito de aplicación restringido de problemas, el "complemento de la ley" da, en cierto sentido, "la misma cantidad de información"

Lo que hacen los matemáticos llaman lo que yo estoy haciendo aquí? Estoy overblowing qué tan común es una tendencia que es?

Answer 1

En la combinatoria de contestar "y" estilo de preguntas, es fácil, porque es una multiplicación. Esto es fácil, ya que puede eliminar los factores comunes entre los denominadores y numeradores, y el uso de la binomial/función de elección. También en cualquier momento que un 1 o 0 sube la operación se convierte en trivial.

Sin embargo pidiendo "o" estilo de preguntas es difícil, ya que tienes que añadir los números y, a continuación, que tienen un doble conteo y restar.

De Morgan leyes de $\neg ( a \vee b) = ( \neg a \wedge \neg b)$ permite transformar un "o" problema "y no" el problema de que es más fácil.

Answer 2

Pongámoslo de esta manera: para cada problema, hay dos formas equivalentes para ponerlo, con cada manera de ser un simple complemento de la otra. Puede haber una disparidad: uno es considerablemente más sencillo que el otro. Pero, ambos son inmediatamente equivalente, puede preguntar a cualquiera de las preguntas en el lugar de los otros.

Así entonces, el problema se convierte, por qué la gente elegir a representar para el menor problema simple? Creo que la razón es, probablemente, pedagógico: mirando el complemento problema es un esfuerzo económico, pero extremadamente valiosa herramienta para resolver problemas de combinatoria. Es una lección que vale la pena aprender que vale la pena mirar el complemento problema, a la derecha del palo, a ver si es más fácil.

No podrían ser algunas de las razones más profundas, posiblemente sobre una cierta correlación entre el más difícil de los dos problemas de tener una estética superior a la mayoría de las veces, pero este tipo de pregunta no es exactamente en el puente de mando de un simple matemático como yo.

Answer 3

Tiene, básicamente, respondió a esta, en su punto puntos.

Yo diría de la siguiente manera:

Respondiendo a la complementaria versión de una combinatoria pregunta es a menudo más fácil si la pregunta original contiene (directa o indirectamente) la restricción de que "al menos uno".

En tales casos, la obtención de la respuesta normalmente requiere la enumeración sobre un gran número de combinaciones, mientras que el complementario de la versión sólo contiene una pequeña cantidad de posibilidades para enumerar y por lo tanto es más susceptible de cálculo directo.

Por ejemplo, en el problema del cumpleaños, puede ser formulada como: "$N$ de la gente, ¿cuál es la probabilidad de que al menos un par de personas que tienen en común un cumpleaños"

El complemento de la versión es "Dado $N$ de la gente, ¿cuál es la probabilidad de que exactamente cero personas tienen en común un cumpleaños?"

Otro de matemáticas stackexchange preguntas donde se puede ver este fenómeno:

• Cuántas combinaciones contener, al menos, dos Como

• Las combinaciones de ingredientes de la pizza con al menos uno de origen vegetal, y al menos uno de carne.

• Combinaciones, incluyendo "a la mayoría"

Answer 4

En la combinatoria cuando sabemos el número total de todas las posibilidades y contar el número de posibilidades de satisfacer la condición C o violar lo son equivalentes problemas. Que es saber que usted consiga la otra por simple resta de los otros número conocido.

Muchas veces para contar las posibilidades de satisfacer la condición C, puede ser difícil directamente. Si C puede ser dividido en discontinuo posibilidades con que cuente en cada uno de los casos y sumarlos.

ASÍ que todo se reduce a si la condición C o su negación (complemento) tiene más casos. Elegir el de menor número de casos. En un experimento invovling contando cuántos resultados en el lanzamiento de 10 monedas de producir al menos 2 jefes de las posibilidades de 2 cabezas, 3 cabezas, y así sucesivamente hasta 10 cabezas. Sin embargo, el complemento es de 0 cabezas o 1 cabezas.

Claro que la segunda es más fácil.

El punto clave es cómo muchos de los casos (mutuamente excluyentes o disjuntos) lo que hay que analizar. Esto le dirá a usted que es el más fácil del problema original o complementaria con el problema.

Answer 5

El conjunto de todos los posibles problemas combinatorios es simétrico y toma el complemento. Pero los problemas que encontramos no se eligen de forma aleatoria a partir de un conjunto de este tipo, por lo general, estos problemas tienen problemas que son lo suficientemente desafiantes como para ser interesantes, pero también son solucionables. Una gran clase de tales problemas son los que se simplifican al tomar el complemento.