Nacional 2023 N1 P6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
marcoalonzo

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024
Mensajes: 127
Registrado: Mar 18 Abr, 2023 4:52 pm
Medallas: 3

Nacional 2023 N1 P6

Mensaje sin leer por 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.
🔮oráculo y magia negra🔮
Avatar de Usuario
BR1

OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024
Mensajes: 355
Registrado: Sab 28 Oct, 2023 1:33 pm
Medallas: 2
Nivel: 1

Re: Nacional 2023 N1 P6

Mensaje sin leer por 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
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
2  
ACLARACIÓN: $1$ no es primo
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Nacional 2023 N1 P6

Mensaje sin leer por 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)

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1129
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2023 N1 P6

Mensaje sin leer por Fran5 »

Solución +21. En particular no es apta para nivel 1 :oops:
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
Imagen
1  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 278
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Nacional 2023 N1 P6

Mensaje sin leer por 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 :roll:
This homie really did 1 at P6 and dipped.
Avatar de Usuario
Ulis7s

OFO - Mención-OFO 2024
Mensajes: 212
Registrado: Dom 07 May, 2023 1:13 pm
Medallas: 1
Nivel: 1
Ubicación: La Pampa

Re: Nacional 2023 N1 P6

Mensaje sin leer por Ulis7s »

$Voy$ $a$ $dejar$ $esto$:
Spoiler: mostrar
IMG_20231115_163814.jpg
Aguante el participante Beto ;)
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
We needed 5 more more points!! :roll: @ulisess.kr
Avatar de Usuario
Kechi

OFO - Medalla de Bronce-OFO 2023 OFO - Medalla de Plata-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024
Mensajes: 87
Registrado: Mié 21 Sep, 2022 1:41 pm
Medallas: 3
Nivel: 2

Re: Nacional 2023 N1 P6

Mensaje sin leer por Kechi »

Pobre Carlos no tiene rostro.
3  
"La suma de las raíces cuadradas de dos lados de un triángulo isósceles es igual a la raíz cuadrada del lado restante."
Responder