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= 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 1 o 2, 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 – 1)/3, o bien si k es impar (2k + 1 – 2)/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.

Published by

dimates

Grupo de divulgación matemática de la Universidad de Alicante

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *