XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

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

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
Mensajes: 203
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 5
Nivel: 3

XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

Mensaje sin leer por Sandy »

Un tablero de $7\times7$ puede estar vacío o contener una pieza cuadrada invisible de $2\times2$ que cubra exactamente $4$ casillas del tablero. En cada casilla del tablero se puede colocar un chip que al encenderse indica si esa casilla está o no cubierta por la pieza. Todos los chips colocados sobre el tablero se encienden en el mismo instante. Determinar el menor número de chips que se necesita para saber con certeza si la pieza está presente en el tablero y, de estarlo, cuál es su ubicación exacta.
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Matiasmk
Mensajes: 1
Registrado: Lun 08 Oct, 2018 1:12 pm
Nivel: 1

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

Mensaje sin leer por Matiasmk »

Creo que la distribución mas eficiente es la siguiente
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
o=vacio
x=chip
A lo mejor hay una mejor demostracion que solo el separar los tal que ninguno tenga otro chip adyacente o en sus esquinas

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 1011
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

Mensaje sin leer por Matías V5 »

Matiasmk escribió:
Lun 02 Mar, 2020 10:29 am
Creo que la distribución mas eficiente es la siguiente
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
o=vacio
x=chip
A lo mejor hay una mejor demostracion que solo el separar los tal que ninguno tenga otro chip adyacente o en sus esquinas
Esa distribución no funciona: si se enciende el primer chip (el de arriba a la izquierda), hay $4$ posibles posiciones de la pieza cuadrada (los cuatro cuadrados de $2\times2$ que contienen la casilla donde está el chip). La idea es poner chips para poder determinar con certeza la posición de la pieza cuadrada.
Tené en cuenta además que como el problema pide hallar el mínimo número de chips, no solamente hay que encontrar una distribución que funcione sino también justificar por qué con menos chips es imposible cumplir el objetivo.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 1551
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

Mensaje sin leer por Gianni De Rico »

Una pista
Spoiler: mostrar
Mirar este problema.
¿Cómo se relacionan los problemas? ¿Podemos llevarlos a los dos a un mismo tipo de enunciado?
¿La respuesta del anterior alcanza para saber en dónde está la pieza?
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Responder