Problema 1 de la Fase Nacional de la de la LV OME 2019
Se dirige a una edad de: 16-17 años

Un conjunto de números enteros T es orensano si existen tres números, llamados a, b y c, a < b < c, tales que a y c pertenecen a T y b no pertenece a T.

Hallar el número de subconjuntos T de {1, 2, … , 2019} que son orensanos.

Solución:

En este caso, la solución es una colaboración de Javier Nistal, medalla de plata en la Fase Nacional y primer clasificado en la Fase Local de la Universidad de Alicante.

Un conjunto no es orensano si y sólo si todos sus elementos son consecutivos.

Sea A el conjunto de todos los subconjuntos de {1, 2, …, 2019}.

Sea B el conjunto de los conjuntos no orensanos (de {1, 2, …, 2019}) .

Sea C el conjunto de los conjuntos orensanos (de {1, 2, …, 2019}).

Tenemos que B y C son disjuntos y que su unión es A, por lo que |C| = |A| – |B|.

Cada elemento de A se puede representar como 2019 cifras en binario, según que el número que ocupa una posición determinada en el conjunto {1, 2, …, 2019} esté incluido o no en ese elemento en concreto. Además, cada uno se representa de forma única y cualquier representación corresponde a un elemento de A, por lo que |A| es igual a la cantidad de números de 2019 cifras en binario, 2²⁰¹⁹.

Si llamamos B_n al conjunto de elementos de B compuestos de exactamente n números, está claro que |B₀| = 1, ya que sólo es el conjunto vacío, mientras que |B_n| = 2020 – n para todo n entre 1 y 2019 (número de sucesiones de n elementos consecutivos). Como la unión de todos ellos forma el conjunto B, y son disjuntos, está claro que |B| = |B₀| + |B₁| + |B₂| + … + |B₂₀₁₉| = 1 + 2019 + 2018 + … + 1 = 1 + 2020·2019/2 = 2039191.

Concluimos por tanto que la cantidad de conjuntos orensanos es 2²⁰¹⁹ – 2039191.