Generalización:
Queremos demostrar que [math] \ exist x, y \ in \ mathbb {N} [/ math] de modo que una sociedad que contenga [math] x [/ math] niños y [math] y [/ math] niñas debe contener un subconjunto de [matemáticas] k_B [/ matemáticas] niños y [matemáticas] k_G [/ matemáticas] niñas (donde [matemáticas] k_B, k_G \ in \ mathbb {N} [/ matemáticas]), para las cuales {todos los niños conocer a todas las chicas} o {ningún chico conoce a ninguna de las chicas}.
Para la pregunta específica proporcionada, se nos da que [matemáticas] k_B = k_G = 5 [/ matemáticas].
- ¿Qué es una extensión HNN?
- ¿Qué es una explicación intuitiva de una derivada de Lie?
- ¿Cómo se calcula la tasa de inflación del IPC? ¿Cuál es la ecuación?
- ¿Cuál es el significado de los correos de Peck?
- Conozco la teoría pero no puedo realizar operaciones básicas como sumar y restar en las pruebas.
Editar:
Podemos generalizar esto aún más. En lugar de etiquetar cada borde de niño a niña como “sabe” o “no sabe”, podemos permitir que sea una de las etiquetas [math] m \ in \ mathbb {N} [/ math]. Todavía podemos demostrar que [matemática] \ existe x, y [/ matemática] tal que una sociedad que contenga [matemática] x [/ matemática] niños y [matemática] y [/ matemática] niñas debe contener un subconjunto de [matemática] k_B [/ math] niños y [math] k_G [/ math] niñas, para lo cual todos los niños tienen la misma etiqueta para todas las niñas.
Para nuestra pregunta específica, [matemáticas] m = 2 [/ matemáticas].
Responder:
Para garantizar que un subconjunto de [matemática] k_B [/ matemática] niños y [matemática] k_G [/ matemática] satisfaga la propiedad relevante, necesitamos, en total, como máximo [matemática] y = 2 (k_G-1 ) +1 [/ matemáticas] niñas y [matemáticas] x = 2 (k_B-1) \ binom {y} {k_G} +1 [/ matemáticas] niños.
Para la pregunta específica proporcionada, requerimos, en total, como máximo [matemáticas] y = 2 (5-1) + 1 = 9 [/ matemáticas] niñas y [matemáticas] x = 2 (5-1) \ binom {9 } {5} + 1 = 1009 [/ matemáticas] niños.
Editar:
Para una mayor generalización de permitir que cada borde de niño a niña sea una de las etiquetas [math] m [/ math], aún podemos satisfacer la propiedad relevante (solo extendiendo el razonamiento existente). Necesitaríamos, en total, como máximo [matemática] y = m (k_G-1) +1 [/ matemática] niñas y [matemática] x = m (k_B-1) \ binom {y} {k_G} +1 [ / matemáticas] muchachos.
Razonamiento:
Un niño determinado [matemáticas] i [/ matemáticas] conoce o no conoce a cada una de las niñas. Para garantizar que haya al menos [math] k_G [/ math] chicas que el niño [math] i [/ math] sabe o no sabe, necesitamos al menos [math] 2 (k_G-1) +1 [/ matemáticas] total de niñas (según el principio de Pigeonhole). Entonces elegimos [math] y \ geq 2 (k_G-1) +1 [/ math] para el resto de la prueba, para satisfacer esta propiedad.
Tenga en cuenta que hay [matemática] 2 \ binom {y} {k_G} [/ matemática] total posible [matemática] k_G [/ matemática] -conjuntos de niñas (la [matemática] 2 [/ matemática] es porque estamos considerando ” saber “y” no sé “categorías por separado). Por lo tanto, si tuviéramos [math] x = 2 (k_B-1) \ binom {y} {k_G} +1 [/ math] total boys, entonces necesariamente existiría al menos un [math] k_G [/ math] – subconjunto de niñas que se encuentra en la categoría “sabe” o “no sabe” para al menos un subconjunto de niños [matemática] k_B [/ matemática] (según el Principio de Pigeonhole). Esto se debe a que cada niño contribuiría al recuento de al menos un subconjunto de niñas [matemáticas] k_G [/ matemáticas] (de al menos una de las categorías de “saber” y “no saber”). Dado que [matemáticas] 2 (k_B-1) \ binom {y} {k_G} +1 [/ matemáticas] los niños (palomas) están asociados con al menos [matemáticas] 1 [/ matemáticas] de [matemáticas] 2 \ binom { y} {k_G} [/ math] subconjuntos de niñas (agujeros), debe haber al menos [math] 1 [/ math] subconjunto de niñas (agujero) asociado con al menos [math] k_B [/ math] niños (palomas) )
