OMA Foros

1. Cada dos filas son distintas
2. Cada fila contiene exactamente $4$ casillas con $1$
3. Para cada $3$ filas hay una columna que las interseca en $3$ casillas con $0$

Spoiler: mostrar

Equivalentemente: hallar la maxima cantidad de subconjuntos de [math]S = \{1,2,\dots,12\} de [math]4 elementos tales que la union de cada tres de ellos nunca sea [math]S.

Si elegimos los [math]\binom{11}{4} subconjuntos de [math]4 elementos de [math]\{1,2,\dots,11\} es claro que cumplen la condicion del enunciado.

Veamos ahora que si se elige mas de [math]\binom{11}{4} subconjuntos, habra tres cuya union sea [math]S. Notemos que la cantidad de subconjuntos de [math]S de [math]4 elementos es [math]k = \binom{12}{4}. Consideremos todas las ternas (no ordenadas) [math]\{A,B,C\} de subconjuntos de [math]S de [math]4 elementos tales que [math]A\cup B\cup C = S. La cantidad de tales ternas es [math]T = \binom{k}{3}. Sumando sobre todas estas ternas la cantidad de sus elementos que son subconjuntos elegidos, nos da a lo sumo [math]2T, pues para cada terna a lo sumo [math]2 de sus elementos pueden ser subconjuntos elegidos y hay [math]T ternas. Por otra parte, cada subconjunto de [math]S de [math]4 elementos aparece en la misma cantidad de ternas [math]t = \binom{k - 1}{2}, entonces cada uno de los subconjuntos elegidos contribuye en exactamente [math]t a esta suma. Como elegimos mas de [math]\binom{11}{4} subconjuntos, la suma calculada de esta otra manera nos da mayor a [math]\binom{11}{4}t. Pero es facil ver que [math]\binom{11}{4}t = 2T, entonces tenemos una contradiccion.

Spoiler: mostrar

332

NPCPepe escribió: ↑Jue 24 Oct, 2019 4:08 pm prillo mira que dice cada DOS filas son distintas, osea yo entendi que si agarras dos filas y otras dos filas y las comparas son distintas, pero podes tener como maximo 3 filas iguales osea al numero combinatorio ese hay que sumarle 2 y da

Spoiler: mostrar

332