Nacional 2016 N1 P4

Problemas que aparecen en el Archivo de Enunciados.
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Nacional 2016 N1 P4

Mensaje sin leer por tuvie »

En cada casilla de un tablero de [math] hay que escribir un número natural de [math] a [math] inclusive de modo que se usen todos estos números (se pueden repetir). Si una fila contiene dos casillas [math] y [math] con el mismo número [math] y [math] está a la izquierda de [math] entonces no hay números [math] en las casillas de la columna de [math] que estén por encima de [math].
El número [math] es el menor posible.
Determinar el valor de [math] y mostrar un tablero con esas condiciones.
1  
Peznerd
Mensajes: 113
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2016 N1 P4

Mensaje sin leer por Peznerd »

Está complicado, y durante el Certamen Nacional me dio [math] pero estoy muy convencido de que distribuyendo correctamente se puede llegar a:
Spoiler: mostrar
[math] porque [math] donde [math]. Ésto también aplica para todos los tableros de impar x impar ([math] x [math]) cantidad de casillas, o al menos esa es a la conclusión donde llegué luego de repensarme el ejercicio después del certamen. También tengo una idea de cómo puede ser el tablero, pero prefiero ver cómo lo han hecho ustedes :mrgreen:
Un día vi una vaca sin cola vestida de uniforme

$$\int u \, dv=uv-\int v \, du\!$$
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Nacional 2016 N1 P4

Mensaje sin leer por jhn »

Aquí tienes una solución con 9, que es el mínimo:
Spoiler: mostrar
8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 9 9
7 7 6 6 5 5 4 4 3 3 2 2 1 1 9 9 8
7 6 6 5 5 4 4 3 3 2 2 1 1 9 9 8 8
6 6 5 5 4 4 3 3 2 2 1 1 9 9 8 8 7
6 5 5 4 4 3 3 2 2 1 1 9 9 8 8 7 7
5 5 4 4 3 3 2 2 1 1 9 9 8 8 7 7 6
5 4 4 3 3 2 2 1 1 9 9 8 8 7 7 6 6
4 4 3 3 2 2 1 1 9 9 8 8 7 7 6 6 5
4 3 3 2 2 1 1 9 9 8 8 7 7 6 6 5 5
3 3 2 2 1 1 9 9 8 8 7 7 6 6 5 5 4
3 2 2 1 1 9 9 8 8 7 7 6 6 5 5 4 4
2 2 1 1 9 9 8 8 7 7 6 6 5 5 4 4 3
2 1 1 9 9 8 8 7 7 6 6 5 5 4 4 3 3
1 1 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2
1 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2
9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1
9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1
1  
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Nacional 2016 N1 P4

Mensaje sin leer por Prillo »

Spoiler: mostrar
Veamos que no se puede con [math]. Dado un tablero que satisface las condiciones, fijemos un [math] y sea [math] la cantidad de veces que aparece [math] en las filas [math] respectivamente, donde se numera las filas de arriba a abajo. Miremos las filas de abajo para arriba. La ultima fila tiene [math] apariciones de [math]. Salvo por la de mas a la derecha, las (al menos) [math] restantes bloquean las columnas en las que estan, a lo que me refiero: en las filas de arriba ya no pueden aparecer [math] en esas columnas. En general, siguiendo para arriba, la fila [math] tiene [math] apariciones de [math], de las cuales las (al menos) [math] de la izquierda bloquean esas columnas. Como ninguna columna puede bloquearse mas de una vez (o se violaria la condicion del enunciado), tenemos que [math], luego [math]. Es decir que cada numero [math] aparece a lo sumo [math] veces en el tablero.

Ahora, si fuera [math], habria un numero que aparece en el tablero al menos [math] veces, contradiciendo nuestra observacion. Entonces [math] es el minimo posible (en el post de arriba de jhn hay un ejemplo con [math]).
Responder