Question

Considera una cadena de $n$ $7$ , $7777\ldots77,$ en la que se insertan signos $+$ para producir una expresión aritmética. Por ejemplo, $7 + 77 + 777 + 7 + 7 = 875$ podría obtenerse de ocho $7$ de esta manera. ¿Para cuántos valores de $n$ es posible insertar signos $+$ de modo que la expresión resultante tenga valor $7000$ ?

Consider a string of $n$ $7$ 's, $7777\ldots77,$ into which $+$ signs are inserted to produce an arithmetic expression. For example, $7 + 77 + 777 + 7 + 7 = 875$ could be obtained from eight $7$ 's in this way. For how many values of $n$ is it possible to insert $+$ signs so that the resulting expression has value $7000?$

Respuesta

Solución:

Dividir entre $7$ convierte los sumandos en $1,$ $11,$ o $111$ (ningún sumando más largo cabe, ya que $1111 \gt 1000$ ) y el objetivo en $1000.$ Si $x,$ $y,$ $z$ cuentan los sumandos de cada tamaño, entonces $x + 11y + 111z = 1000$ y $n = x + 2y + 3z.$ Restar da $n = 1000 - 9(y + 12z),$ así que los posibles $n$ corresponden exactamente a los valores alcanzables de $v = y + 12z.$

Las restricciones son $z \le 9$ y $0 \le y \le \frac{1000 - 111z}{11}$ (entonces $x \ge 0$ se sigue). Para $z = 0, 1, \ldots, 9$ el valor $v = y + 12z$ recorre los intervalos $[0, 90],$ $[12, 92],$ $[24, 94],$ $[36, 96],$ $[48, 98],$ $[60, 100],$ $[72, 102],$ $[84, 104],$ $[96, 106],$ y $\{108\}$ (cuando $z = 9,$ solo $y = 0$ cabe). Su unión es todo entero desde $0$ hasta $106$ junto con $108;$ solo $107$ es inalcanzable.

Así que $v$ toma $107 + 1 = 108$ valores, y $n = 1000 - 9v$ toma $108$ valores.

Dividing by $7$ turns the summands into $1,$ $11,$ or $111$ (no longer summand fits, since $1111 \gt 1000$ ) and the target into $1000.$ If $x,$ $y,$ $z$ count the summands of each size, then $x + 11y + 111z = 1000$ and $n = x + 2y + 3z.$ Subtracting gives $n = 1000 - 9(y + 12z),$ so the possible $n$ correspond exactly to the attainable values of $v = y + 12z.$

The constraints are $z \le 9$ and $0 \le y \le \frac{1000 - 111z}{11}$ (then $x \ge 0$ follows). For $z = 0, 1, \ldots, 9$ the value $v = y + 12z$ ranges over the intervals $[0, 90],$ $[12, 92],$ $[24, 94],$ $[36, 96],$ $[48, 98],$ $[60, 100],$ $[72, 102],$ $[84, 104],$ $[96, 106],$ and $\{108\}$ (when $z = 9,$ only $y = 0$ fits). Their union is every integer from $0$ to $106$ together with $108;$ only $107$ is unattainable.

So $v$ takes $107 + 1 = 108$ values, and $n = 1000 - 9v$ takes $108$ values.

2004 AIME II Problema 14

Solución:

El Problema 14 en otros años