Cono 2022 P6

[Gianni De Rico]

En el pizarrón están escritos los números enteros $1,2,3,\ldots ,170$. Se desea colorear cada número con uno de los $k$ colores $C_1,C_2,\ldots ,C_k$, de modo que se cumpla la siguiente condición: para cada $i$ con $1\leq i<k$, la suma de todos los números de color $C_i$ divide a la suma de todos los números de color $C_{i+1}$. Determinar el máximo valor de $k$ para el cual es posible realizar esta coloración.

[enigma1234]

Solución:

Spoiler: mostrar

Sea $k$ tal que cumple las condiciones del problema.

Definimos para cada $i$ el conjunto $D_i$ como el conjunto de números del color $C_i$.

Lema 1: Si $S=\{i : |D_i|=1\}$. Luego $|S|\leq 8$.

Spoiler: mostrar

Sea $S=\{i_1<i_2<\dots<i_s\}$ donde $|S|=s$. Si $D_{i_m}=\{a_m\}$ para cada $1\leq m\leq s$, luego por la condición del problema tenemos que:
$$a_1\mid a_2\mid a_3\mid\dots\mid a_s\dots(1)$$
Donde claramente $1\leq a_1<a_2<\dots<a_n\leq 170\dots (2)$. Luego, en:
$$a_s=a_1\times \frac{a_2}{a_1}\times\frac{a_3}{a_2}\times\dots\times\frac{a_s}{a_{s-1}}$$
Cada factor (aparte de $a_1$) es un entero por (1) y al menos 2 por (2), luego:
$$170\geq a_s\geq 1\times 2\times 2\times\dots\times 2=2^{s-1}\to s\leq 8$$
Lo que prueba lo deseado.

Lema 2: $k\leq 89.$

Spoiler: mostrar

Como $D_1,D_2\dots, D_k$ es una partición de $\{1,2,3,\dots,170\}$. Tenemos que:
$$170=\sum_{i=1}^{k} |D_i|=\sum_{i\in S} |D_i|+\sum_{i\notin S}|D_i|$$
$$ \to 170=|S|+\sum_{i\notin S}|D_i|\geq |S|+ 2(k-|S|)=2k-|S|\geq 2k-8\to k\leq 89$$
como queriamos.

Por lo tanto solo bastaría un ejemplo para probar que $k_{\text{max}}=89$, y en efecto el ejemplo lo encontramos de la siguiente manera:

Spoiler: mostrar

$S_i$ es la suma de los elementos de $D_i$.

Usando lo probado anteriormente tenemos que si $k=89$, luego $|S|=8$ y necesariamente tendremos que los 8 conjuntos de un elemento son las potencias de $2$: $\{1\}, \{2\},\{4\},\dots,\{128\}$. Luego para tener las igualdades tendremos que todos los subconjuntos restantes deben ser necesariamente de 2 elementos, que deben sumar una potencia de 2, o un múltiplo de $128$. Para este múltiplo de 128, podemos ver que no puede ser mas de $128*3=384$ debido a que una pareja tiene como máximo suma $170+169=339$

Luego todos los subconjuntos de 2 elementos deberían sumar una potencia de 2 y vamos formando los subconjuntos empezando por 170 y dándonos cuenta que todos los subconjuntos se van formando de una única manera de esta forma, obteniendo el siguiente ejemplo:

$$D_1=\{1\}, D_2=\{2\},D_3=\{4\}\to S_1=1\mid S_2=2\mid S_3=4$$
$$D_4=\{3,5\}, D_5=\{8\}\to S_3\mid S_4=S_5=8$$
$$D_6=\{6,10\}, D_7=\{7,9\},D_8=\{16\}\to S_5\mid S_6=S_7=S_8=16$$
$$D_{9}=\{11,21\},D_{10}=\{12,20\}\dots, D_{13}=\{15,17\},D_{14}=\{32\}\to S_{8}\mid S_{9}=S_{10}=\dots=S_{14}=32$$
$$D_{15}=\{22,42\},D_{16}=\{23,41\}\dots, D_{24}=\{31,33\},D_{25}=\{64\}\to S_{14}\mid S_{15}=S_{16}=\dots=S_{25}=64$$
$$D_{26}=\{43,85\},D_{27}=\{44,84\}\dots, D_{46}=\{63,65\},D_{47}=\{128\}\to S_{25}\mid S_{26}=S_{26}=\dots=S_{47}=128$$
$$D_{48}=\{86,170\},D_{43}=\{87,169\}\dots, D_{89}=\{127,129\}\to S_{47}\mid S_{48}=S_{49}=\dots=S_{89}=256$$