Problema 2 de la Fase Catalana de la OME 2019 Se dirige a una edad de: 16-17 años
Sea n= 2k 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 2k – 1, pero la mitad de los pares (2k – 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 2k – 3), y los que son múltiplos de 8 (pero no de 16), no. Y así sucesivamente.
Contando todas estas cantidades, tendremos 2k – 1 + 2k – 3 + 2k – 5 + … + 2k – 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 (2k + 1 – 2)/3, o bien si k es impar (2k + 1 – 1)/3, pues depende del último elemento de la suma.
Si nos damos cuenta, en realidad se tratará de la parte entera de 2k + 1/3, en cualquier caso, ya que este número nunca será un entero.
Yo diria que hay un error en el càlculo cuando k és par, en efecto, por ejemplo en el caso k=2, el número màximo de elementos de un conjunto bescanoní és 3: {1,3,4}, en cambio el resultado de la fórmula seria: (2^3-2)/3=2, lo mismo ocurre en todos los casos pares, creo que hay que añadir una unidad en el caso k par:
(2^(k+1)-2)/3+1
o también (2^(k+1)+1)/3
Se puede dar una fórmula cerrada para cualquier k:
(2^(k+1)+(-1)^k)/3
Ahora veo que la fórmula para el caso de los impares tampoco és correcta creo que és:
k impar: (2^(k+1)-1)/3
k par: (2^(k+1)+1)/3
Saludos
Pues sí que había un error, gracias por comentar. Voy a corregirlo…
Pues es verdad.