Autor Tema: Difícil problema de divisibilidad

0 Usuarios y 1 Visitante están viendo este tema.

23 Enero, 2011, 06:33 pm
Leído 2135 veces

Lolyta

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 262
  • Karma: +0/-0
  • Sexo: Femenino
Hola.
Todas las sucesiones posibles de 7 dígitos se escriben una a continuación de la otra en una fila para formar un nº de 7000000 dígitos. Prueba que sea cual sea el orden  en que se han escrito las sucesiones, el número resultante es siempre divisible por 239.

Me dan una pista: 239 divide a \( 10^{-7}-1 \).

Agradecería su ayuda.

24 Enero, 2011, 06:24 am
Respuesta #1

jgonzalez

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 16
  • Karma: +0/-0
  • Sexo: Masculino
Sean \( A_{i} \) (con \( 1 \le i \le K \)) una posible ordenación de las sucesiones de 7 dígitos, entonces el número que se forma concatenando las sucesiones es \( N = A_{K}\dots{}A_{2}A_{1} \), podemos representar esto como una sumatoria \( N = A_{K} 10^{7(K-1)} + \cdots + A_{3} 10^{14} + A_{2} 10^{7} + A_{1} \). Ahora usando que \( 10^7 \equiv 1 \mod{239} \), queda \( N \equiv A_{K} + \cdots +A_{2} + A_{1} \mod{239} \). Que es más simple de calcular y además no depende del orden en que se concatenen las sucesiones.

PD: Una posible forma de probar esto ultimo es que se puede agrupar las sucesiones de manera que de a pares sumen \( 999999 = 10^{7} \). Por ejemplo si las sucesiones fueran de un digito te quedaria algo asi (0+9) + (1+8) + (2+7) + (3+6) + (4+5).

26 Enero, 2011, 03:36 pm
Respuesta #2

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

¿No serán todas las sucesiones posibles de siete dígitos iguales?
Por ejemplo:

\( 1111111,7777777,8888888,\ldots \)

Saludos.
Eram quod es, eris quod sum.

27 Enero, 2011, 01:59 am
Respuesta #3

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
No Teón. Yo coincido con jgonzalez, aunque su explicación no esté escrita de forma muy clara.

Una aclaración nomás, "for the record": \( 999999\neq 10^7 \), pero se entiende a lo que ibas  :D
"...parecido pero nada que ver"

27 Enero, 2011, 02:59 am
Respuesta #4

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Hasta el momento, si bien no lo analicé a fondo, pero creo que es correcto

\( N \equiv A_K + \cdots +A_2 + A_1 \mod 239 \)

Pero en tal caso se puede demostrar que para algunas sucesiones

\( N\not\equiv 0\mod 239 \)

Supongamos

\( A_{k-1}+\cdots +A_2 + A_1\equiv r \mod 239 \)

Podemos elegir un \( A_k\equiv s\mod 239\quad\forall s:0\leq s <239 \)

Luego podemos elegir s tal que
\( r+s\not\equiv 0 \mod 239\Rightarrow N\not\equiv 0\mod 239 \)

Saludos.
Eram quod es, eris quod sum.

27 Enero, 2011, 04:58 am
Respuesta #5

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Lo que pasa es que él usa la letra \( K \) innecesariamente. Es \( K=10^7 \), no es una variable extraña ni nada. Su argumento es que lo que queda va a ser divisible por 239 porque podemos asociar a cada tira \( A_i \) con \( 9.999.999-A_i \).
"...parecido pero nada que ver"

27 Enero, 2011, 10:33 am
Respuesta #6

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola Pepito

Hola.
Todas las sucesiones posibles de 7 dígitos se escriben una a continuación de la otra en una fila para formar un nº de 7000000 dígitos. Prueba que sea cual sea el orden  en que se han escrito las sucesiones, el número resultante es siempre divisible por 239.

Me dan una pista: 239 divide a \( 10^{-7}-1 \).

Agradecería su ayuda.

Conforme a lo que tú interpretas, ¿Cuál sería un elemento cualquiera de la sucesión?

Según mi interpretación, puede ser un número arbitrario de 7 dígitos, podemos dar la concesión de que el más significativo no sea 0.

Uno de nuestros elementos de la sucesión podría ser

\( 1111112  \), y como este el que se nos ocurra de 7 dígitos, inclusive del enunciado no se desprende que estos elementos deban ser distintos.
Qué impide que sean casi todos todos \( 1111111 \) excepto uno de ellos que puede ser
\( 1111112 \).

No veo muy claro el enunciado :P

Saludos.


Eram quod es, eris quod sum.

27 Enero, 2011, 02:27 pm
Respuesta #7

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Creo que el error está en los 7000000 siete millones, en realidad serían 70000000, setenta millones de dígitos

donde las sucesiones irían desde el 0000000 hasta el 9999999, son de 7 dígitos cada una y en total son 10000000 diez millones por siete dígitos son setenta millones de dígitos.

De ser así, ya lo tengo.

Déjenme respirar un poco, que enseguida lo subo. :P

Saludos.

Eram quod es, eris quod sum.

27 Enero, 2011, 05:12 pm
Respuesta #8

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

Sea

\(
\\A_0=0000000\\
\vdots\\
A_i=i\\
\vdots\\
A_{9999999}=9999999
 \)

Definimos

\( t=10^7-1 \)  Corregido
Gracias Pepito por la observación.

\( X=\{i\in\mathbb{N}:0\leq i\leq t\} \)

\( \varphi:X\longrightarrow X \), una biyección

Si llamamos N al número que estamos estudiando, se tiene

\( N=\displaystyle\sum_{i=0}^tA_{\varphi(i)}\left(10^7\right)^i \)

Como
\( 10^7\equiv 1\mod 239 \)

Podemos escribir

\(
\begin{eqnarray}
N&\equiv& \displaystyle\sum_{i=0}^tA_{\varphi(i)}\mod 239\\
&\equiv& \displaystyle\sum_{i=0}^tA_i\mod 239\\
&\equiv& \displaystyle\sum_{i=1}^tA_i\mod 239
\end{eqnarray}
 \)

Pero la suma en (3) tiene \( t  \) sumandos y sabenos que
\( t\equiv 0 \mod 239  \) es decir podemos escribir
\(  t=239k \)

Además como los restos se repiten cada 239 términos, podemos escribir

\(
\setcounter{equation}{3}
\begin{eqnarray}
N &\equiv & k\displaystyle\sum_{i=1}^{239}A_i \mod 239\\
&\equiv & k \dfrac{239\times 240}{2}\mod 239\\
&\equiv & k 239\times 120\mod 239\\
&\equiv & 0 \mod 239
\end{eqnarray}
 \)


Saludos.

Eram quod es, eris quod sum.

27 Enero, 2011, 10:32 pm
Respuesta #9

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Ya te entendí... es otra forma de verlo, sí. Tenés una errata nomás, tendría que ser \( t=10^7-1 \).

Pero sigo pensando que (lo que interpreté de) la solución de jgonzalez también está bien. Hasta tu paso \( (2) \) estamos todos de acuerdo. Lo que él dice es que en ese punto, uno puede asociar a cada \( A_i \) con \( 9.999.999-A_i \), y lo que va a obtener es el número \( 9.999.999 \) sumado una cantidad de veces que no importa cuál es (es \( \frac 12 \cdot 10^7 \)), porque \( 239 \) divide a \( 9.999.999 \).

Su explicación deja mucho que desear, pero la idea es buena.
"...parecido pero nada que ver"