domingo, 9 de enero de 2011

2010 cartas

Fase local de Cataluña de la XLVII Olimpiada Matemática Española, 2010/11

Tenemos 2010 cartas numeradas de 1 a 2010.

Demuestra que si tomamos 11 cartas cualquiera, hay entre esas 11 dos (numeradas i y j), que cumplen la condición i < j ≤ 2i.

Solución

4 comentarios:

David dijo...

Como me resulta más sencillo demostrar que es imposible incumplir la condición con 11 cartas de entre 2010 consecutivas, voy a reducirlo al absurdo:

Para que no se cumpla la condición cada nueva carta debería ser más que el doble de la anterior, así 2i sería menor que j y no cumpliría el enunciado.

Comenzando por uno, la carta menor que infringe el enunciado debería ser 3 (el doble más uno), el siguiente número sería el 7, etc...:

1+1+1=3
3+3+1=7
7+7+1=15
15+15+1=31
...

Ahora debemos hallar la relación entre el resultado y la cantidad de cartas.

Como la condición implica “el doble”, buscaré una relación en base 2

n=1; 1+1+1=3 2^2-1=3
n=2; 3+3+1=7 2^3-1=7
n=3; 7+7+1=15 2^4-1=15
n=4; 15+15+1=31 2^5-1=31
---

Es un crecimiento exponencial que responde a la formula: x=2^(n+1)-1

Aplicamos para n=11
x=2^(11+1)-1=2^12-1=4096-1=4095

Como no disponemos más que de 2010 cartas es imposible incumplir el enunciado por lo que demostramos su veracidad.

Proble Mático dijo...

La idea es correcta, pero creo que no has contado la primera carta. En realidad bastaría que hubiese 2047 cartas para que sí se pudiese escoger una colección de 11 cartas 1, 3, 7, 15,...

David dijo...

Es verdad, me he liado yo solo n=1 es la segunda carta, por lo que la undécima sería n=10

Como así se simplifica la fórmula:
x = 2^(n+1-1)-1 = 2^n-1

Aplicamos para verificar el rsultado:
2^11-1 = 2048-1 = 2047

Bruno dijo...

Separo los numeros en los siguientes 10 conjuntos

(1,2)
(3,4,5,6)
(7,8...,13,14)
(15,16,...,29,30)
(31,32,...,60,61)
(62,63,...,123,124)
(125,126,...,249,250)
(251,252,...,500,501)
(502,503...,1003,1004)
(1005,1006,...,2009,2010)

Se puede comprobar que si elijo dos numeros del mismo conjuntos se cumple la propiedad. y como tengo que elegir 11 numeros y tengo 10 conjunto por el principio de dirichet tendre que elegir al menos del mismo grupo. Entonces se demuestra lo pedido