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 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.

Published by

dimates

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

3 thoughts on “Solución a conjunto bescanoní”

  1. 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

  2. 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

Deja un comentario

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