Pregunta del concurso de matemáticas de la escuela secundaria (teoría de los números) - demostrar:

Question

Reposting con Mathjax - ¡lo siento, es la primera vez!

Dejemos que $S = \{4,8,9,16,...\}$ sea el conjunto de enteros de la forma $m^k$ para los enteros $m, k \ge 2$ . Para un número entero positivo $n$ , dejemos que $f(n)$ denotan el número de formas de escribir $n$ como la suma de (uno o más) elementos distintos de $S$ . Por ejemplo, $f(5) = 0$ ya que no hay formas de expresar 5 de esta manera, y $f(17) = 1$ desde $17 = 8+9$ es la única forma de expresar 17.

(a) Demuestre que $f(30) = 0$

(b) Demuestre que $f(n) \ge 1$ para $n \ge 31$ .

(c) Que $T$ sea el conjunto de enteros para los que $f(n) = 3$ . Demostrar que $T$ es finito y no vacío, y encontrar el mayor elemento de $T$ .

Creo que la parte a) es relativamente fácil de comprobar ya que ninguno de los valores de los primeros valores del conjunto $S = \{4,8,9,16,25,27,32,64,...\}$ se sumarán para llegar a 30.

No estoy seguro de por dónde empezar con la parte b y la parte c. Para la parte b, estaba trabajando en la búsqueda de sumas para cada número, pero pensé que no era una forma inteligente de proceder. Para la parte c) no estoy seguro de por dónde empezar.

Gracias por la ayuda que puedan prestar.

Answer 1

Para la parte b, observe que todos los múltiplos de $4$ puede ser representado porque tiene todos los poderes de $2$ excepto $1,2$ . Exprese cualquier múltiplo de $4$ en binario y leer los números que hay que sumar para obtenerlo. Todos los números equivalentes a $1 \bmod 4$ que son al menos $9$ se puede expresar porque el número menos $9$ es un múltiplo de $4$ y, por tanto, expresable. Todos los números equivalentes a $2 \bmod 4$ que son $34$ o mayores son expresables porque $34=9+25$ . Todos los números equivalentes a $3 \bmod 4$ que son $27$ o mayor porque tenemos $27$ disponible. Por lo tanto, el mayor número que no se puede expresar es $30$ .

En el caso de c, los números que son bastante grandes tendrán demasiadas representaciones. Haremos cada clase de residuo $\mod 4$ a su vez.

Para $0 \bmod 4$ tenemos $\emptyset,36, 9+27, 25+27$ como formas de expresar los números sin ninguna de las $2^n$ términos. Por lo tanto, podemos expresar cualquier número $52$ o mayor en $4$ o más formas.

Para $1 \bmod 4$ tenemos $9, 25, 9+36, 49$ por lo que podemos expresar cualquier número $49$ o mayor en $4$ o más formas.

Para $2 \bmod 4$ tenemos $9+25, 9+49, 9+36+49, 25+49$ por lo que podemos expresar cualquier número $74$ o mayor en $4$ o más formas.

Para $3 \bmod 4$ tenemos $27, 27+36, 9+25+49, 9+25+36+49$ por lo que podemos expresar cualquier número $119$ o mayor en $4$ o más formas.

El mayor número en $T$ es $115$ que puede expresarse como $64+27+16+8, 36+32+27+16+4, 49+32+25+9$ pero de ninguna otra manera.