OMA Foros

Ocho jueces califican a los participantes de un concurso con $1$ o $0$. Se sabe que para cada dos participantes: hay dos jueces que calificaron a ambos con $1$; hay dos jueces que calificaron al primero con $1$ y al segundo con $0$; hay dos jueces que calificaron al primero con $0$ y al segundo con $1$; y finalmente hay dos jueces que calificaron a ambos con $0$. Determinar el máximo número posible de participantes en el concurso.

Solución +21. En particular no es apta para nivel 1

Spoiler: mostrar

Lema: Sea $C \subset \mathbb{F}_q^n$ un subconjunto que verifica lo siguiente: "Para cada dos vectores de $C$, ellos difieren en al menos $d$ coordenadas". Luego $|C| \leq q^{n+1-d}$.

Demo del lema:

Spoiler: mostrar

Es un lindo ejercicio: dos vectores cualesquiera tienen que ser distintos en al menos $d$ coordenadas. Ignorando las primeras $d-1$, tenemos que las restantes $k = n-(d-1)$ tienen que ser distintas para cada vector, de modo que hay inyección de $C$ en $\mathbb{F}_2^k$

Afirmación 1: Podemos suponer que el primer juez es copado y pone todos $1$, por lo que podemos ignorarlo

Demo:

Spoiler: mostrar

Es fácil ver que todo participante tiene exactamente $4$ unos y $4$ ceros. Si un participante tiene $0$ en el primer juez, su complemento (cambiando $0$ por $1$ y $1$ por $0$ en los $8$ jueces) intercambia de lugar los $4$ jueces que coinciden y los $4$ jueces que difieren con cualquier otro participante, de modo que podemos considerarlo en lugar del original

Ahora: Supongamos que hay $p$ participantes. Sin pérdida de generalidad podemos suponer que el primer juez es copado y pone todos $1$, por lo que podemos ignorarlo. A cada participante le asignamos un vector en $ \mathbb{F}_2^7$ según el puntaje del jurado.
Consideremos un participante con $7$ puntuaciones $0$,
También, podemos considerar a cada participante su puntaje opuesto (cambiando $0$ por $1$ y $1$ por $0$ en los $7$ jueces)

De este modo tenemos un conjunto $C$ de $2(p+1)$ vectores en $\mathbb{F}_2^7$.

Afirmación 2: Para cada dos vectores de $C$, ellos difieren en al menos $3$ coordenadas

Demo:

Spoiler: mostrar

Claramente ningún vector no nulo de $C$ tiene menos de $3$ unos. Además todos excepto el nulo y el "todos uno" tienen o bien $3$ unos y $4$ ceros o bien $4$ unos y $3$ ceros, de modo que ninguno tiene menos de $3$ ceros. Dentro de los originales, por enunciado difieren en exactamente $4$ coordenadas. Ergo, dentro de los complementos, difieren en exactamente $4$ coordenadas. Entre un vector original y un complemento, difieren en exactamente $3$ coordenadas, aquellas $3$ restantes en las que coincidían.

Luego $2(p+1) =|C| \leq 2^{7+1-3} = 2^4 = 16$ de donde $p \leq 7$

El ejemplo es entre comillas, "único", así que pueden ver las soluciones anteriores

PD1:

Spoiler: mostrar

https://en.wikipedia.org/wiki/Hamming(7,4)

PD2:

Spoiler: mostrar

Spoiler: mostrar

Dado un torneo cualquiera donde representamos a cada participante por una fila de $0$ y $1$ supongamos un reorden de los jueces de modo que el primer participante es $11110000$ (esto es válido ya que no estamos cambiando solo los votos del primer participante ni lo que votó cada jurado, sino que estamos cambiando el orden de los votos en todos los participantes) luego los votos de cualquier otro participante son de la forma $AB$ donde $A$ y $B$ son dos tiras de $0$ y $1$ de largo cuatro con dos $0$ y dos $1$.
Afirmo que dados $A$ y $\overline{A}$ de esta forma (donde entendemos a este complemento cómo el resultado de cambiar todos los $0$ por $1$ y viceversa) existen a lo sumo $2$ participantes que empiezan con alguna de las dos. Supongamos sin pérdida de generalidad que existen $3$ de los cuales $2$ empiezan con $A$, si uno de estos es $AB$ el otro deberá ser $A\overline{B}$. Si el tercero empezara también con $A$, por comparación con el primero, debería ser igual al segundo que no puede ocurrir. Luego el tercero empieza con $\overline{A}$ pero por comparación con el primero debe ser $\overline{A}B = \overline{A\overline{B}}$ que es el complemento del segundo, absurdo!
Como existen $\binom{4}{2} = 6$ bloques de este tipo existen $3$ pares $A-\overline{A}$ y como por cada uno de estos aparecen a lo sumo dos participantes más, aparecen a lo sumo $6$ participantes más.
Lo que en total son a lo sumo $7$ participantes y hay un ejemplo.

Bueno es lo mismo que escribió BR1

$Voy$ $a$ $dejar$ $esto$:

Spoiler: mostrar

IMG_20231115_163814.jpg

Aguante el participante Beto

Pobre Carlos no tiene rostro.