Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 2

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: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 2

Mensaje sin leer por Fedex »

Decimos que una palabra es un palíndromo si se lee igual en ambos sentidos. Construimos una secuencia de palabras de la siguiente manera: $P_0=a$, $P_1=b$ y para $n \geq 2$ la palabra $P_n$ resulta de escribir la palabra $P_{n-2}$ seguida de $P_{n-1}$.
Demostrar que para $n\geq 1$ la palabra $P_1P_2\cdots P_{n-1}P_n$ es un palíndromo.
This homie really did 1 at P6 and dipped.
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: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Simulacro Nacional 2022 Politecnico - Nivel 3 Problema 2

Mensaje sin leer por Fedex »

Spoiler: mostrar
Dada una palabra $P$ definimos $\overline{P}$ como la palabra $P$ leída al revés. Entonces las palabras palíndromo son aquellas que satisfacen que $\overline{P} = P$.
Notemos las siguientes cosas:
  • $\overline{\overline{A}} = A$ ya que si damos vuelta una palabra $2$ veces tenemos la palabra original.
  • $\overline{AB} = \overline{B} \; \overline{A}$ ya que si leemos al revés una palabra compuesta leemos primero la palabra del final al revés y luego la del principio. En general, se da que $\overline{A_1A_2 \cdots A_{i-1} A_i} = \overline{A_i} \; \overline{A_{i-1}} \; \cdots \; \overline{A_2} \; \overline{A_1}$
Primero verificamos lo pedido para $n = 0,1,2$. La palabra que se forma con $n = 0$ es vacía por lo que trivialmente esto es cierto. La palabra $P_1 = b$ también es palíndromo. Finalmente la palabra $P_2 = ab$ luego $P_1P_2 = bab$ que es palíndromo.

Ahora vamos a demostrar lo pedido por inducción: Supongamos que el enunciado es cierto para $n \geq 0$ y para $n+2 \geq 2$ luego $P_1P_2\cdots P_n$ y $P_1P_2\cdots P_{n+2}$ son palíndromos, veremos que esto es cierto para $n+3$.
Notar que:
$$\overline{P_1\cdots P_{n+3}} = \overline{P_{n+3}} \; \overline{P_1\cdots P_n P_{n+1}P_{n+2}} = \overline{P_{n+3}} P_1 \cdots P_n P_{n+1} P_{n+2} = \overline{P_{n+2}} \; \overline{P_{n+1}}P_1\cdots P_n P_{n+1}P_{n+2} $$
Donde si leemos al revés lo ultimo tenemos que:

$$\overline{\overline{P_{n+2}} \; \overline{P_{n+1}} P_1\cdots P_n P_{n+1}P_{n+2}} = \overline{P_{n+2}} \; \overline{P_{n+1}} \; \overline{P_1\cdots P_n} \; \overline{\overline{P_{n+1}}} \; \overline{\overline{P_{n+2}}}
= \overline{P_{n+2}} \; \overline{P_{n+1}} \; \overline{P_1\cdots P_n} P_{n+1} P_{n+2}
= \overline{P_{n+2}} \; \overline{P_{n+1}} \; P_1\cdots P_n P_{n+1} P_{n+2}$$

Por lo que si leemos al revés esta palabra, es la misma. Donde concluimos que $\overline{P_1\cdots P_{n+3}}$ es un palíndromo, es decir, $P_1\cdots P_{n+3}$ es un palíndromo, como queríamos demostrar.
This homie really did 1 at P6 and dipped.
Responder