FOFO 9+1 Años - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 1002
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: Santa Fe

FOFO 9+1 Años - Problema 5

Mensaje sin leer por Fran5 »

La ciudad Nlogonia tiene $2048$ personas. Cuando se ordena a las personas de manera creciente por la cantidad de dinero que tienen, la $n-$ésima persona tiene $n$ veces la cantidad de dinero que tiene la más pobre. En cierto momento específico, todos los ciudadanos de Nlogonia deciden hacer lo siguiente: cada quien reparte equitativamente la mayor parte posible de su riqueza entre todos los ciudadanos de Nlogonia (incluído él mismo) y da lo que sobre a la ciudad vecina Ncubonia.

Sabemos que a la cantidad de dinero de la persona más pobre de Nlogonia es un número impar. Determinar la cantidad de dinero total que se dio a la ciudad Ncubonia.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 1002
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: Santa Fe

Re: FOFO 9+1 Años - Problema 5

Mensaje sin leer por Fran5 »

Como a pocas personas le salió este problema, les traigo una solución oficial
Spoiler: mostrar
soluciion fofo 2020 p5.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
1  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años
Mensajes: 68
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 7
Nivel: 3

Re: FOFO 9+1 Años - Problema 5

Mensaje sin leer por joa.fernandez »

Solución:
Spoiler: mostrar
Vamos a darle forma a lo que realizan los nlogonenses.

Al tener que repartir el dinero lo más equitativamente posible, si un habitante tiene una cantidad de dinero, la cual llamamos $k$, entonces, a cada nlogonense le corresponderá $\lfloor \dfrac{k}{2048} \rfloor$ dinero de esa cantidad. Como $k$ es natural (ya que la cantidad de dinero del más pobre lo es, y la cantidad de dinero del resto son múltiplos de esta) podemos expresarlo como $k = 2048 \cdot t + r$, con $t \in \mathbb{N}_0$, $r \in \{0,1,2,3,...,2046,2047\}$.
Ahora, notemos que al fin y al cabo, la cantidad de dinero que recibirán los ncubonianos serán, por cada nlogonense, su resto en la división por $2048$, es decir, $r$.

Sean $N_1,N_2,...,N_{2048}$ las cantidades de dinero de los Nlogonenses ordenadas de menor a mayor según el subíndice ($i<j \Leftrightarrow N_i<N_j$). Por enunciado sabemos que:
$N_i = iN_1$. Supongamos que $N_i \equiv N_j$ (mód $2048$) para algunos $i$,$j$, $i\neq j$. Luego:
$iN_1 \equiv jN_1$ (mód $2048$) y como $d=(2048,N_1) = 1$ ya que $N_1$ es impar y $2048 = 2^{11}$, podemos dividir por N_1 a ambos lados, de donde: $i \equiv j$ (mód $2048$), y esto es un absurdo, ya que $i$ y $j$ son ambos menores o iguales a $2048$ (no pueden ser $0$), y además $i$ es distinto de $j$. Luego, todos los $N_i$ tienen restos distintos en la división por $2048$. Sea $r_i | N_i \equiv r_i$ (mód $2048$). Por lo tanto, sabemos que:
$A = \{r_1,r_2,...,r_{2048}\}$ es una permutación de $B = \{0,1,2,...,2047\}$. Y como habíamos dicho que los ncubonianos recibían $r_i$ dinero por cada $N_i$, al fin y al cabo recibirán la suma total de $0+1+2+...+2047 = \frac{2047\cdot 2048}{2}=2096128$.
2  

Gabriel Bernal

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 FOFO Pascua 2020 - Mención-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González
COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 33
Registrado: Sab 10 Ago, 2019 12:37 pm
Medallas: 8

Re: FOFO 9+1 Años - Problema 5

Mensaje sin leer por Gabriel Bernal »

Solución
Spoiler: mostrar
Sea $K$ la cantidad de dinero que tiene la persona más pobre y $r$ tal que $K≡r(mód2048)$ y $0≤r≤2047$. Además sea $d=mcd(2048,r)$. Queremos ver cuánto da la suma $r+2r+...+2048r$ donde cada sumando se toma módulo $2048$ (si es exactamente $2048$ se toma $0$).

Como $2048=2^{11}$ todos los posibles valores de $d$ son $2^t$ con $0≤t≤11$. Tomamos entonces $d=2^t$, consecuentemente $r=2^ta$ con $a$ impar. Luego $2^ta,2×2^ta,...,\frac{2048}{2^t}×2^ta$ son congruentes con $2^t,2×2^t,...,\frac{2048}{2^t}\times 2^t$ módulo $2048$ en algún orden. Esto ocurre porque ambos grupos, $a,2a,...,\frac{2048}{2^t}a$ y $1,2,...,\frac{2048}{2^t}$, son todos distintos módulo $\frac{2048}{2^t}$.

La suma $r+2×r+...+\frac{2048}{2^t}×r$ tomados cada sumando módulo $2048$ es entonces la suma $2^t+2×2^t+...+\frac{2048}{2^t}×2^t$ tomados todos módulo $2018$. Pero a esto último se le puede sacar factor $2^t$ (tomando aparte $\frac{2048}{2^t}×2^t=0$) porque todos los números son menores a $2048$. Haciendo esto queda $2^t(1+2+...+(2^{11−t}−1))=2^t(\frac{(2^{11−t}−1)×(2^{11−t})}{2})=1024(2^{11−t}−1)$. Además esta suma aparece $2^t$ veces en $r+2r+...+2048r$ por lo que al final nos queda que la cantidad de dinero que va a Ncubonia es $2^t×1024(2^{11−t}−1)$.
En particular si $t=0$ el dinero que recibe Ncubonia es $2096128$.

Uriel J

OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020
COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 21
Registrado: Jue 29 Nov, 2018 2:46 pm
Medallas: 9
Nivel: 1

Re: FOFO 9+1 Años - Problema 5

Mensaje sin leer por Uriel J »

Solución:
Spoiler: mostrar
Sea $k$ la cantidad de dinero de la primera persona (la más pobre)
Entonces la segunda persona tiene $2k$ y así hasta que llegamos que la persona número $2048$ tiene $2048k$ de dinero

A nosotros nos preguntan cuanto dinero se le dió a la otra ciudad, que cada persona le da lo que le sobra después de repartir entre los $2048$, basicamente le da el resto de sus monedas en la división por $2048$

Sea $r(i)$ el resto en la división por $2048$ del dinero que tiene la persona $i$, que sería $i . k$

Vamos a demostrar que para todo $m$ tal que $1 \leq m \leq 1023$, $r(m) + r(2048 - m) = 2048$

Veamos que $m . k\equiv r(m) \pmod{2048}$ y $(2048 - m) . k\equiv -m . k \equiv r(2048 - m) \pmod{2048}$

Luego, $m . k + (-m). k\equiv r(m) + r(2048 - m) \pmod{2048}$ como $mk + (-m)k = 0$ tenemos que:

$r(m) + r(2048 - m)\equiv 0 \pmod{2048}$

Veamos que como $r(i)$ es el resto en la división por $2048$, $r(i) < 2048$

además si $i\neq 2048$, entonces $r(i)\neq 0$ pues $k$ es coprimo con $2048$ porque es impar y el $2048$ solo tiene factor primo al $2$ pero también $i$ no es multiplo de $2048$ entonces $i . k$ no es multiplo de $2048$ si $i\neq 2048$ entonces para todo $i$ entre $1$ y $2047$, $0 < r(i) < 2048$

Además tenemos que para todo $m \leq 1023$, $r(m) + r(2048 - m)\equiv 0 \pmod{2048}$ y $0 < r(m) + r(2048 - m) < 2048 . 2 = 4096$ entonces para todo $m$ tal que $1 \leq m \leq 1023$ tenemos que $r(m) + r(2048 - m) = 2048$

Ahora veamos que si reemplazamos $m$ por todos los números entre $1$ y $1023$ obtenemos:

$2048 . 1023 = 2095104 = r(1) + r(2) + r(3) + .... + r(1023) + r(1025) + .... + r(2047)$

Ahora solo nos falta calcular $r(2048)$ y $r(1024)$

Como $2048k$ es múltiplo de $2048$, tenemos que $r(2048) = 0$

Ahora veamos que $1024k$ es múltiplo de $1024$ pero no de $2048$ pues $k$ es impar, entonces tenemos que $r(1024) = 1024$ pues $1024k = 1024(2j + 1) = 2048j + 1024$ que entonces tiene resto $1024$ en la división por $2048$

Entonces,
$2095104 + 1024 = 2096128 = r(1) + r(2) + r(3) + ..... + r(1023) + r(1024) + r(1025) + .... + r(2047) + r(2048)$

RTA: Se le dió $2096128$ de dinero a la ciudad de Ncubonia
1  

Responder