Nacional 2023 N1 P6

[marcoalonzo]

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.

[BR1]

Spoiler: mostrar

Por definición, todo participante recibirá cuatro 1 y cuatro 0.
Sean J1, J2, J3, J4, J5, J6, J7 y J8 los jueces.
Asumamos que un participante recibe un 1 de J1, J2, J3 y J4 y recibe un 0 de J5, J6, J7 y J8.
- Cualquier otro participante deberá recibir dos 0 y dos 1 de parte de J1, J2, J3 y J4.
- Cualquier otro participante deberá recibir dos 0 y dos 1 de parte de J5, J6, J7 y J8.

Llamaremos "nota A" al conjunto de notas dadas por J1, J2, J3 y J4, y "nota B" al conjunto de notas dadas por J5, J6, J7 y J8.

Si dos participantes reciben la misma nota A, por ejemplo 0; 1; 1; 0, las notas B de estos dos participantes deberán ser opuestas entre sí (los 0 se cambian por 1 y viceversa), por ejemplo 1; 1; 0; 0 y 0; 0; 1; 1. Esto demuestra que no puede haber tres participantes con la misma nota A o la misma nota B (no hay tres notas opuestas entre sí).

El mismo razonamiento se puede aplicar a la inversa, si dos participantes reciben dos notas A opuestas entre sí, sus notas B deberán ser iguales.

Las notas opuestas son las siguientes:
Clase i) 0011 y 1100
Clase ii) 0101 y 1010
Clase iii) 0110 y 1001
No pueden haber más de dos notas A de la misma clase ni más de dos notas B de cada clase.

En conclusión, dado un participante cualquiera no pueden haber más de 6 participantes aparte de ese, lo cual significa que la máxima cantidad de participantes es 7
El ejemplo es el siguiente:

Captura de pantalla 2023-11-20 181939.png

[usuario250]

Spoiler: mostrar

El máximo de participantes que se puede es 7

Partamos de los 2 primeros participantes (PARTICIPANTES 1 y 2) con sus calificaciones.
ABCDEFGH
11110000
11001100

Para cada uno de los restantes participantes x, la cantidad de 1's entre C y D, deberá ser la misma que la cantidad de 1's entre E y F (para que el participante x tenga la misma cantidad de 1's en común con el participante 1 que con el participante 2).
Si el participante tiene 0 1's entre C y D y entre E y F, de acuerdo con las condiciones del enunciado, sus calificaciones son 11000011.
Si el participante tiene 2 1's entre C y D y entre E y F, de acuerdo con las condiciones del enunciado, sus calificaciones son 00111100.
Como se puede observar, estos dos casos son excluyentes, ya que no coinciden en la calificación de ningún juez.
Entonces, de estos dos casos puede haber a lo sumo 1 (PARTICIPANTE 3).

Ahora bien, faltan los participantes que tienen 1 1's entre C y D y 1 1's entre E y F. Por las condiciones del enunciado, estos participantes tienen 1 1's entre A y B y 1 1's entre G y H.
Sin pérdida de generalidad (se puede porque hasta ahora A y B tienen calificaciones idénticas, lo mismo con C y D, con E y F y con G y H), tomemos que el primero de los participantes que quedan tiene las calificaciones 10101010 (es decir, 1 según A,C,E,G y 0 según B,D,F,H).
Como en estos participantes la calificación de A es opuesta a la de B, la de C opuesta a la de D, la de E opuesta a la de F y la de G opuesta a la de H, quedémosno con las calificaciones de A,C,E y G.
El primer participante tiene calificación 1111.
Para cumplir con las condiciones del enunciado, dos cualesquiera de estos participantes tienen que coincidir en exactamente 2 de estas 4 calificaciones.
Entonces tenemos:
1) 1111 (PARTICIPANTE 4)
Para evitar confusiones con los jueces, renombremos a A,C,E y G como I,J,K y L en algún orden. Entonces, el siguiente participante tiene calificaciones:
IJKL
2) 1100 (PARTICIPANTE 5)
Para los restantes de este estilo, tienen que tener 1 1's entre I y J y 1 1's entre K y L.
Tomemos las calificaciones de I y K. Los participantes restantes,
A) entre I y K tienen 1 1's y 1 0's
B) coinciden, para cada pareja, en exactamente una de estas 2 calificaciones (I,K).
Las posibles parejas de calificaciones de I y K, de acuerdo a A), son:
11
10
01
00
Que las podemos dividir en parejas (11, 00) y (10, 01). Notar que en cada una de estas dos parejas podemos elegir a lo sumo 1 de los dos casos (porque entre ellos no coindicen en ninguna de las 2 calificaciones, lo que contradice a B)).
Por lo tanto, podemos tomar a lo sumo 2 participantes más (PARTICIPANTES 6 y 7)

Finalmente, un ejemplo (tomando A=I, C=J, E=K y G=L), de 7 participantes es el siguiente:
11110000
11001100
11000011
10101010 (este es el 1111 de IJKL)
10100101 (este es el 1100 de IJKL)
10011001 (este es el 11 de IK -------> 1010 de IJKL)
10010110 (este es el 10 de IK -------> 1001 de IJKL)

[Fran5]

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

[Fedex]

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