OMA Foros

Problema 333

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

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$.

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$.

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.

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.

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

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?

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)$.

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

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.