2010 cartas

Enunciado

El truco lo desvela David en los comentarios. Supongamos que queremos escoger 11 cartas con la propiedad contraria a la citada, es decir, que no sea posible encontrar dos i, j, que cumplan la desigualdad i < j ≤ 2i.

Cuando tengamos esas 11 cartas, pensemos en la menor de ellas. Su valor es al menos 1. Por lo tanto, la segunda debe ser mayor que 2, porque si no no se cumpliría la propiedad. Luego debe ser al menos 3. Por lo tanto, la tercera debe ser mayor o igual que 7 (= 2³ - 1), por la misma razón, la cuarta mayor o igual que 15 (= 2⁴ - 1).

Puesto que la siguiente carta a una que es mayor o igual que 2ⁿ - 1 debe ser mayor que el doble, que es 2^{n + 1} - 2, su valor debe ser mayor o igual que 2^{n + 1} - 1, por lo que vemos que el valor de la que ocupa la posición 11 debe ser al menos 2¹¹ - 1, lo que supone 2047.

Evidentemente, es imposible seleccionar una carta mayor que 2011, según el enunciado, con lo que queda demostrado el problema.