Sea x un conjunto de enteros {9,15,21,27, … 375}. Denote el subconjunto de x, de modo que la suma de no dos elementos de y sea 384. ¿Cuál es el número máximo de elementos en y?

El número máximo de elementos en cualquiera de estos subconjuntos es [matemática] 31 [/ matemática] , y hay [matemática] 2 ^ {31} [/ matemática] tales subconjuntos.


Sea [math] X = \ {9, 15, 21, \ ldots, 375 \} = \ {6k + 3: 1 \ le k \ le 62 \} [/ math]. Si [matemática] x_1 = 6k_1 + 3 \ en X [/ matemática] y [matemática] x_2 = 6k_2 + 3 \ en X [/ matemática], entonces [matemática] x_1 + x_2 = 6 (k_1 + k_2 + 1) [ /matemáticas]. Entonces [matemáticas] x_1 + x_2 = 384 = 64 \ cdot 6 [/ matemáticas] es equivalente a [matemáticas] k_1 + k_2 = 63 [/ matemáticas].

Por lo tanto, necesitamos encontrar el subconjunto [math] S [/ math] del tamaño máximo del conjunto [math] \ {1,2,3, \ ldots, 62 \} [/ math] tal que [math] s_1 + s_2 \ ne 63 [/ math] para cada elección de [math] s_1, s_2 \ en S [/ math].

Forme los pares [matemáticas] 31 [/ matemáticas] [matemáticas] \ {1,62 \}, \ {2,61 \}, \ {3,60 \}, \ ldots, \ {31,32 \} [/ matemáticas]. Si elegimos exactamente un elemento de cada uno de estos pares, el conjunto de elementos así formado satisface claramente la condición requerida (no hay dos elementos que sumen [math] 63) [/ math]. Tal elección se puede hacer de [math] 2 ^ {31} [/ math], ya que hay dos opciones para cada par y estas se hacen independientes entre sí.

Por otro lado, elegir [math] 32 [/ math] números del conjunto [math] \ {1,2,3, \ ldots, 62 \} [/ math] nos obliga a elegir ambos elementos de al menos un par . Cualquiera de estos pares tiene elementos que suman [math] 63 [/ math], violando el requisito para el subconjunto.

Esto prueba nuestras dos afirmaciones. [matemáticas] \ blacksquare [/ matemáticas]

Lo siento, lee la pregunta mal.
El número máximo de elementos será =>
Tomar uno de cada par desfavorable, es decir, 31

Espero haberlo dejado lo más claro posible.