Maratón de Problemas

Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Maratón de Problemas

Mensaje sin leer por Matías »

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-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 808
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 »

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-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

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  
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años
Mensajes: 59
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 4

Re: Maratón de Problemas

Mensaje sin leer por HelcsnewsXD »

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.
Na, clave la solución :lol:
maxiR

OFO - Mención-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Bronce-OFO 2019
Mensajes: 26
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 »

Este problema es el 1 del Selectivo de $IMO$ de 2015
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

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?
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años
Mensajes: 59
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 4

Re: Maratón de Problemas

Mensaje sin leer por HelcsnewsXD »

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
Na, clave la solución :lol:
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
Responder