IMO 2012 en Mar del Plata – Problema nº 6 - Gaussianos

Hay nuevos comentarios sin leer

IMO 2012 en Mar del Plata – Problema nº 6

Autor: ^DiAmOnD^ | Publicado el 28 de agosto de 2012
Categorías: Juegos | Imprime este post

60 comentarios

Trackback | 28 ago, 2012

Bitacoras.com
Juanjo Escribano | 29 de agosto de 2012 | 08:47

Vótalo 0
Se ve una solución en N=2 y a1=a2=1
Juanjo Escribano | 29 de agosto de 2012 | 08:55

Vótalo 0
Se ven fácilmente dos soluciones en N=1 y a1=0 y en N=2 y a1=a2=1
Juanjo Escribano | 29 de agosto de 2012 | 09:57

Vótalo 0
Tomo b(n) = max(a(i))- a(n) y multiplico la parte de los doses por 2^(max(a(i))) y me queda

2^b1 +2^b2+…+2^bn= 2^max(a(i))

Dado que el segundo término es par y que en el primero existe por construcción un bi=0, con lo que 2^bi = 1, concluyo que para el ai máximo, tiene que haber un número de repeticiones par, dado que sino el término de la izquierda sería impar.

Para N = 3 y para la parte de la izquierda se deduce que el único caso posible es el conjunto {1,2,2} que en sus tres posibles órdenaciones no cumplen la ecuación de los treses

Para N = 4 las posibles soluciones son {1,2,3,3} y {2,2,2,2} que tampoco son solución en la parte de los treses
Juanjo Escribano | 31 de agosto de 2012 | 08:59

Vótalo 0
Vos a demostrar que si para un n > 1, existe un a(i) = n-1 el conjunto de a (i) es de la forma
N={1,2,3,…,n-2,n-1,n-1} cuya suma es 1 en la fórmula de los doses.

Se cumple para 2 y para 3

Si se cumple para n, en n+1 ya hemos demostrado que si hay algun a(i) = n + 1 su cantidad es par.

Sea A={a(1),…a(n+1)} donde algun a(i)=n, por lo ya demostrado habrá un j / a(j) = n.

Construyo el conjunto B ={a(1),…,a(i-1),a(i+1),…,a(j-1),a(j+1),..,a(n+1),”n-1″}, por hipótesis es de la forma N y su forma única (dado que el “n-1″ añadido pertenece al conjunto) es:

B={1,2,…,n-2,n-1,”n-1″}. Su sumatorio de doses sigue siendo 1 por construcción

A B le quito el “n-1″ que había añadido i añado a(i) = n y a(j) =n y queda demostrado.

Para este tipo de conjuntos, a(i) = 1 solo se cumple para i € {1,2} dado que sino la suma de treses será mayor que 1.

Bueno, a ver si alguien se anima y aporta algo, que por ahora estoy triste en mi soledad
Juanjo Escribano | 31 de agosto de 2012 | 09:27

Vótalo 0
Con el mismo método que en el comentario anterior se demuestra que el conjunto de soluciones debe pertenecer al conjunto {1,2,…,n-1}
Cristhian Camacho | 31 de agosto de 2012 | 19:41

Vótalo 0
Haciendo operaciones queda:

$\cfrac{ 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{1} } } + 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{2} } } + \cdots + 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{n} } } } { 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) } } = 1$

$\cfrac{ 1 \cdot 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{1} } } + 2 \cdot 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{2} } } + \cdots + n \cdot 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) \displaystyle{ -a_{n} } } } { 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) } } = 1$

Entonces

$\displaystyle{ \sum_{j=1}^{n} } 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) - \displaystyle{ a_{j} } } = 2^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) } \quad \quad \quad (I)$

$\displaystyle{ \sum_{j=1}^{n} } j \cdot 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) - \displaystyle{ a_{j} } } = 3^{ \left ( \displaystyle{ \sum_{i=1}^{n} } a_{i} \right ) } \quad \quad \quad (II)$

Ahora con $a_{i}=k$ con $k$ constante,

En $(I)$ queda

$n \cdot 2^{n\cdot k - k} = 2^{n\cdot k}$

$n \cdot 2^{k(n-1)} = 2^{n\cdot k}$

Entonces $n=2^{k}$

En $(II)$ queda

$\displaystyle{ \sum_{j=1}^{n} } j \cdot 3 ^{k(n-1)} = 3^{k\cdot n}$

$\cfrac{n(n+1)}{2} \cdot 3 ^{k(n-1)} = 3^{k\cdot n}$

$\cfrac{n(n+1)}{2} = 3^{k}$

$n^{2}+n-2 \cdot 3^{k} = 0$

$n_{1,2} = \cfrac{-1\pm \sqrt{1^{2} - 4 \cdot (- 2 \cdot 3^{k} )}}{2} = \cfrac{-1\pm \sqrt{1 + 8 \cdot 3^{k}}}{2}$

con $k=1$ , $n_{1}=2$ , $n_{2}=-3$ (no sirve)

Finalmente, hasta aquí se cumple la igualdad propuesta para los valores: $n=2$ y $a_{1}=1$ , $a_{2}=1$

Falta verificar con valores de $a_{i}$ distintos y con $a_{i}=f(i)=\mbox{funci\'on de i}$
Cristhian Camacho | 31 de agosto de 2012 | 23:11

Vótalo 0
Como dice Juanjo Escribano en su segundo comentario aparentemente los valores $n$ pueden ser 2,
$n=1$ y $a_{1}=0$ y $n=2$ y $a_{1}=a_{2}=1$

Por ejemplo:

para $a_{j}=j$

$\displaystyle{ \sum_{j=1}^{n} } \cfrac{j}{3^{j}}$

Deberia ser igual a $1$

$\displaystyle{ \sum_{j=1}^{n} } \cfrac{j}{3^{j}}$

$\displaystyle{ \sum_{j=1}^{n} } \cfrac{j}{3^{j}} = \cfrac{3^{n+1}-(n+1)\cdot 3 + n }{ 3^{n} \cdot (3-1)^{2} }$

Luego

$\cfrac{3^{n+1}-(n+1)\cdot 3 + n }{ 3^{n} \cdot 2^{2} } = 1$

Entonces

$3^{n+1}-(n+1)\cdot 3 + n = 3^{n} \cdot 4$

$3 \cdot 3^{n}-(n+1)\cdot 3 + n = 4 \cdot 3^{n}$

$3^{n}+(n+1)\cdot 3 - n = 0$

Ahora no hay valores de $n$ enteros positivos que cumplan con esa igualdad, por lo tanto $a_{j}=j$ no nos sirve para verificar la igualdad propuesta
Mmonchi | 1 de septiembre de 2012 | 10:33

Vótalo 0
Otra solución es N=6: {2,2,3,3,3,3}
Mmonchi | 1 de septiembre de 2012 | 10:42

Vótalo 0
Otra es N=10: {4,3,4,4,3,3,4,4,4,4}
Mmonchi | 1 de septiembre de 2012 | 10:45

Vótalo 0
La última no es válida…
Mmonchi | 1 de septiembre de 2012 | 10:51

Vótalo 0
Esta sí: N=10 {2,3,3,3,4,4,4,4,4,4}
Mmonchi | 1 de septiembre de 2012 | 11:38

Vótalo 0
No son soluciones los N del tipo 4k+3 y 4k+4.

La suma de los numeradores, si hacemos común denominador, debe ser impar, concretamente una potencia de 3, por el segundo término. Los numeradores son números consecutivos que alternan pares e impares: esto no varía al multiplicarlos por potencias de 3. La suma de números con paridad alterna va dando pares e impares de dos en dos, como es fácil ver en la serie de los números triangulares. Esto nos permite descartar la mitad de las posibles soluciones y quedarnos solo con las del tipo N=4k+1 y N=4k+2.
Mmonchi | 1 de septiembre de 2012 | 12:10

Vótalo 0
Otra más: N=13 {2,3,3,4,4,5,4,4,4,4,5,5,5}
Mmonchi | 1 de septiembre de 2012 | 12:19

Vótalo 0
Para N=5: {2,2,2,3,3}
Y para N=9: {2,3,3,3,3,4,4,4,4}

Ahora que sé cómo buscarlas, creo que es posible encontrar soluciones para todo N=4k+1 y N=4k+2.

Aunque todavía estoy lejos de una demostración, creo que podría ser constructiva.
Mmonchi | 1 de septiembre de 2012 | 12:51

Vótalo 0
Los pasos para construir una solución son:

1. Tomar un valor de N del tipo 4k+1 o 4k+2.
2. Hallar la suma S de 1 a N.
3. Se define el mayor an como el menor que cumple S<3^an.
4. Se da el valor an a todos los ai.
5. Se disminuyen los ai de forma ordenada para conseguir que el primer término (de potencias de 2) sume 1. Primero se van disminuyendo hasta conseguir que el resultado sea mayor que 1 y después se aumentan y disminuyen hasta conseguir el 1.
6. Cuando se tiene una solución para el primer término se busca la del segundo. Se alternan los valores de ai para acercarnos progresivamente al valor buscado -1- en el segundo término.

Faltaría demostrar que siempre se encuentra una solución que sume 1 en el paso 5 y que siempre se puede transformar en una solución válida en el paso 6.
Mmonchi | 1 de septiembre de 2012 | 12:54

Vótalo 0
Ejemplo con N=14

S=105.
El an máximo es 5, pues 3^4=81 y 3^5=243 que ya es mayor que 105.
Al hacer los ai=5 la suma es 0,4375.
Voy reemplazando los 5 por 4, pero no alcanzo una solución ya que la suma al reemplazarlos todos es 0,875.
Las soluciones con ai=3 me dan valores de la suma del segundo témino mayores que 1 que no permiten aplicar el paso 6. Por ejemplo, {3,3,3,3,3,3,5,5,5,5,5,5,5,5} suma 1,12345679.
Al empezar por 2 encuentro soluciones válidas, como {2,3,3,4,4,4,4,4,5,5,5,5,5,5} o {2,3,3,3,4,4,5,5,5,5,5,5,5,5} cuyo primer término suma 1 y el segundo menos que 1.
Reordenando las soluciones la suma del primer término no varía y la del segundo aumenta lo suficientemente despacio como para alcanzar el valor 1. Con los dos ejemplos anteriores, {2,4,3,3,4,4,4,4,5,5,5,5,5,5} y {2,3,4,3,3,5,5,5,4,5,5,5,5,5}.

Parece evidente que siempre habrá soluciones mediante este proceso, pero falta una demostración rigurosa.
Juanjo Escribano | 3 de septiembre de 2012 | 09:38

Vótalo 0
En orden a buscar posibles soluciones, doy una pista de las sumas de treses.

Sigo centrado en soluciones para los doses del tipo {1,2,…,n-2,n-1,n-1} pero parte del razonamiento puede valer para el caso general.

Sumo los términos de exponente n-1 en los treses, y si son los elementos i,j, para poder reducir el denominador i/3^(n-1)+j/3^(n-1)=(i+j)/3^(n-1) deducimos que i+j = múltiplo de 3, que no puede ser el 3, pues sería i,j€{1,2} y no podria poner el elemento de exponente 1 (que ya he demostrado que es el 1 o el 2).

Tras esto, el elemento k de exponente n-2 tiene que ser múltiplo de 3.

Esto se puede aplicar parcialmente en el caso general
Juanjo Escribano | 3 de septiembre de 2012 | 09:51

Vótalo 0
Mmonchi

En el paso 5 que siempre hay solución es evidente. Por lo menos la que he dado yo. {1,2,…,n-2,n-1,n-1}
Mmonchi | 3 de septiembre de 2012 | 11:11

Vótalo 0
Llevas toda la razón, Juanjo, descartaba esas soluciones porque me obligaban a trabajar con números muy “grandes”. Pero también sirven, por ejemplo, para N=14, a partir de la solución de “doses” {1,2,3,4,5,6,7,8,9,10,11,12,13,13} se llega a la solución de “treses” {2,1,4,3,6,5,8,7,10,9,11,12,13,13}.

Ahora solo falta demostrar que siempre se puede reordenar tu solución para obtener una que valga con las potencias de 3.
Mmonchi | 3 de septiembre de 2012 | 11:25

Vótalo 0
Las soluciones son fáciles de encontrar: N=1 {1}, N=2 {1,1}, N=5 {2,1,3,4,4}, N=6 {2,1,3,5,5,4}, N=9 {2,1,4,3,5,8,7,6,8}, N=10 {2,1,4,3,6,5,7,9,8,9}, N=11 {2,1,4,3,6,5,8,7,9,11,12,10,12}…

Parecen seguir un patrón, si es así ya estaría la demostración terminada.
Juanjo Escribano | 3 de septiembre de 2012 | 12:44

Vótalo 0
Mmonchi,

si parece haberla pero no veo como hacerlo de manera formal.

En cuanto al apartado 5 a demostrar, siempre existe solución (y en general mas de una) si partimos de mi solución para 3 {1,2,2} en cada paso cojes cualquier Nº y lo eliminas, sustituyendolo por dos iguales con valor Nº+1.

Para 4, p.e. {2,2,2,2}, o {1,3,3,2} o {1,2,3,3}

cojo el 2 caso, y para 5

{2,2,3,3,2}, {1,4,4,3,2},{1,3,4,4,2},{1,3,3,3,3}
Juanjo Escribano | 3 de septiembre de 2012 | 13:25

Vótalo 0
Mmonchi, la última serie es N13 ¿no?
Juanjo Escribano | 3 de septiembre de 2012 | 14:50

Vótalo 0
La frase:

Tras esto, el elemento k de exponente n-2 tiene que ser múltiplo de 3.

es un error
Juanjo Escribano | 4 de septiembre de 2012 | 09:23

Vótalo 0
La ventaja que le veo a las construcciones que propongo es que son “mas constructivas” y posiblemente encontremos la recurrencia.

Estoy mirando que para conjuntos de n=4k+1 elementos la solución sea fijando n-5 elementos {2,1,4,3,6,5,…} y reordenar n-4,n-3-n-2,n-1,n-1

y para conjuntos de n=4k+2 lo mismo con los 4 últimos.

Si tenemos en cuenta que i+j es múltiplo de 3 para n-1, son pocos casos a revisar
Juanjo Escribano | 4 de septiembre de 2012 | 09:57

Vótalo 0
La ventaja que le veo a las construcciones que propongo es que son “mas constructivas” y posiblemente encontremos la recurrencia.

Estoy mirando que para conjuntos de n=4k+1 elementos la solución sea fijando n-5 elementos {2,1,4,3,6,5,…} y reordenar n-4,n-3-n-2,n-1,n-1

y para conjuntos de n=4k+2 lo mismo con los 4 últimos.

Si tenemos en cuenta que i+j es múltiplo de 3 para n-1, son pocos casos a revisar

Posiblemente la repetición se produzca cada 12 elementos (4*)
Juanjo Escribano | 4 de septiembre de 2012 | 11:38

Vótalo 0
Respecto al descarte, creo que siguiendo to idea, las sumas de los numeradores módulo 3 es :
1,0,0,1,0,0,1,0,0,…. con lo que serían posibles soluciones 3k y 3k+2
Juanjo Escribano | 4 de septiembre de 2012 | 11:52

Vótalo 0
Respecto al descarte, creo que siguiendo tu idea, las sumas de los numeradores módulo 3 es :
1,0,0,1,0,0,1,0,0,…. con lo que serían posibles soluciones 3k y 3k+2

Para N=5, {2,1,3,4,4} cumple (si no me he equivocado)
Juanjo Escribano | 4 de septiembre de 2012 | 12:06

Vótalo 0
Pero la realidad es mas cabezona, y creo que los dos estamos equivocados en como reducir los casos (N10 = 3k+1 destroza mi teoria). La única condición segura es que la suma de numeradores del conjunto de a(i) mas grande es múltiplo de 2
Juanjo Escribano | 4 de septiembre de 2012 | 12:08

Vótalo 0
multiplo de 3 obviamente
Juanjo Escribano | 4 de septiembre de 2012 | 14:16

Vótalo 0
Mmonchy, lo tuyo está bien. Es una restriccón válida. La mía no.
Ratoncillo de biblioteca | 4 de septiembre de 2012 | 16:10

Vótalo 0
Hola.

Sé como probar que los posibles $n$ válidos son de la forma $4k+1$ ó $4k+2$ y también que si un $n$ de la forma $4k+1$ es solución entonces también es solución $4k+2$ . Por tanto sólo quedaría probar que los $n$ de la forma $4k+1$ son solución.

También he visto que si consideramos la sucesión $a_n$ como una función $a:\{1,2,\dots,n\}\longrightarrow\mathbb{N}\cup\{0\}$ y $m$ es su máximo entonces $a^{-1}\left(\{m\}\right)$ tiene un número par de elementos y que si los sumamos el resultado debe ser un múltiplo de tres.

No se si incluir hasta donde he llegado por si quereis seguir pensando…
Mmonchi | 4 de septiembre de 2012 | 19:42

Vótalo 0
Juanjo, sí, era N=13. Profundizando en tu idea he llegado a algunas conclusiones:

Si tenemos una solución {1,2,3,…,N-3,N-2,N-1,N-1} de la primera fracción, podemos construir la siguiente solución (no válida) de la segunda fracción: {2,1,4,3,…,N-1}. Es decir, ai=i+1 para i impar y ai=i-1 para i par, excepto el último término si N=2q+1 y los dos últimos si N=2q+2. Es fácil comprobar que la solución tiende a 1 cuando se reemplazan los ai por las potencias de 3 en la segunda fracción, así que vamos a evaluar el error cometido y a buscar la forma de solucionarlo.

Tenemos la segunda fracción de la forma 1/3^2 + 2/3^1 + 3/3^4 +4/3^3+ … + N/3^(N-1). Como el MCM es 3^N-1 lo transformamos en una sola fracción: (1*3^(N-3) + 2*3^(N-2) + 3*3^(N-5) + 4*3^(N-4) + … + N*3^0) / 3^(N-1). El error cometido para que esta fracción valga 1 es la diferencia entre el numerador y el denominador, que vale –q tanto para N=2q+1 como para N=2q+2. Al intercambiar dos ai modificamos el error siempre en una cantidad par, por tanto podemos corregir ese error cuando q es par, pero no cuando q es impar, así que podemos hallar soluciones para todos los N del tipo 4k+1 o 4k+2 como ya sabíamos.

¿Cómo se corrige ese error? En eso ando precisamente . Ratoncillo de biblioteca, si puedes hallar una solución para N=4k+2 a partir de la de N=4k+1 el problema se reduce a la mitad.

Cuando tenga un rato libre sigo, si me dejáis algo.
Juanjo Escribano | 5 de septiembre de 2012 | 09:01

Vótalo 0
MMonchi
Justamente iba a colgar un resultado similar, pero sin deducción (calculada para varios casos)

O no te entiendo o te has confundido, pero la diferencia -q se produce (obviamente) en un solo valor (no puede ser igual en 2q+1 y 2q+2.
Yo veo:

2 2
4 3
6 4
8 5
10 6
12 7
14 8
…

Eso me ha permitido encontrar fácilmente la solución N18 con muy poco cálculo

Coloco en la fila superior los numeradores e iré calculando en la inferior los denominadores.

Empiezo fijando 14 números
15 16 17 18, y para explonente 17 (suma múltiplo de 3) tengo dos posibilidades 15,18 y 16,17

15 16 17 18 15 16 17 18
17 17 17 17
Caso 1º, los numeradores suman 33, divido por 3 y me queda 11/16. Para este nivel me obliga al 16 para que sea múltiple de 3

15 16 17 18
17 16 17. 11+16 = 27 = 9/15, que no se puede reducir con 17

15 16 17 18
17 17
Para 17 33=11/16 y no se puede reducir

Tomo 6 números

13 14 15 16 17 18 y sigo el mismo procedimiento

Para 17 y múltiplo 3 tengo las siguientes posibilidades: 13,17 14,16 15,18

La 1ª la dejo para mas tarde pues en lo que hemos visto sería 13 posiblemente el denominador 1 cojo 14,16

13 14 15 16 17 18
17 17 Suma 30=10/16 y me obliga a cojer el 17

13 14 15 16 17 18
17 17 16 Suma 27=9/15, ahora me valen 15 y 18. Escojo el 18 pues la suma es múltiplo de 9 y me da buena espina, pues así pillaré luego el 15.

13 14 15 16 17 18
17 17 16 15 Suma 27=9/14 y pillo único el 15

13 14 15 16 17 18
17 14 17 16 15 Suma 24=8/13, pongo el 13

13 14 15 16 17 18
13 17 14 17 16 15 Suma 21=7/12 que es la diferencia correspondiente a 12 y sin más cálculo es OK

{2,1,4,3,6,5,8,7,10,9,12,11,13,17,14,17,16,15}
Juanjo Escribano | 5 de septiembre de 2012 | 09:16

Vótalo 0
Siguiendo el mismo procedimiento

N17={2,1,4,3,6,5,8,7,10,9,12,11,13,16.14.16.15}}
Juanjo Escribano | 5 de septiembre de 2012 | 09:25

Vótalo 0
Para Ratoncillo y Mmonchi

Además de simplificar al caso 4k+1 podremos intentar ordenar solo casos de 5 números
Juanjo Escribano | 5 de septiembre de 2012 | 09:34

Vótalo 0
Mmonchi

Ahora te he entendido y es lo que yo había deducido sin demostración.

Mi serie

2 2
4 3
6 4

quiere decir que la diferencia si sumo {2,4,6} elementos primeros es {2,3,4} y así sucesivamente.

Creo que en la terminología has puesto 2q+2 y es 2q-2
Juanjo Escribano | 5 de septiembre de 2012 | 10:52

Vótalo 0
N22={2,1,..,16,15,17,21,18,20,21,19}

pero N21 no me sale con 5 Nºs ordenados
Juanjo Escribano | 5 de septiembre de 2012 | 11:12

Vótalo 0
N26={2,1,…,20,19,21,23,25,22,25,24}

Pero no veo ninguna lógica y las permutaciones de 6 con 2 repetidos son 360.

Agrupo soluciones encontradas con el desarrollo {1,2,..,n-2,n-1,n-1}

N=1.. {1}
N=5.. {2,1,3,4,4}
N=9.. {2,1,4,3,5,8,7,6,8}
N=13 {2,1,4,3,6,5,8,7,9,11,12,10,12}
N=17{2,1,4,3,6,5,8,7,10,9,12,11,13,16.14.16.15}

N=2.. {1,1}
N=6.. {2,1,3,5,5,4}
N=10 {2,1,4,3,6,5,7,9,8,9}
N=14 {2,1,4,3,6,5,8,7,10,9,11,12,13,13}
N=18 {2,1,4,3,6,5,8,7,10,9,12,11,13,17,14,17,16,15}
N=22 {2,1,..,16,15,17,21,18,20,21,19}
Juanjo Escribano | 5 de septiembre de 2012 | 12:26

Vótalo 0
Voy a intertar demostrar que la forma N=14 no se repite mas:

Sumo los dos últimos elementos y aplico las divisiones por 3:

(n-1)+n=3a con a €N
(n-2)+a=3b
(n-3)+b=3c
y c=(n/2)-1 por los residuos que hemos visto previamente

4 ecuaciones con 4 incognitas cuya solución es:

a=9
b=7
c=6
n=14

Habría que revisar esto para las 12 variantes de 4 cifras con 2 repetidas, pero la pinta es mala, pues para cada forma tendremos 4 ecuaciones con 4 incógnitas.

Si pasamos a 6 nos pasará lo mismo (6 ecuaciones con 6 incognitas) y 360 formas y así sucesivamente.

Además algunos de estos casos podrá no tener solución
Mmonchi | 5 de septiembre de 2012 | 13:35

Vótalo 0
Juanjo, he puesto 2q+1 y 2q+2 porque en los casos 1 y 2 el error es 0, en los casos 5 y 6 es -2, en los casos 9 y 10 es -4, en 13 y 14 es -6, etc. Como el error es creciente el número de términos que hay que reordenar también crecerá, me parece inevitable. Habrá excepciones, por ejemplo, si intercambiamos los términos de las posiciones N-4 y N-3 el error disminuye en 18, así que los casos N=37 y N=38 se solucionan intercambiando esos dos términos. (No lo he comprobado) Lo mismo debe ocurrir con N=325 y N=326 pues si intercambiamos solo los términos de las posiciones N-6 y N-5 el error disminuye en 162, que es el valor que se tiene en esos casos.

Estoy tratando de ver cuánto disminuye el error con intercambios dobles, triples y múltiples en general, ya que si obtengo todos los números pares positivos ya estaría demostrado y habría una forma de construir la solución. Aunque el número de intercambios para conseguir todos los pares será cada vez mayor.

Ratoncillo, ya he visto como solucionar 4k+2 a partir de 4k+1, de hecho lo he aplicado en el ejemplo anterior para N=37 y N=38
Juanjo Escribano | 5 de septiembre de 2012 | 14:25

Vótalo 0
Podeis poner por favor la construcción de 4k+2 si hay solución de 4k+1, pues nos dejaría el campo al 50% y yo no lo veo.

Mmonchi, no he entendido el paso final del residuo, donde de la ecuación pasas a que falta q (ya he comentado que lo había descubierto, pero no de manera formal) y ojo hay que solucionar los impares (4k+1)=>4k+2 y no habeis dicho nada de la inveresa)
Juanjo Escribano | 10 de septiembre de 2012 | 10:41

Vótalo 0
La parte del residuo he conseguido demostrarla por inducción completa.

decímos que el residuo es r(p) al valor r/3^2P

para p = 1 {2,1,…..} y r(p)= 1-(1/3^2+2/3^1)) = 1-7/9=2/9, luego r(1)=2=p+1

Ahora si se cumple para un p,

tenemos que para el conjunto {2,1,4,3,…,2p,2p-1} el residuo es p+1

Para calcular el residuo de r(p +1) = 1 – (2/3^1+1/3^2+…+2p/3^(2p-1)+(2p-1)/3^2p+(2p+2)/3^(2p+1)+(2p+1)/3^(2p+2) = r(p)+(2p+2)/3^(2p+1)+(2p+1)/3^(2p+2)=
(p+1)/3^2p+(2p+2)/3^(2p+1)+(2p+1)/3^(2p+2)= (9(p+1)-3(2p+2)-(2p+1))/3^(2p+2)=(p+6)/3^(2p+2)
(9p+9-6p-6-2p-1)/3^(2p+2)=(p+2)/3^(2p+2) como queríamos demostrar
Juanjo Escribano | 10 de septiembre de 2012 | 10:43

Vótalo 0
Mmonchi,

la suma de los numeradores no tiene por que ser impar, 1,2,3 suma 6 y es multiplo de 3
Juanjo Escribano | 10 de septiembre de 2012 | 10:49

Vótalo 0
n=8 {2,1,5,7,6,3,4,7}
Juanjo Escribano | 10 de septiembre de 2012 | 11:02

Vótalo 0
Mi solución del 8 es errónea (residuo 3 en vez de 2)
Ratoncillo de biblioteca | 10 de septiembre de 2012 | 17:14

Vótalo 0
El caso $4k+1$ se obtiene probando que si el resultado es cierto para $4k+1$ entonces es cierto para $4(k+3)+1$ y teniendo en cuenta que para $1,5,9$ el resultado es cierto. Ando bastante liado con el trabajo, pero si tengo hueco incluyo la solución.
Mmonchi | 14 de septiembre de 2012 | 23:47

Vótalo 0
Hola, he estado analizando las posibles soluciones para buscar un patrón que me diera una solución general, como la de Juanjo para las potencias de 2. Primero busqué todas las soluciones posibles:

N=1 {1}
N=2 {1,1}
N=5 {2,1,3,4,4} {2,2,2,3,3}
N=6 {2,1,3,5,5,4} {2,1,4,4,4,4} {2,2,2,4,4,3} {2,2,3,3,3,3}

Con N=9 hay 130 soluciones, de {1,2,5,8,7,6,4,8,3} a {2,3,3,3,3,4,4,4,4}. Con N=10, 524, de {1,2,4,8,5,7,9,9,6,3} a {2,3,3,3,4,4,4,4,4,4}. Con N=13 51906, de {1,2,4,5,7,9,12,8,11,3,12,6,10} a {3,2,3,3,4,4,4,5,5,5,5,5,5}. Eran demasiadas soluciones para poder analizarlas, así que probé a buscar soluciones “crecientes”, es decir, aquellas en las que Ai+1 >= Ai. Las únicas soluciones de este tipo hasta N=20 son {1} {1,1} {2,2,2,3,3} {2,2,3,3,3,3} {2,3,3,3,3,4,4,4,4} y {2,3,3,3,4,4,4,4,4,4}, lo que me ha llevado a otro callejón sin salida. Y hasta aquí he llegado.

Juanjo, tu forma de calcular el residuo es más elegante que la mía. Yo calculaba la suma de una serie infinita, tanto para 4k+1 como para 4k+2, de los términos no truncados al elegir los términos ai= 2,1,4,3,6,5,… y así llegaba al valor, pero de una forma bastante engorrosa.

Ratoncillo de biblioteca, si puedes demostrar 4(k+3)+1 (es decir, 4k+13) a partir de 4k+1, ya estaría terminado.
Ratoncillo de biblioteca | 16 de septiembre de 2012 | 14:49

Vótalo 0
(1) Veamos que $4k+1$ implica $4k+2$ .

Observemos que:

${\displaystyle\begin{cases} \cfrac{1}{2^{a_{2k+1}}}=\cfrac{1}{2^{a_{2k+1}+1}}+\cfrac{1}{2^{a_{2k+1}+1}}\vspace*{0.5cm}\\ \cfrac{2k+1}{3^{a_{2k+1}}}=\cfrac{2k+1}{3^{a_{2k+1}+1}}+\cfrac{4k+2}{3^{a_{2k+1}+1}} \end{cases}}$

Por tanto, a partir de la sucesión de partida $a_1,a_2,\dots,a_{4k+1}$ podemos construir la nueva sucesión

$a_1,a_2,\dots,a_{2k},\pmb{a_{2k+1}+1},a_{2k+2},\dots,a_{4k+1},\pmb{a_{2k+1}+1}$

que hace que el resultado sea cierto para $4k+2$

(2) Veamos que $4k+1$ implica $4(k+3)+1=4k+13$ .
Esto probará el caso $4k+1$ , ya que el resultado es cierto para

$\begin{cases}4\cdot 0 +1=1 \\ 4\cdot 1+1=5 \\ 4\cdot 2+1=9\end{cases}$

Por el apartado (1) basta probar que $4k+2$ implica $4k+13$ .

Para los pares: $4k+4, \ 4k+6, \ 4k+8, \ 4k+10, \ 4k+12$ aplicamos la misma técnica que en el apartado (1):

${\displaystyle\begin{cases} \cfrac{1}{2^{a_{2k+2}}}=\cfrac{1}{2^{a_{2k+2}+1}}+\cfrac{1}{2^{a_{2k+2}+1}}\vspace*{0.5cm}\\ \cfrac{2k+2}{3^{a_{2k+2}}}=\cfrac{2k+2}{3^{a_{2k+2}+1}}+\cfrac{4k+4}{3^{a_{2k+2}+1}} \end{cases} \quad \begin{cases} \cfrac{1}{2^{a_{2k+3}}}=\cfrac{1}{2^{a_{2k+3}+1}}+\cfrac{1}{2^{a_{2k+3}+1}}\vspace*{0.5cm}\\ \cfrac{2k+3}{3^{a_{2k+3}}}=\cfrac{2k+3}{3^{a_{2k+3}+1}}+\cfrac{4k+6}{3^{a_{2k+3}+1}} \end{cases}}$

${\displaystyle\begin{cases} \cfrac{1}{2^{a_{2k+4}}}=\cfrac{1}{2^{a_{2k+4}+1}}+\cfrac{1}{2^{a_{2k+4}+1}}\vspace*{0.5cm}\\ \cfrac{2k+4}{3^{a_{2k+4}}}=\cfrac{2k+4}{3^{a_{2k+4}+1}}+\cfrac{4k+8}{3^{a_{2k+4}+1}} \end{cases} \quad \begin{cases} \cfrac{1}{2^{a_{2k+5}}}=\cfrac{1}{2^{a_{2k+5}+1}}+\cfrac{1}{2^{a_{2k+5}+1}}\vspace*{0.5cm}\\ \cfrac{2k+5}{3^{a_{2k+5}}}=\cfrac{2k+5}{3^{a_{2k+5}+1}}+\cfrac{4k+10}{3^{a_{2k+5}+1}} \end{cases}}$

${\displaystyle\begin{cases} \cfrac{1}{2^{a_{2k+6}}}=\cfrac{1}{2^{a_{2k+6}+1}}+\cfrac{1}{2^{a_{2k+6}+1}}\vspace*{0.5cm}\\ \cfrac{2k+6}{3^{a_{2k+6}}}=\cfrac{2k+6}{3^{a_{2k+6}+1}}+\cfrac{4k+12}{3^{a_{2k+6}+1}} \end{cases}}$

Ahora vamos con los impares: $4k+3, \ 4k+5, \ 4k+7, \ 4k+9, \ 4k+11, \ 4k+13$

Si los sumamos se obtiene:

$(4k+3) + (4k+5) + (4k+7) + (4k+9) + (4k+11) + (4k+13)=3(8k+16)$

Por otro lado,

$\cfrac{k+2}{3^{a_{k+2}}}=\cfrac{8k+16}{3^{a_{k+2}+2}}+\cfrac{k+2}{3^{a_{k+2}+2}}$

luego

$\cfrac{k+2}{3^{a_{k+2}}}=\left(\cfrac{4k+13}{3^{a_{k+2}+3}}+\cfrac{4k+11}{3^{a_{k+2}+3}}+\cfrac{4k+9}{3^{a_{k+2}+3}}+\cfrac{4k+7}{3^{a_{k+2}+3}}+\cfrac{4k+5}{3^{a_{k+2}+3}}+\cfrac{4k+3}{3^{a_{k+2}+3}}\right)+\cfrac{k+2}{3^{a_{k+2}+2}}$

y además

$\cfrac{1}{2^{a_{k+2}}}=\left(\cfrac{1}{2^{a_{k+2}+3}}+\cfrac{1}{2^{a_{k+2}+3}}+\cfrac{1}{2^{a_{k+2}+3}}+\cfrac{1}{2^{a_{k+2}+3}}+\cfrac{1}{2^{a_{k+2}+3}}+\cfrac{1}{2^{a_{k+2}+3}}\right)+\cfrac{1}{2^{a_{k+2}+2}}$

Por último se define la nueva sucesión:

$a_1, \dots,a_{k+1},\pmb{a_{k+2}+3},a_{k+3},\dots,a_{4k+2},\pmb{a_{k+2}+3},\pmb{a_{2k+2}+1},\pmb{a_{k+2}+3},\pmb{a_{2k+3}+1},\pmb{a_{k+2}+3},$

$\pmb{a_{2k+4}+1},\pmb{a_{k+2}+3},\pmb{a_{2k+5}+1},\pmb{a_{k+2}+3},\pmb{a_{2k+6}+1},\pmb{a_{k+2}+3}$
Mikita | 16 de septiembre de 2012 | 16:01

Vótalo 0
Muy bien redactado, Ratoncillo de biblioteca.
Juanjo Escribano | 17 de septiembre de 2012 | 09:10

Vótalo 0
No lo he revisado en detalle, pero en apariencia muy bueno
Mmonchi | 17 de septiembre de 2012 | 10:48

Vótalo 0
Qed.

Los que lo resolvieron en el IMO debían ser unos monstruos…
Juanjo Escribano | 21 de septiembre de 2012 | 09:47

Vótalo 0
Ratoncillo de biblioteca

Me ha gustado mucho tu explicación de 4k +1 => 4k +2 (y voy a desarrollarla un poco mas en otra entrada)

Estoy revisando la de 4k +1 => 4k +13 y creo que la linea que sigue es lo que yo llamo un hand error, que no invalida la demostración (que aun no he verificado).

Por el apartado (1) basta probar que 4k+2 implica 4k+13.

Creo que debe decir:

4k+1 implica 4k+13.
Ratoncillo de biblioteca | 21 de septiembre de 2012 | 09:56

Vótalo 0
Juanjo Escribano como queremos probar que $4k+1$ implica $4k+13$ y ya tenemos probado que $4k+1$ implica $4k+2$ , bastará probar entonces que $4k+2$ implica $4k+13$ .

Otra cosa: Al final al definir la sucesión que resuelve $4k+13$ hay una errata (copy/paste): el término $k+2$ -ésimo en lugar de ser $a_{k+2}+3$ es $a_{k+2}+2$ .

Gracias!
Juanjo Escribano | 21 de septiembre de 2012 | 10:58

Vótalo 0
Aunque parece que las únicas soluciones posibles sean 4k+1 y 4k+2, no me convenze el comentario de Mmonchi que concluye que esos dos son los únicos tipos de soluciones que existen. Quisiera encontrar una demostración mas fuerte.

Por otro lado (y aunque al final no servirá seguramente para nada) voy a demostrar basandome en el punto 1 de ratoncillo de biblioteca(RB en adelante) que si existe una solución para un impar 2n+1, existe solución para 2n+2 (si encontraramos alguna solución en 4k+3 implicaría una solución en 4k+4

Primero describo dos lemas que me han sugerido la solución de RB

Lema1: 1+1 = 2 que no voy a demostrar.
Lema2: 1+2 = 3 que no voy a demostrar.

Tomo el elemento a(i) de la sucesión, y lo voy a separar en dos nuevos elementos b1 y b2 = a(i) + 1 tales que su parte de doses y treses sumen lo mismo:

Para los doses:

1/2^a(i) = 2/2*2^a(i) = (1+1)/2^(a(i)+1) = lema 1 = 1/2^(a(i)+1) + 1/2^(a(i)+1) =
1/2^b1 + 1/2^b2

Para los treses:

i/3^a(i) = 3i/3*3^a(i) = (1+2)i/3^(a(i)+1) = lema 2 = i/3^(a(i)+1) + 2i/3^(a(i)+1) =
i/3^b1 + 2i/3^b2.

Una solución a ambas ecuaciones se produce cuando b1 se coloca en la posición i y b2 en la posición 2i

Por tanto si tengo una solución cualquiera de 2n+1 la descomposición del elemento n+1 en dos elementos a(n+1) +1 ubicados en las posiciones i=n+1 y 2i=2n+2 nos dá una solución para 2n+2

Por tanto esta es una ampliación de la demostración del punto 1 de RB para todos los impares.

Por último RB, entendido que 4k+2=>4k+13 es correcto (no he empezado a revisar ese apartado, pues tu solución del punto 1 me obligó a pensar en como lo habías hecho y desarrollar este divertimento)
Ratoncillo de biblioteca | 21 de septiembre de 2012 | 11:11

Vótalo 0
Es fácil probar que las únicas posibles soluciones son $4k+1$ ó $4k+2$ . Ahora mismo no tengo tiempo de incluirlo, pero básicamente ”quitar” denominadores en el segundo sumando (el de potencias de 3) y tomar clases módulo 2… Es cierto lo que dices, si el resultado es cierto para un par de la forma $2n+1$ también lo es para $2n+2$ . Pero sólo tiene sentido partir de impares de la forma $4k+1$ .
Mmonchi | 21 de septiembre de 2012 | 13:47

Vótalo 0
Demostración de que no puede haber soluciones del tipo 4k ni 4k+3:

Tenemos una suma de fracciones con denominador siempre impar y numeradores {1,2,3,4,5,…}. Los restos módulo 2 de los numeradores son {1,0,1,0,1,…} ya que alternan pares e impares. Podemos hallar un denominador común D que sea impar ya que todos eran impares. La paridad de los numeradores no varía, pues siempre se multiplican por un término impar. Como D es impar, para que la suma de las fracciones sea 1 debe cumplirse que la suma de los numeradores sea impar. En los casos N=1 y N=2 la suma es impar (1mod2=1 y (1+0)mod2=1) mientras que en los casos N=3 y N=4 es par ((1+0+1)mod2=0 y (1+0+1+0)mod2=0). Si hallo la paridad de N+4 tengo que Nmod2+(1+0+1+0)mod2=Nmod2+2mod2=Nmod2, es decir, la paridad de N+4 es la misma que la de N. Por tanto, como el numerador en los casos N=4k y N=4k+3 es par y el denominador es impar, la fracción nunca puede valer 1.
Juanjo Escribano | 21 de septiembre de 2012 | 14:16

Vótalo 0
OK Mmonchy (en la anterior entrada ya lo explicabas, pero no llegué ha entenderla en el sentido correcto, y eso me liaba. Ahora, y entendida la idea está claro.

Voy a revisar la 2ª parte de RB y si como intuyo es correcta, el problema queda cerrado (al menos para mí).
Juanjo Escribano | 21 de septiembre de 2012 | 14:21

Vótalo 0
Ratoncillo de biblioteca

Cierto tu comentario, pero me parecía divertido el descubrimiento de que la solución constructiva de 1 salía del simple concepto de 1+1=2 y 1+2=3 y era mas divertido si lo exponía como lemas de apoyo. En el fondo lo magnífico de tu solución, si la encontraste como la comentó, es que se basa en conceptos sencillos que desarrollados te permiten formularlos como si los sacarás por arte de magia y lo que hay por detrás es trabajo.
Juanjo Escribano | 21 de septiembre de 2012 | 14:50

Vótalo 0
RB

Revisado y entendido el punto 2, además se basa en el lema 3: 1+8=9.