Al detallar el proceso en lulu El comentario de la señora:
Dado que sólo hay un número finito de opciones para $a,b$ debe existir un óptimo. Consideremos todos los pares $(a,b)$ con $a+b=n$ y $S(a)+S(b)=\max$ y $a\le b$ . $a=\overline{a_1a_2\ldots a_d}$ y $b=\overline{b_1b_2\ldots b_d}$ (con $b_1>0$ , pero posiblemente $a_1=0$ ). Entre todos estos $(a,b)$ elija uno que maximice $S(a)$ .
Supongamos que $a_k<9$ para algunos $k>1$ .
-
Si $b_k=0$ entonces debe haber una (máxima) $j<k$ con $b_j>0$ porque, de lo contrario, tendríamos $b<a$ . Si sustituimos $a_k$ con $a_k+1$ , $b_j$ con $b_j-1$ y $b_i$ con $9$ para $j<i\le k$ con los números $a',b'$ obtenido de esta manera, tenemos $a'+b'=a+b=n$ pero $S(a')+S(b')=S(a)+S(b)+9(k-j)$ , constriñendo la maximalidad de $S(a)+S(b)$ .
-
Si $b_k>0$ podríamos aumentar $a_k$ y disminuir $b_k$ por uno, logrando así $a'+b'=a+b=n$ , $S(a')+S(b')=S(a)+S(b)$ pero $S(a')=S(a)+1$ contradiciendo la maximalidad de $S(a)$ .
Concluimos que existe una maximización $a$ con $a\le b$ y $a_2=\ldots=a_d=9$ .
¿Qué podemos ganar si abandonamos la condición $a\le b$ ?
-
Si $a_1+b_1\ge 9$ podemos dejar que $a_1'=9$ y $b_1'=a_1+b_1-9$ , lo que hace que $a'$ consisten únicamente en $9$ y aparentemente el mayor número $\le n$ de esta forma
-
Si $a_1+b_1<9$ podemos dejar que $a_1'=0$ y $b_1'=a_1+b_1$ , lo que hace que $a'$ consisten únicamente en $9$ y aparentemente el mayor número $\le n$ de esta forma
En resumen, el $a$ (y sus asociados $b$ ) encontrado por el método codicioso está entre los maximizadores.
