OFO 2023 Problema 10

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

OFO 2023 Problema 10

Mensaje sin leer por Gianni De Rico »

La delegación argentina en Qatar estuvo conformada por $n$ muchachos. Algunos muchachos son amigos de otros (la amistad es mutua), y en promedio cada muchacho tiene $d$ amigos. Scaloni quiere armar un grupo con algunos de los muchachos. Decimos que un muchacho del grupo está ilusionado si tiene al menos $\dfrac{d}{2}$ amigos en el grupo.
Demostrar que Scaloni puede armar un grupo en el cual todos los muchachos están ilusionados.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2023 Problema 10

Mensaje sin leer por Gianni De Rico »

Solución Oficial:
Spoiler: mostrar
Decimos que dos muchachos forman un par especial si son amigos entre sí. Digamos que hay $m$ pares especiales en el grupo. Numeramos los muchachos de $1$ a $n$ y llamamos $a_i$ a la cantidad de amigos del muchacho $i$. Entonces $a_1+a_2+\cdots +a_{n-1}+a_n=2m$, pues si el muchacho $a_i$ es amigo del muchacho $a_j$ estamos contando dos veces al par especial que ellos forman (una cuando contamos a $a_j$ como amigo de $a_i$, otra cuando contamos a $a_i$ como amigo de $a_j$), con lo que $d=\dfrac{a_1+a_2+\cdots +a_{n-1}+a_n}{n}=\dfrac{2m}{n}$, y así $\dfrac{d}{2}=\dfrac{m}{n}$. Entonces el problema nos pide hallar un grupo de muchachos tal que todos tengan al menos $\dfrac{m}{n}$ amigos (dentro del grupo). Si $m=0$, entonces todos los muchachos están ilusionados. Supongamos entonces que $m>0$.

Realizamos el siguiente procedimiento. En el paso $0$ tenemos el grupo $G_0$. Si en el paso $k$ tenemos el grupo $G_k$, sacamos un muchacho que tenga menos de $\dfrac{m}{n}$ amigos (dentro del grupo) y obtenemos el grupo $G_{k+1}$.
Como en cada paso sacamos un muchacho y $G_0$ tiene $n=n-0$ muchachos, entonces $G_k$ tiene $n-k$ muchachos. Se sigue que el procedimiento termina en a lo sumo $n$ pasos. Sea $t$ el paso en el que termina. Si $t<n$ entonces $G_t$ es no vacío y, como no podemos realizar otro paso, resulta que todos los muchachos tienen al menos $\dfrac{m}{n}$ amigos en $G_t$. Llamamos $E(G_k)$ a la cantidad de pares especiales de $G_k$ y $M(G_k)$ a la cantidad de muchachos de $G_k$, entonces $M(G_k)=n-k$.

Veamos que $\dfrac{E(G_k)}{M(G_k)}\geq \dfrac{m}{n}$ para todo $k$ válido, por inducción en $k$.
El caso base $k=0$ es claramente cierto pues$$\frac{E(G_k)}{M(G_k)}=\frac{E(G_0)}{M(G_0)}=\frac{m}{n}.$$Supongamos como hipótesis inductiva que vale para $k$. Veamos que vale para $k+1$.
En efecto, si el muchacho sacado tiene $a$ amigos, entonces$$E(G_k)=E(G_{k+1})+a<E(G_{k+1})+\frac{m}{n},$$pues los muchachos que sacamos tienen menos de $\dfrac{m}{n}$ amigos, entonces$$E(G_{k+1})\geq E(G_k)-\frac{m}{n}.$$Luego,$$\frac{E(G_{k+1})}{M(G_{k+1})}=\frac{E(G_{k+1})}{n-k-1}\geq \frac{E(G_k)-\frac{m}{n}}{n-k-1}.$$Por hipótesis inductiva tenemos que $E(G_k)\geq \dfrac{m}{n}M(G_k)=\dfrac{m}{n}(n-k)$, con lo que\begin{align*}\frac{E(G_{k+1})}{M(G_{k+1})} & \geq \frac{E(G_k)-\frac{m}{n}}{n-k-1} \\
& \geq \frac{\dfrac{m}{n}(n-k)-\frac{m}{n}}{n-k-1} \\
& =\frac{\dfrac{m}{n}(n-k-1)}{n-k-1} \\
& =\frac{m}{n}.
\end{align*}La inducción está completa.

Supongamos que $t=n$, entonces tenemos definido el grupo $G_{n-1}$, con $M(G_{n-1})=n-(n-1)=1$, de modo que $E(G_{n-1})=0$, lo que nos dice que$$0=\frac{0}{1}=\frac{E(G_{n-1})}{M(G_{n-1})}\geq \frac{m}{n}.$$Absurdo pues $m,n>0$. El absurdo provino de suponer que $t=n$, y como $t\leq n$, esto implica que $t<n$. Ganamos.
♪♫ do re mi función lineal ♪♫
FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Medalla de Plata-OFO 2023
OFO - Jurado-OFO 2024
Mensajes: 60
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Corrientes

Re: OFO 2023 Problema 10

Mensaje sin leer por FabriATK »

Advertencia: solución no apta para todo público(contiene escenas violentas)
Spoiler: mostrar
Imaginemos que tenemos un grafo con $n$ vértices que representan a los muchachos, con aristas que representas sus amistades.
Definimos "matar a un muchacho" como agarrar y borrar del grafo el vértice que lo representa y todas las aristas que se unían a este vértice(es decir, hacemos como que deja de existir).

Sean $A_1, A_2,..., A_k$ la cantidad de amigos vivos de cada muchacho vivo(estas cantidades van a ir variando).
En un inicio, $\frac{A_1 +A_2+...+A_n}{n} = d$ Es decir, $A_1+A_2+...+A_n = nd$

Y acá es donde llega la parte violenta, porque vamos a ir matando sucesivamente a los muchachos con menos amigos.
En cada paso, busquemos al muchacho con menos amigos(si hay varios con la misma cantidad, tomamos a uno solo por paso) y vemos si tiene menos de $\frac{d}{2}$ amigos. Supongamos que elegimos al muchacho $i$
Si tiene menos de $\frac{d}{2}$ amigos, lo matamos.
Si observamos nuevamente la suma $A_1 +A_2+...+A_k$, esta se reduce en $2A_i$, porque dejamos de contar a los amigos del muchacho $i$, y el muchacho $i$ ya no suma en los contadores de amigos de los demás muchachos vivos.


Quiero demostrar que este proceso termina antes de matar a todos los muchachos:
Si matamos a todos los muchachos, la suma de la cantidad de amigos pasaría, de inicio a final, de $nd$ a $0$.
Pero en cada paso matamos a un muchacho con menos de $\frac{d}{2}$ amigos vivos, reduciendo la suma de amistades en menos de $2\times \frac{d}{2} = d$. Y si matamos a $n$ muchachos la suma se reduce en menos de $n\times 2\times \frac{d}{2} = nd$, absurdo.

Es decir que en algún momento el proceso termina, sin matar a todos los muchachos. Lo que quiere decir que existe un subconjunto de los muchachos (que son los que quedan vivos) tales que todos tienen $\frac{d}{2}$ o mas amigos entre ellos(entre los que quedaron vivos). Scaloni puede armar el grupo con ellos y todos estarán ilusionados.
5  
Avatar de Usuario
fran :)

FOFO 12 años - Mención-FOFO 12 años OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años
Mensajes: 20
Registrado: Mié 22 Jun, 2022 6:04 pm
Medallas: 3
Nivel: 3
Ubicación: Buenos Aires

Re: OFO 2023 Problema 10

Mensaje sin leer por fran :) »

Spoiler: mostrar
Mi solución es igual a la de @FabriATK pero menos violenta, y analizo el promedio en vez de la suma (analizar la suma probablemente hubiese sido más fácil)


Sea $a$ la cantidad de amistades entre muchachos en el grupo.
Sea $n$ la cantidad de muchachos en el grupo.
Para calcular el promedio de amistades, tenemos que sumar las amistades que tiene cada muchacho y dividirlas por la cantidad de muchachos. Como las amistades son mutuas, esto cuenta cada amistad que existe dos veces.

Entonces, $d = \frac{2a}{n}$ (y $\frac{d}{2} = \frac{a}{n}$)

Con el siguiente procedimiento Scaloni puede armar un grupo donde todos los muchachos están ilusionados.

Primero, mete a todos los muchachos en el grupo. En este grupo cada muchacho tiene un promedio de $d$ amigos.

Scaloni busca a algún muchacho con menos de $\frac{d}{2} = \frac{a}{n}$ amigos, y lo saca del grupo. Vamos a ver cómo queda el promedio de amigos en este caso. Sea $x < \frac{a}{n}$ la cantidad de amigos que tiene ese muchacho que sacamos.

Sean $a', n', d'$ los valores de $a, n, d$ para este nuevo grupo.

$a' = a - x$, porque eliminamos a todas las amistades que salían de ese muchacho.
$n' = n - 1$, porque sacamos a 1 muchacho.
$d' = \frac{2a'}{n'} = \frac{2(a-x)}{n-1}$
$d' > d$ si y solo si
$\frac{2(a-x)}{n-1} > \frac{2a}{n}$ si y solo si
$\frac{a-x}{n-1} > \frac{a}{n}$ si y solo si
$n(a-x) > (n-1)a$ si y solo si
$na - nx > na - a$ si y solo si
$- nx > - a$ si y solo si
$nx < a$ que es verdadero, porque $x < \frac{a}{n} \to nx < a$

Entonces $d' > d$ cuando Scaloni hace esto, lo que significa que el promedio de amigos de cada muchacho en el grupo aumenta.

Por lo tanto, lo que puede hacer Scaloni es repetir esto muchas veces.

Este procedimiento solo termina de dos maneras
  • No hay nadie con menos de $\frac{d}{2}$ amigos. Entonces este grupo cumple las condiciones del problema.
  • Solo queda una persona en el grupo, que no podemos sacar. Esta persona tiene cero amigos en el grupo, entonces $d' = 0$. Pero esto implica que $d$ originalmente era $0$, porque $d$ siempre aumenta. Entonces esta persona ya tiene por lo menos $\frac{d}{2} = 0$ amigos, entonces cumple con las condiciones del problema, y es imposible llegar a este caso sin llegar al caso anterior.
Entonces, Scaloni siempre puede armar un grupo donde todos los muchachos están ilusionados

lamentablemente, con este método los chicos que quedan afuera quedan doblemente desilusionados. primero porque Scaloni los había metido en el grupo (eso los ilusionó) y después los sacó, y segundo porque tienen menos de d/2 amigos en el grupo. pero cuando argentina ganó la tercera ya se volvieron a ilusionar, entonces como -2 + 1 = -1 los chicos que quedan afuera quedan solamente desilusionados 1 vez, como lo especifica el problema.
3  
$$\phantom{[muajajacaracteresinfinitos=}\begin{matrix}(λx.F\;a)&→&x=a;F\\(\{x_0\;x_1\}\;a)&→&\{a_0\;a_1\}=a;\{(x_0\;a_0)\;(x_1\;a_1)\}\\\{a_0\;a_1\}=\{b_0\;b_1\}&→&a_0=b_0;a_1=b_1\\\{a_0\;a_1\}=λx.F&→&x=\{x_0\;x_1\};\{f_0\;f_1\}=F;a_0=λx_0.f_0;a_1=λx_1.f_1\end{matrix}\phantom{]}$$
Responder