Solución: Sumas de año nuevo

Publicamos la solución al divertimento de las sumas de año nuevo.

Divertimento:

De un conjunto \(C\) de 2022 enteros positivos se toman \(n\) subconjuntos distintos de modo que las sumas de los elementos de cada uno de ellos son coprimas dos a dos. ¿Cuál es el máximo valor posible de \(n\)?
Nota: Se entiende que el vacío tiene suma cero.

Solución:

En este divertimento debemos maximizar el valor de \(n\) escogiendo bien el conjunto \(C\), y la respuesta es \(2^{2021}+1\), es decir, la mitad de todos los posibles subconjuntos de \(C\) más uno. Vamos a ver en primer lugar que no podemos tener más de esa cantidad de subconjuntos de \(C\). Llamaremos «suma de un subconjunto» a la suma de sus elementos.

En efecto, si todos los elementos de \(C\) fueran pares, todos los subconjuntos tendrían sumas pares y no serían primas entre sí. Por otro lado, si hubiera algún elemento impar \(x\in C\), podríamos descomponer las partes de \(C\) en parejas de la forma \(\{P,P\cup\{x\}\}\), para todo subconjunto \(P\) que no contenga a \(x\). Como las sumas de \(P\) y de \(P\cup{x}\) son de paridad opuesta, cada par de los que hemos formado contiene un subconjunto de suma par y otro de suma impar. Por tanto, no podremos escoger más de los \(2^{2021}\) subconjuntos de \(C\) de suma impar y, si acaso, uno más con suma par, obteniendo los \(2^{2021}+1\) que hemos dicho al principio.

Vamos a ver ahora que existe un conjunto \(C\) para el que es posible completar esa estrategia. De lo anterior podemos deducir que no podemos tener más de un elemento impar, pero eso no evita que los elementos pares sean primos entre sí. Sin embargo, esto último se puede solventar. Sea \(f=(2^{2021})!\) y consideremos el conjunto \(C={1,f,2f,4f,\ldots,2^{2020}f}\). De \(C\) tomaremos los \(2^{2021}\) subconjuntos que contienen al uno y, además, \({f}\). La suma de este último es coprima con cualquier otra, porque el resto serán impares, así que centrémonos en las demás, que serán de la forma \(af+1\) para cierto entero \(0\leq a<2^{2021}\). Por la forma de los elementos de \(C\), la expresión binaria de dicho entero \(a\) nos determina unívocamente qué elementos de \(C\) están presentes en nuestro subconjunto, por lo que todas las sumas \(af+1\) serán distintas entre sí.

Sean pues dos subconjuntos \(A,B\subseteq C\) de sumas respectivas \(af+1\) y \(bf+1\) (con \(a>b\)), y supongamos que existe un primo \(p\) dividiendo a ambas sumas. En ese caso, \(p|(a-b)f\). Como \(a-b\) es un entero positivo menor que \(2^{2021}\), aparece en los factores de \(f\), así que en cualquier caso \(p|f\), pero eso es una contradicción, porque \(p|af+1\). En conclusión, las sumas de los subconjuntos que contienen al uno son todas coprimas dos a dos y hemos terminado.