Triángulos diferentes

Problema 3 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

Tenemos siete listones, cuyas longitudes, todas diferentes, en centímetros, son 3, 4, 7, 8, 24, 26 y 28.

¿Cuántos triángulos diferentes podemos construir uniendo tres de estos listones?

Se supone que dos triángulos son iguales si sus tres lados son iguales, aunque sean simétricos en lugar de iguales, es decir, se les puede dar la vuelta y poner los listones al revés, y siguen siendo iguales.

Solución a octógono irregular

Problema 2 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

A partir de un cuadrado, encontramos los puntos medios de los cuadrados y unimos cada vértice con uno de los puntos medios.

A partir de esas líneas, dibujamos el octógono amarillo que vemos en la figura.

Calcula la proporción del área total del cuadrado que ocupa ese octógono.

Solución: Continue reading Solución a octógono irregular

Octógono irregular

Problema 2 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

A partir de un cuadrado, encontramos los puntos medios de los cuadrados y unimos cada vértice con uno de los puntos medios.

A partir de esas líneas, dibujamos el octógono amarillo que vemos en la figura.

Calcula la proporción del área total del cuadrado que ocupa ese octógono.

Solución: Aquí.

Solución a sucesión recursiva

Problema 2 de la fase nacional de la 56 Olimpiada Matemática Española (2020)
Se dirige a una edad de: 16-17 años

Consideramos la sucesión de números enteros f(n), con n mayor o igual que 1, definida por las siguientes condiciones:

f(1) = 1.

Si n es par, f(n) = f(n/2).

Si n es impar y f(n – 1) es impar, entonces f(n) = f(n – 1) – 1.

Si n es impar y f(n – 1) es par, entonces f(n) = f(n – 1) + 1.

a) Calcula f(22020 – 1).

b) Demuestra que la sucesión no es periódica, es decir, que no existen enteros positivos t y n0 que cumplan que si n es mayor que n0, entonces f(n + t) = f(n).

Solución:

Este es un problema en el que es muy importante generalizar con rigor, para lo cual vamos a estudiar los primeros elementos de la sucesión.

También es útil haber tenido un contacto previo con los números binarios, ya que la importancia de la paridad en la definición de la sucesión sugiere que van a tener una gran importancia.

Los primeros elementos formarían la cadena siguiente:

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, …

Aparentemente no hay ninguna regularidad, pero si los relacionamos con su expresión binaria, podemos observar un hecho curioso.

Voy a construir una sucesión muy parecida, a la que llamaré la sucesión g, pero en lugar de restar 1 a f(n – 1), le voy a sumar 1.

Y voy a representar cada término de la sucesión junto a su posición, y la representación en números binarios de esa posición.

1 – 1 – 1
2 – 10 – 1 (como 1)
3 – 11 – 2 (2 + 1)
4 – 100 – 1 (como 2)
5 – 101 – 2 (1 + 1)
6 – 110 – 2 (como el 3)
7 – 111 – 3 (2 + 1)
8 – 1000 – 1 (como el 4)
9 – 1001 – 2 (1 + 2)
10 – 1010 – 1 (como el 5)

Es evidente que la sucesión se parece mucho, sólo que en este caso, a diferencia de f, g tiene valores mayores. Está claro que f no crece, porque la única manera de aumentar es sumando a un valor anterior, pero si ese valor es 1, en f restamos, y volvemos a 0.

Y en f tampoco bajamos de cero, porque si el valor es 0, es par, luego sumamos.

Básicamente, la f es como la g en el sentido de que si g es par, f vale 0, y si g es impar, f vale 1. La sucesión f es la llamada paridad de g.

Pues bien, si os dais cuenta, g representa el número de cifras 1 en la representación binaria.

Claramente, si n es par, su cantidad de cifras 1 es la misma que la de n/2, ya que multiplicar por 2 equivale a añadir un 0 como última cifra.

Y si es impar, tiene un 1 más que el número anterior, ya que un “0” del final del número lo cambiamos por un “1”.

Lo que quiero decir es que f sólo puede valer 0 o 1, y consiste en que vale 0 si la cantidad de 1 de la representación en binario de un número tiene una cantidad par de 1, y 1 si la representación en binario de un número tiene una cantidad impar de 1 entonces vale 1.

Podemos demostrarlo con los argumentos dados antes, por recursividad, tal y como está bien definida la función.

Observando esto, está claro que f(22020 – 1) vale 0, ya que es un número que está formado por 2020 unos.

Una forma directa de demostrarlo puede ser probando por inducción que 2n – 1 vale 0 si n es par y 1 si n es impar. Como siempre es impar, se basa en el número anterior, que será 2n – 2 = 2(2n – 1 – 1), que por hipótesis de inducción ya tiene la propiedad buscada.

Ver que no es periódica es bastante más complicado. Si hemos dado con la analogía de que el valor de f depende del número de cifras en formato binario, podemos observar que cuando pasamos de una potencia a otra de 2, vuelve a repetir la misma secuencia, pero invertida.

Por ejemplo, 1, 1, 0, 1, 0, 0, 1, 1 son los 8 primeros, y los de 9 a 15 son 0, 0, 1, 0, 1, 1, 0. Sin embargo, las potencias de 2, tanto 8 como 16, siempre valen 1. Con lo que las secuencias se van haciendo cada vez más largas.

Para probar que no es periódica (como casi siempre que queremos ver que algo no sucede) lo mejor suele ser proceder por reducción al absurdo, es decir, suponer que sí lo es y llegar a una contradicción.

Supongamos que sí es periódica, por lo que existe un valor n0 y un valor t, como dice el enunciado, de forma que f(n + t) = f(n) para cada n mayor que n0.

Para llegar a un absurdo sin mucha dificultad, podemos pensar en los dígitos en binario de t. Necesitamos tomar una n que podamos manejar con claridad. Puesto que tenemos que negar esta propiedad, trataremos de llegar a una situación que no pueda darse esta igualdad.

Imaginemos que t es un número binario, como por ejemplo 1 100 111. En este caso, tiene 5 cifras 1, con lo que f(t) = 1. Pero ese no significa mucho para nosotros. Sin embargo, si tomamos el valor 1 000 000, sabemos que al sumarlo a t obtendremos 10 100 111, es decir, obtendremos la misma cantidad de unos, es decir, que f(n + t) = 1. Y si tomamos el valor 11 000 000, al sumarlo obtendremos el valor para n + t (en binario) de 100 100 111, es decir, que volveremos a tener el mismo valor para la cantidad de cifras 1 que t. La diferencia entre 1 000 000 y 11 000 000 es que mientras que f en el primero da 1, f en el segundo da 0, y en ambos casos f(n + t) debería ser f(n), luego es imposible.

Ahora bien, ¿cómo nos aseguramos que eso no pasa hasta un cierto valor suficientemente grande?, pues tomamos el valor n0 y usamos una potencia suficientemente grande. Imagina que nos dicen que n0 fuese 101 110 001. Pues usamos como candidatos a n los números 1 001 000 000 (cuyo valor de f es 0) y 1 011 000 000, que tiene un valor de f de 1. en ambos casos, al sumar t nos da la misma cantidad de 1 en binario (1 más que t), y por lo tanto el valor de f(n + t) debería ser el mismo, lo que es imposible.

¿Cómo se puede hacer de manera formal?

Habría que demostrar que si 2p es mayor que un cierto valor x, f(2p + x) = 1 – f(x). Es fácil de ver si aplicamos la hipótesis de inducción y desglosamos los casos en que x es par o impar. Eso quiere decir que si sumamos potencias suficientemente grandes a un valor, f cambia su valor al opuesto (de 1 a 0 y de 0 a 1).

Además, si tenemos el valor p que cumple que 2p <= t < 2p + 1 (es decir, la última cifra binaria de p), se tiene que f(t) = f(2p + t). Probar esto es más complicado, salvo que se conozca muy bien el sistema binario.

Tratemos de probarlo por inducción sobre t. Está claro que para t = 1 se cumple (el valor correspondiente de p es 0). Supongamos que es cierto hasta un cierto valor t – 1 y tratemos de ver que es cierto para t. Habrá que diferenciar dos casos, aquel en el que tienen el mismo p y el que tienen diferente p. Si tienen el mismo p, puesto que se define f por recursión es muy sencillo apoyarnos en la hipótesis de inducción. Si no tienen el mismo valor de p, es porque coincide que t es exactamente 2p + 1 , y entonces tenemos que f(t) = 1, y f(2p + 1 + t) = f(2p + 2) = 1.

Una vez que hemos averiguado estas propiedades con sumas de potencias grandes de 2 y t, elegimos un valor de p de forma que 2p <= t < 2p + 1 y un valor de q que al menos sea tres unidades mayor que p y que 2q sea también mayor que n0. A partir de ahí y las propiedades que hemos trabajado, concluiremos que f(2q + 2p) es diferente de f(2q + 2p + 1 + 2p), pero que f(2q + 2p + t) = f(2q + 2p + 1 + 2p + t), por la elección de p, y los dos posibles candidatos para n son mayores que n0.

Como veis, no es un trabajo sencillo, y eso sin contar la presión de tiempo que supone el concurso (aproximadamente una hora por problema).

Sucesión recursiva

Problema 2 de la fase nacional de la 56 Olimpiada Matemática Española (2020)
Se dirige a una edad de: 16-17 años

Consideramos la sucesión de números enteros f(n), con n mayor o igual que 1, definida por las siguientes condiciones:

f(1) = 1.

Si n es par, f(n) = f(n/2).

Si n es impar y f(n – 1) es impar, entonces f(n) = f(n – 1) – 1.

Si n es impar y f(n – 1) es par, entonces f(n) = f(n – 1) + 1.

a) Calcula f(22020 – 1).

b) Demuestra que la sucesión no es periódica, es decir, que no existen enteros positivos t y n0 que cumplan que si n es mayor que n0, entonces f(n + t) = f(n).

Solución: Aquí.

Solución a la edad de la madre

Problema 1 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

Cuando una madre escribe tres veces seguidas su edad obtiene un número de seis cifras que es el producto de seis números: La edad de sus cuatro hijos (que son números diferentes), la edad del padre y su propia edad.

¿Cuál es la suma de las edades de los cuatro hijos?
Solución:
Continue reading Solución a la edad de la madre

La edad de la madre

Problema 1 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

Cuando una madre escribe tres veces seguidas su edad obtiene un número de seis cifras que es el producto de seis números: La edad de sus cuatro hijos (que son números diferentes), la edad del padre y su propia edad.

¿Cuál es la suma de las edades de los cuatro hijos?
Solución: Aquí.

Solución a prueba de aptitud

Problema 0 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

A una prueba de aptitud se presentan 2019 personas, 995 chicos y 1024 chicas, y exactamente 1234 superan la prueba.

Calcula cuál es el valor de A – B, siendo A el número de chicas que han superado la prueba y B el número de chicos que no la han superado.

Solución: Continue reading Solución a prueba de aptitud

Prueba de aptitud

Problema 0 del concurso marató de problemes 2019
Se dirige a una edad de: 14-15 años

A una prueba de aptitud se presentan 2019 personas, 995 chicos y 1024 chicas, y exactamente 1234 superan la prueba.

Calcula cuál es el valor de A – B, siendo A el número de chicas que han superado la prueba y B el número de chicos que no la han superado.

Solución: Aquí.

Solución a juego para dos

Problema 4 de la fase nacional de la 56 Olimpiada Matemática Española (2020)
Se dirige a una edad de: 16-17 años

Ana y Benito juegan a un juego que consta de 2020 rondas.

Inicialmente, en la mesa hay 2020 cartas, numeradas de 1 a 2020, y Ana tiene una carta adicional con el número 0.

En la ronda k-ésima, el jugador que no tiene la carta k – 1 decide si toma la carta k o si se la entrega al otro jugador.

El número de cada carta indica su valor en puntos.

Al terminar el juego, gana quien tiene más puntos.

Determina qué jugador tiene la estrategia ganadora, o si ambos jugadores pueden forzar el empate, y describe la estrategia a seguir.
Solución: Continue reading Solución a juego para dos