Solución a conjunto bescanoní

Problema 2 de la Fase Catalana de la OME 2019
Se dirige a una edad de: 16-17 años

Sea n= 2^k un número entero positivo.

Se dice que un subconjunto A de {1, 2, 3, …, n} es bescanoní si cumple que

1) El número 1 pertenece al conjunto.

2) Si un número x pertenece al conjunto, entonces 2x no pertenece al conjunto.

Se pide:

a) Encontrar un conjunto bescanoní con el máximo número de elementos cuando n = 2⁵.

b) Calcular el máximo número de elementos que puede tener un conjunto bescanoní en función de k.
Solución:

La idea central es que debemos elegir si un número x o 2x pertenece al conjunto, ya que ambos simultáneamente no pueden pertenecer.

Además, puesto que queremos conjuntos con el mayor número de elementos, siempre optaremos porque x pertenezca, ya que en muchos casos la cantidad de elementos será la misma, y en ocasiones nos impedirá que 4x pertenezca al conjunto, si optamos porque sea 2x en lugar de x el que forme parte del conjunto.

En el caso de k = 5, n = 32, y el conjunto con más elementos estará formado por {1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 29, 31}. Hay más conjuntos con la misma cantidad de elementos, cambiando el 16 por el 32, pero también podemos cambiar 15 por 30, o 26 por 13, por ejemplo.

Por lo tanto, tenemos una respuesta para (a), y es uno de estos conjuntos de 21 elementos.

Para la respuesta de (b), podemos observar que podemos situar en el conjunto que construimos a todos los impares, que serán 2^{k – 1}, pero la mitad de los pares (2^{k – 2}) no podemos situarlos (los que son múltiplos de 2, pero no de 4, ya que sus mitades serán impares y pertenecerán al conjunto). Sin embargo, los que son múltiplos de 4 (pero no de 8) sí podremos incluirlos (son 2^{k – 3}), y los que son múltiplos de 8 (pero no de 16), no. Y así sucesivamente.

Contando todas estas cantidades, tendremos 2^{k – 1} + 2^{k – 3} + 2^{k – 5} + … + 2^{k – 2·[k/2] + 1}. Si nos fijamos, el último término puede valer 2 o 1, ya que depende de que k sea par o impar.

Se trata, entonces, de la suma de una progresión geométrica de razón 1/4, Si k es par, la suma (aplicando la fórmula correspondiente, o bien reproduciendo el razonamiento mediante la estrategia de multiplicar por 4 y restar), da (2^{k + 1} – 2)/3, o bien si k es impar (2^{k + 1} – 1)/3, pues depende del último elemento de la suma.

Si nos damos cuenta, en realidad se tratará de la parte entera de 2^{k + 1}/3, en cualquier caso, ya que este número nunca será un entero.