OFO 2019 Problema 3

Avatar de Usuario
MateoCV

OFO - Medalla de Bronce FOFO 7 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 218
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 9
Nivel: Exolímpico
Ubicación: Córdoba

OFO 2019 Problema 3

Mensaje sin leer por MateoCV » Dom 20 Ene, 2019 12:12 am

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$.
$2^{82589933}-1$ es primo

Avatar de Usuario
MateoCV

OFO - Medalla de Bronce FOFO 7 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 218
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 9
Nivel: Exolímpico
Ubicación: Córdoba

Re: OFO 2019 Problema 3

Mensaje sin leer por MateoCV » Lun 28 Ene, 2019 1:19 am

Aquí publicaremos la solución oficial
$2^{82589933}-1$ es primo

Avatar de Usuario
enigma1234

OFO - Medalla de Oro FOFO 8 años - Medalla Especial OFO - Medalla de Plata
Mensajes: 66
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 3
Nivel: 2

Re: OFO 2019 Problema 3

Mensaje sin leer por enigma1234 » Lun 28 Ene, 2019 9:26 am

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}$.
One in a millon...my lucky strike! :D

Sandy

OFO - Medalla de Bronce
Mensajes: 29
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

Re: OFO 2019 Problema 3

Mensaje sin leer por Sandy » Lun 28 Ene, 2019 11:10 am

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}$


Avatar de Usuario
Joacoini

OFO - Medalla de Plata FOFO 8 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 144
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 4
Nivel: 2
Ubicación: Ciudad Gotica

Re: OFO 2019 Problema 3

Mensaje sin leer por Joacoini » Lun 28 Ene, 2019 12:21 pm

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}$
NO HAY ANÁLISIS.

Pirógeno

OFO - Medalla de Bronce
Mensajes: 3
Registrado: Vie 11 Ene, 2019 10:31 am
Medallas: 1
Nivel: Otro

Re: OFO 2019 Problema 3

Mensaje sin leer por Pirógeno » Mar 29 Ene, 2019 9:02 am

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.

Responder