Rioplatense 2019 - N1 P6

Problemas que aparecen en el Archivo de Enunciados.
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 261
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Rioplatense 2019 - N1 P6

Mensaje sin leer por BrunZo » Sab 14 Dic, 2019 12:57 pm

Llamamos palíndromos a aquellos números que se leen igual de izquierda a derecha que de derecha a izquierda. Por ejemplo: $7$, $282$ y $3443$ son palíndromos, pero $1212$ no lo es. Dado un entero positivo $N$, decimos que un entero positivo $M$ es un porción de $N$ si los dígitos de $M$ aparecen en secuencia y en ese mismo orden dentro de los dígitos de $N$. Por ejemplo, para $N=1618$, hay nueve números que son una porción de $N$:
$$1,\quad 6,\quad 8\quad 16,\quad 18,\quad 61,\quad 161,\quad 618,\quad 1618$$
En el pizarrón está escrito un número $N$ de $28$ dígitos, todos ellos distintos de $0$. Ana busca todos los números que son una porción de $N$ y cuenta cuántos de esos números son palíndromos. (Notar que si un mismo palíndromo aparece varias veces entre los dígitos de $N$, Ana sólo lo cuenta una vez.)
a) Determinar la mínima cantidad de palíndromos que puede encontrar Ana.
b) Determinar la máxima cantidad de palíndromos que puede encontrar Ana.
1  

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 261
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: Rioplatense 2019 - N1 P6

Mensaje sin leer por BrunZo » Sab 14 Dic, 2019 9:18 pm

a)
Spoiler: mostrar
Yo digo que hay como mínimo $3$ palíndromos. Por ejemplo:
$$1231231231231231231231231231$$
contiene únicamente a los palíndromos $1$, $2$ y $3$.

Veamos que no pueden haber $2$ palíndromos o menos:
Como cada dígito forma un palíndromo por sí mismo, queda claro que no puede haber más de dos clases de dígitos. Más aún, es claro que no puede haber sólo una clase de dígito, en caso contrario, el número sería, digamos, $11111\dots 1$, que tiene $28$ palíndromos. Es decir, tendrían que haber exactamente dos clases de dígitos.
Ahora, es claro que alguna clase de dígito aparecerá más de una vez, tomémoslo. Ahora, si consideramos la porción que empieza en la primera aparición de este dígito y que termina en la segunda aparición de este dígito, podemos asegurarnos que va a tener la forma:
$$1222\dots 2221$$
Con alguna cantidad de dígitos $2$ (posiblemente ninguno). Pero esta porción sería un tercer palíndromo, por lo que siempre habrá al menos tres palíndromos.

b)
Spoiler: mostrar
Yo digo que hay como máximo $28$ palíndromos. Por ejemplo:
$$\underbrace{1111111111111111111111111111}$$
contiene a los $28$ palíndromos $1$, $11$, $111$, $1111$, etc.

Veamos que no pueden haber más de $28$ palíndromos:
Para cada clase de palíndromo distinto, vamos a decir que su representante es la primera aparición de este palíndromo en el número. Notemos que la cantidad de palíndromos distintos es igual a la cantidad de representantes.
Supongamos que hay $29$ representantes. Por el Principio del Palomar, como hay $28$ dígitos, queda claro que existen dos representantes que terminan en el mismo dígito. Sean $A$ y $B$ estos representantes y supongamos, sin pérdida de generalidad, que $\text{long}\, A>\text{long}\, B$.
$$\underbrace{00000\overbrace{000000000}^B}_{A}$$
Llamemos por $B'$ a la porción que consiste de los primeros $\text{long}\, B$ dígitos de $A$.
Como $A$ es un palíndromo, leer los primeros $\text{long}\, B$ dígitos de $A$ es lo mismo que leer los últimos $\text{long}\, B$ dígitos en orden inverso: $B'=\text{rev}\, B$.
Como $B$ es un palíndromo, leer sus dígitos en orden inverso es lo mismo que leerlos en orden natural: $\text{rev}\, B=B$.
Combinando, $B'=\text{rev}\, B=B$, pero $B'$ aparece antes que $B$ y dijimos que $B$ era la primera aparición de su clase de palíndromo, por lo que llegamos a un absurdo.
Esto implica que no puede haber más de $28$ palíndromos.


Aclaración: Por $\text{long}\,N$ denoto a la cantidad de dígitos del número $N$ y por $\text{rev}\,N$ denoto al número que se obtiene al leer los dígitos de $N$ en orden inverso. (Notar que $\text{rev}\,N=N$ si y sólo si $N$ es un palíndromo.)
1  

Responder