OFO 2019 Problema 3

[MateoCV]

En el pizarrón hay escritos $2019$ números $1$, uno al lado del otro separados por un espacio de la siguiente forma:
$$\underbrace{1\;\;1\;\;1\;\;1\;\;...\;\;1}_{2019}$$
Edu quiere poner entre cada par de unos consecutivos un signo $+,-,\times,\div$. Como no se decidía cuál de todas las combinaciones le gustaba más, probó todas las posibilidades, y para cada una calculó el resultado de hacer la cuenta del pizarrón. Luego sumó todos estos resultados y obtuvo un número $N$. Hallar el valor de $N$.

[MateoCV]

Aquí publicaremos la solución oficial

[enigma1234]

Spoiler: mostrar

Si un 1 tiene un $\times$ o $\div$ a la izquierda este no estuviera en la suma dado que no afecta en nada. Si este tiene un $+$ o un $-$ a la izquierda al sumar todas las posibilidades este 1 aparece igual cantidad de veces como positivo que como negativo,es decirla suma de estos tampoco afecta a la suma. Entonces solo debemos ver la suma del 1 que no tiene ninguno a la izquierda es decir del primero y este aparece $4^{2018}$ veces (dado que cada espacio tiene 4 posibilidades).
Entonces la suma es $4^{2018}$.

[Sandy]

Spoiler: mostrar

Primero agrupamos todas las posibilidades en grupos de 2, tal que cada posibilidad esté junto con la que tiene los signos $\times$ y $\div$ iguales, pero con los signos $+$ y $-$ opuestos, es decir, cada uno se agrupa con el que es igual, pero que donde el primero tiene signos $+$, el segundo tiene signos $-$ y viceversa (por ejemplo, si fueran cinco números $1$, el $1+1\times 1\div 1-1$ iría agrupado con el $1-1\times 1\div 1+1$), para que así, al sumarlos, se cancelen todos los términos menos el primero (ya que es siempre positivo), haciendo que la suma de cada par sea la del primer término de cada posibilidad, es decir $1$. Por lo tanto, la suma de cada par será $1+1=2$.
Si por cada par de posibilidades la suma es $2$, entonces, en promedio, cada posibilidad suma $1$. Esto funciona para todas las posibilidades que tengan algún signo de suma o de resta, pero todos los que no tienen ninguno tienen como suma $1$ (cada uno), por lo que no afecta al promedio, que sigue siendo $1$. Por lo tanto, $N$ es igual a la cantidad de posibilidades.
Como se colocan 2018 signos, y cada signo puede ser cada uno de los $4$ posibles, la cantidad de posibilidades será $4\times 4\times 4\times ... \times 4$ (2018 veces), lo que significa que $N=4^{2018}$

[Joacoini]

Una solución más corta.

Spoiler: mostrar

Multiplicar y dividir lo que hacen es quitar unos del problema (un uno por cada signo).

Supongamos que hay $n$ símbolos de multiplicar y dividir ($0\leq n\leq2018$), estos se pueden ubicar de $\binom{2018}{n}$ formas y los multiplicamos por $2^n$ porque pueden ser de multiplicar o dividir.

Ahora nos quedan $2019-n$ unos y $2018-n$ símbolos + y - que ubicar, supongamos que $m$ de estos son menos ($0\leq m\leq 2018-n$) y los podemos ubicar de $\binom{2018-n}{m}$ formas.

Nuestro resultado es $2019-n-2m$, este resultado con $n$ y $m$ fijos aparece $2^n\binom{2018}{n}\binom{2018-n}{m}$ veces en $N$ (el número $2019-n-2m$ puede aparece más veces en $N$ pero utilizando otros $n$ y $m$).


$N=\sum_{n=0}^{2018} (2^n\binom{2018}{n}\sum_{m=0}^{2018-n}((2019-n-2m)\binom{2018-n}{m}))$

Vayamos por partes, $c=2018-n$

$\sum_{m=0}^{2018-n}((2019-n-2m)\binom{2018-n}{m})=\sum_{m=0}^{c}((c+1-2m)\binom{c}{m})$

$=(c+1-0)\binom{c}{0}+(c+1-2)\binom{c}{1}+...+(c+1-2c)\binom{c}{c}$

$=(c+1)\binom{c}{0}-0\binom{c}{0}+(c+1)\binom{c}{1}-2\binom{c}{1}+...+(c+1)\binom{c}{c}-2c\binom{c}{c}$

$=(c+1)(\sum_{m=0}^{c}\binom{c}{m})-0\binom{c}{0}-2\binom{c}{1}-...-2c\binom{c}{c}$

$=(c+1)2^c-0\binom{c}{0}-0\binom{c}{n}-1\binom{c}{1}-1\binom{c}{c-1}-...-c\binom{c}{c}-c\binom{c}{0}$

$=(c+1)2^c-c(\sum_{m=0}^{c}\binom{c}{m})=(c+1)2^c-c2^c=2^c=2^{2018-n}$

Ahora tenemos.

$N=\sum_{n=0}^{2018} (2^n\binom{2018}{n}2^{2018-n})=\sum_{n=0}^{2018} (2^{2018}\binom{2018}{n})=2^{2018}\sum_{n=0}^{2018} \binom{2018}{n}=2^{2018}\times 2^{2018}=4^{2018}$

[Pirógeno]

Buenas,

Los problemas de contar casos me resultan difíciles de interpretar, por eso hago esta pregunta, para entender y aprender.

Si el enunciado hubiera dicho que Edu quería decidir cuál de todas las permutaciones le gustaba más,

cómo debería yo contar todos los posibles casos?
cuál sería la diferencia con contar cuántos casos son todas las posibilidades de combinaciones que escribió?

Muchas gracias.