Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Sea $p_n$ el número de subconjuntos majos de $\{1,2,\ldots,2n-1\}$ que contienen a su último elemento $2n-1$ y $q_n$ el número de subconjuntos majos de $\{1,2,\ldots,2n-1\}$ que no lo contienen. Por lo tanto, el número que nos piden es $p_6+q_6$, pero podemos obtenerlo más fácilmente de forma recursiva utilizando conjuntos de menos elementos.

Para ello, comenzamos observando que $p_1=q_1=1$ ya que los subconjuntos majos de $\{1\}$ son el vacío (que no contiene a $1$) y el total $\{1\}$ (que sí lo contiene). Además, un subconjunto $A\subseteq \{1,2,\ldots,2n-1\}$ majo con $2n-1\in A$, da lugar a tres subconjuntos majos de $\{1,2,\ldots,2n+1\}$: podemos añadirle únicamente $2n+1$, añadirle $\{2n,2n+1\}$ o no añadirle nada. Por su parte, si $2n+1\not\in A$, tenemos únicamente dos posibilidades: añadirle $2n+1$ o no añadirle nada. Esto nos da las fórmulas recursivas \[p_{n+1}=2p_n+q_n,\qquad q_{n+1}=p_n+q_n.\] Sin necesidad de resolver la recurrencia en general (ver la nota), como solo nos interesa $p_6+q_6$, podemos calcular directamente con las fórmulas obtenidas y los valores iniciales, lo que nos da \[p_2=3,\quad q_2=2,\quad p_3=8,\quad q_3=5,\quad p_4=21,\quad q_4=13,\quad p_5=55,\quad q_5=34,\] de donde obtenemos finalmente $p_6=144$ y $q_6=89$, luego el número que nos piden es $233$.

Nota. En general, se puede expresar la solución de la recurrencia matricialmente como \[\begin{pmatrix}p_{n+1}\\q_{n+1}\end{pmatrix}=\begin{pmatrix}2&1\\1&1\end{pmatrix}^n\begin{pmatrix}p_1\\q_1\end{pmatrix}.\] Fíjate en que aparecen los números de Fibonnacci en los cálculos. ¿Sabrías relacionar la expresión matricial con la recursión de Fibonnacci?