Maratón de Problemas

Matías

OFO - Medalla de Bronce FOFO Pascua 2019 - Medalla OFO - Medalla de Plata FOFO 8 años - Medalla Especial OFO - Medalla de Oro
Mensajes: 175
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 7
Nivel: 2

Re: Maratón de Problemas

Mensaje sin leer por Matías » Vie 15 Feb, 2019 12:20 pm

Problema 333

¿Cuáles números son múltiplos de $333$ en la sucesión $1$, $11$, $111$, $1111$, $\ldots$?

Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 791
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Maratón de Problemas

Mensaje sin leer por Vladislao » Sab 16 Feb, 2019 12:10 am

Spoiler: mostrar
Infinitos.

Llamemosle $r_k$ al $k$-ésimo término de la sucesión, i.e., $r_k = \frac{10^k-1}{9}$. Notar que $r_k \equiv 0 \pmod{333}$ si y sólo si $10^k-1 \equiv 0 \pmod{2997}$. Ahora bien, como $10$ es coprimo con $2997$, por el Teorema de Euler, tomando cualquier $k$ que sea un múltiplo de $\varphi(2997)$, estamos hechos.
Problema 334

Sean $x_1<\ldots<x_n$ enteros positivos. Demostrar que se pueden elegir $\lceil \frac{n}{3}\rceil$ de esos números de modo que no hay una terna $x_i<x_j<x_k$ entre los elegidos de modo que $x_i+x_j=x_k$.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 936
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico » Sab 16 Feb, 2019 12:47 am

Vladislao escribió:
Sab 16 Feb, 2019 12:10 am
Spoiler: mostrar
Infinitos.
Ojo
Spoiler: mostrar
Pregunta "¿Cuáles?", no "¿Cuántos?".
Solución 333
Spoiler: mostrar
Sea $1_n$ el número formado por $n$ números $1$. Vemos que $333=3^2\cdot 37$, luego $9\mid 333\mid 1_n$, es decir $1_n\equiv 0(9)$, pero $n\equiv \underbrace{1+1+\ldots +1+1}_{n}\equiv 1_n\equiv 0(9)$, de donde si $1_n$ es múltiplo de $333$ entonces $n$ es múltiplo de $9$.
Ahora sea $k\in \mathbb{N}$, tenemos que $1_{9k}=111\cdot 10^{9k-3}+111\cdot 10^{9k-6}+\ldots +111\cdot 10^6+111\cdot 10^3+111$, pero $111=3\times 37$, por lo que $37\mid 1_{9k}$, y por la congruencia anterior tenemos $9\mid 1_{9k}$, como $9$ y $37$ son coprimos, tenemos que $333=9\cdot 37\mid 1_{9k}$.
Entonces $1_n$ es múltiplo de $333$ si y sólo si $n$ es múltiplo de $9$.
Vladislao escribió:
Sab 16 Feb, 2019 12:10 am
Problema 334

Sean $x_1<\ldots<x_n$ enteros positivos. Demostrar que se pueden elegir $\lceil \frac{n}{3}\rceil$ de esos números de modo que no hay una terna $x_i<x_j<x_k$ entre los elegidos de modo que $x_i+x_j=x_k$.
6  
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 936
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico » Mié 03 Abr, 2019 11:23 pm

Ya pasó más de un mes, así que cambio el problema por uno un poco más fácil.

Problema 334
Un número natural $n$ es fachero si para todos los números $x$ e $y$ naturales se verifica $$n\mid (x+y)^5-x^5-y^5 \Leftrightarrow n\mid (x+y)^7-x^7-y^7$$
Decidir si la cantidad de números facheros es finita o infinita.
[math]

HelcsnewsXD
Mensajes: 4
Registrado: Jue 13 Sep, 2018 8:59 am
Nivel: 2

Re: Maratón de Problemas

Mensaje sin leer por HelcsnewsXD » Lun 15 Abr, 2019 3:54 pm

Solución problema 334

Disculpen si no se entiende bien, es mi primera vez publicando en el foro.
Spoiler: mostrar
Como n divide a (x+y)^5-x^5-y^5, y también a (x+y)^7-x^7-y^7, podemos considerar a n como el MCD (máximo común divisor) entre estos dos números. Para demostrar que es infinito, deberemos poder encontrar un valor para el MCD (es decir, n) para todo valor de x e y. Para esto, lo primero que hacemos es factorizar (solo la parte numérica) los dos polinomios:

(x+y)^5-x^5-y^5=5*y*x^4+10*y^2*x^3+10*y^3*x^2+5*y^4*x
=5*(y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x)

(x+y)^7-x^7-y^7=7*y*x^6+21*y^2*x^5+35*y^3*x^4+35*y^4*x^3+21*y^5*x^2+7*y^6*x
=7*(y*x^6+3*y^2*x^5+5*y^3*x^4+5*y^4*x^3+3*y^5*x^2+y^6*x)

De los dos números tomados, despreciamos la parte numérica y consideramos solo el segundo término. Ahora, como queremos saber si existe un MCD, diferente de 1, entre estos dos números, debemos dividirlos (el mayor es dividido por el menor). Es por esto que tenemos lo siguiente:

(y*x^6+3*y^2*x^5+5*y^3*x^4+5*y^4*x^3+3*y^5*x^2+y^6*x) / (y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x)=
=x^2+y*x+y^2

Es decir, el resultado de la división es entero, por lo que el resto es 0 y, por ende, sí existe un MCD entre estos dos números. Ahora bien, como el MCD, es decir n, es el máximo divisor, tenemos que:

n=y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x

Es por esto que la respuesta a este problema es que la cantidad de números facheros es infinita ya que para cada posible par de naturales (x; y), n va a ser también natural.
Problema 335

Beto trata de adivinar un entero positivo n. Sabe que tiene exactamente 250 divisores enteros positivos distintos 1=d1<d2<d3<…<d250=n. Por turnos, pregunta un índice j a su elección, 2≤j≤249, y recibe como respuesta el número dj. En el caso de que ya haya preguntado j, tiene prohibido preguntar 251−j. Determinar el menor número de turnos con los que Beto puede determinar con certeza el número n.

maxiR

OFO - Mención FOFO 8 años - Mención Especial OFO - Medalla de Bronce
Mensajes: 21
Registrado: Vie 26 Ene, 2018 3:30 pm
Medallas: 3
Nivel: 1
Ubicación: Barrancas

Re: Maratón de Problemas

Mensaje sin leer por maxiR » Lun 15 Abr, 2019 7:31 pm

Este problema es el 1 del Selectivo de $IMO$ de 2015

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 936
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico » Lun 15 Abr, 2019 8:18 pm

maxiR escribió:
Lun 15 Abr, 2019 7:31 pm
Este problema es el 1 del Selectivo de $IMO$ de 2015
La idea de la maratón es que los usuarios propongan problemas para que otros los resuelvan, no importa el origen de los mismos. Es recomendable que los problemas no estén en el foro, porque hay usuarios que podrían conocerlos y se pierde la dinámica, pero no está prohibido porponerlos. Si sabés de qué competencia es el último problema, no deberías decirlo, solamente esperar a que alguien lo resuleva, o como mucho agregar un "¿Podrías cambiarlo?" al final del mensaje. Además, siendo un usuario nuevo, es razonable que no haya visto todo el foro como para saber dónde está el problema.
De todas formas, @HelcsnewsXD ¿Podrías proponer un problema distinto?
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 936
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico » Lun 15 Abr, 2019 8:59 pm

HelcsnewsXD escribió:
Lun 15 Abr, 2019 3:54 pm
Solución problema 334
Spoiler: mostrar
Como n divide a (x+y)^5-x^5-y^5, y también a (x+y)^7-x^7-y^7, podemos considerar a n como el MCD (máximo común divisor) entre estos dos números. Para demostrar que es infinito, deberemos poder encontrar un valor para el MCD (es decir, n) para todo valor de x e y. Para esto, lo primero que hacemos es factorizar (solo la parte numérica) los dos polinomios:

(x+y)^5-x^5-y^5=5*y*x^4+10*y^2*x^3+10*y^3*x^2+5*y^4*x
=5*(y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x)

(x+y)^7-x^7-y^7=7*y*x^6+21*y^2*x^5+35*y^3*x^4+35*y^4*x^3+21*y^5*x^2+7*y^6*x
=7*(y*x^6+3*y^2*x^5+5*y^3*x^4+5*y^4*x^3+3*y^5*x^2+y^6*x)

De los dos números tomados, despreciamos la parte numérica y consideramos solo el segundo término. Ahora, como queremos saber si existe un MCD, diferente de 1, entre estos dos números, debemos dividirlos (el mayor es dividido por el menor). Es por esto que tenemos lo siguiente:

(y*x^6+3*y^2*x^5+5*y^3*x^4+5*y^4*x^3+3*y^5*x^2+y^6*x) / (y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x)=
=x^2+y*x+y^2

Es decir, el resultado de la división es entero, por lo que el resto es 0 y, por ende, sí existe un MCD entre estos dos números. Ahora bien, como el MCD, es decir n, es el máximo divisor, tenemos que:

n=y*x^4+2*y^2*x^3+2*y^3*x^2+y^4*x

Es por esto que la respuesta a este problema es que la cantidad de números facheros es infinita ya que para cada posible par de naturales (x; y), n va a ser también natural.
Hola, la solución no es correcta, una breve explicación
Spoiler: mostrar
Lo que vos estás haciendo es:
Para cada par $(x,y)$, encontramos un $n$ que divide a ambos polinomios, entonces hay infinitos $n$.

El problema con esto es que $n$ va a ser fachero cuando divida a ambos polinomios para cualquier valor de $x$ e $y$, es decir, el $n$ no puede depender de $x$ e $y$. Por ejemplo, $2$ es fachero pues siempre divide a ambos polinomios, sin importar el valor de $x$ ni de $y$. Pero $5$ no es fachero, pues divide a $30=(1+1)^5-1^5-1^5$ pero no a $126=(1+1)^7-1^7-1^7$, que son los números que obtenemos para el par $(x,y)=(1,1)$.
Última edición por Gianni De Rico el Mar 16 Abr, 2019 4:29 pm, editado 2 veces en total.
[math]

HelcsnewsXD
Mensajes: 4
Registrado: Jue 13 Sep, 2018 8:59 am
Nivel: 2

Re: Maratón de Problemas

Mensaje sin leer por HelcsnewsXD » Mar 16 Abr, 2019 10:49 am

Me olvidé de parte de para todo (x; y) Jajaj
La solución sería la siguiente entonces:
Spoiler: mostrar
Supongamos que la cantidad de números facheros n es infinita. Consideremos un nj>6.
Como cada n debe dividir a los dos números sea cualquiera el valor entero positivo de x e y, debe dividir si x=1 e y=1. Ahora bien, en este último caso, (x+y)^5-x^5-y^5=30 y (x+y)^7+x^7-y^7=126, por lo que MCD=2*3. Y, como dice el teorema fundamental de la aritmética, todo número tiene una única factorización, nj debe ser sí o sí un divisor de MCD=6. Pero recordemos que nj>6. Es por esto que se llega a un absurdo y se demuestra que la cantidad es finita.
Dejo abierto a que otro proponga

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 936
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico » Mar 16 Abr, 2019 4:28 pm

La solución sigue siendo incorrecta

Respuesta:
Spoiler: mostrar
La cantidad de números facheros es infinita.
Sobre tu solución:
Spoiler: mostrar
Hay dos errores. Primero, el que debe ser divisor de $6$ según tu solución es $n$, no tenés ninguna información sobre $nj$. Y segundo, $n$ no tiene que dividir a ambos polinomios para cualquier par $(x,y)$, lo que ocurre es que si divide a uno, entonces tiene que dividir al otro.
[math]

Responder