FOFO de Pascua 2017 - Problema 5

FOFO de Pascua 2017 - Problema 5

UNREAD_POSTpor Vladislao » Jue 13 Abr, 2017 4:45 am

Sean $x_1,\ldots,x_n$ números reales tales que su suma es igual a $1$. Demostrar que es posible distribuirlos alrededor de una circunferencia de modo tal que la suma de los $n$ productos de dos números vecinos sea menor o igual que $\frac{1}{n}$.
Sea $\theta = 1,3063778838...$ Para todo entero positivo $k$ se cumple que $\left\lfloor \theta^{3^k}\right\rfloor$ es un número primo.
Avatar de Usuario
Vladislao
 
Mensajes: 777
Registrado: Mar 28 Dic, 2010 3:26 pm
Ubicación: Córdoba
Medals: 6
Colaborador OFO - Jurado OFO - Jurado FOFO 6 años - Jurado
OFO - Jurado FOFO Pascua 2017 - Jurado
Nivel: Exolímpico

Re: FOFO de Pascua 2017 - Problema 5

UNREAD_POSTpor Gianni De Rico » Dom 16 Abr, 2017 8:31 pm

Spoiler: Mostrar
Vamos a demostrar que la mayor suma posible es $\frac {1}{n}$.

Primero que nada vemos que no es posible que entre los $n$ números haya algún ${x_y}\leq {0}$ ya que en ese caso por lo menos dos de los sumandos estarían restando o serían $0$. El único caso en el que habiendo un número negativo en el conjunto original ningún sumando resta se da cuando todos los $x$ son negativos, pero dado que su suma es igual a 1 eso no es posible.

Vamos a escribir todos los números como $\frac {1}{r}$ con $r$ real, por ejemplo, si tuivéramos el número $\frac {2}{3}$ lo escrbiríamos como $\frac {1}{1,5}$ que podemos ver son iguales. También veamos que para todo número $i$ irracional, $r=\frac{1}{i}$.
Es conocido que entre dos números $a$ y $b$, con $a+b=k$, el menor $ab$ posible se tendrá cuando $a=b\Rightarrow {ab={a^2}={b^2}}$. Por lo tanto, el mayor sumando que podemos obtener de dos números $\frac {1}{r_1}$ y $\frac {1}{r_2}$ se conseguirá cuando ${r_1}={r_2}$, ya que ${\frac {1}{r_1}}\times{\frac {1}{r_2}}={\frac {1}{r_1}}\times{\frac {1}{r_1}}={\frac {1}{{r_1}^2}}$. Sigue que ${r_y}={r_{y+1}}={n}$. Entonces estaremos sumando $n$ $veces$ ${\frac {1}{n^2}}={\frac {n}{n^2}}={\frac {1}{n}}$. Y como esta es la mayor suma posible, queda demostrado que no se podrán ordenar los números de forma que la suma sea mayor a $\frac {1}{n}$, que es lo que pide el problema.
$\phi=\frac {1+{\sqrt {5}}}{2}$
Avatar de Usuario
Gianni De Rico
 
Mensajes: 62
Registrado: Vie 16 Sep, 2016 6:58 pm
Ubicación: Rosario
Nivel: 3

Re: FOFO de Pascua 2017 - Problema 5

UNREAD_POSTpor davisbeckam18 » Dom 16 Abr, 2017 9:44 pm

Solución

Spoiler: Mostrar
Sean $x_1, x_2, ..., x_n$ números reales tales que su suma es igual 1. Procedamos por contradicción. Supongamos que sin importar cómo distribuyamos los $n$ números alrededor de una circunferencia, la suma de los $n$ productos de dos números vecinos siempre es mayor que $\frac{1}{n}$.

Hay un total de $(n-1)!$ formas de permutar los números alrededor de una circunferencia (pueden haber configuraciones repetidas en caso de que algunos valores de $x_i$ sean iguales). Como la suma de los $n$ productos en cada configuración es mayor que $\frac{1}{n}$, entonces al sumar las sumas de todas las permutaciones sería mayor que $\frac{(n-1)!}{n}$.

Pero como hay $(n-1)!$ configuraciones y $\frac{n(n-1)}{2}$ parejas, concluimos que cada pareja aparece un total de $2(n-2)!$ veces en total. De las dos conclusiones anteriores tenemos:

$2(n-2)!\sum_{i<j}x_ix_j>\frac{(n-1)!}{n}$



$\Leftrightarrow 2\sum_{i<j}x_ix_j>\frac{n-1}{n}$ $\Leftrightarrow \sum ^n_{i=1}x_i^2+2\sum_{i<j}x_ix_j>\sum ^n_{i=1}x_i^2+\frac{n-1}{n}$ $\Leftrightarrow (\sum ^n_{i=1}x_i)^2>\sum ^n_{i=1}x_i^2+\frac{n-1}{n}$


$\Leftrightarrow \frac {1}{n}>\sum ^n_{i=1}x_i^2$



Pero por $QM-AM$ : $\frac{\sum ^n_{i=1}x_i^2}{n}\geq (\frac{\sum ^n_{i=1}x_i}{n})^2$, que en nuestro problema equivale a $\sum ^n_{i=1}x_i^2 \geq \frac {1}{n}$. Juntando ambas expresiones llegamos a una contradicción la cual partió de afirmar que sin importar cómo distribuyamos los $n$ números alrededor de una circunferencia, la suma de los $n$ productos de dos números vecinos siempre es mayor que $\frac{1}{n}$.

Queda demostrado que existe una forma de distribuir los números alrededor de una circunferencia de tal forma que la suma de los $n$ productos de dos números vecinos sea menor o igual que $\frac {1}{n}$.

A MateoCV le gusta este mensaje.
Avatar de Usuario
davisbeckam18
 
Mensajes: 11
Registrado: Sab 17 Dic, 2016 8:57 pm
Medals: 2
OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla
Nivel: 2

Re: FOFO de Pascua 2017 - Problema 5

UNREAD_POSTpor jujumas » Dom 16 Abr, 2017 9:50 pm

Gianni De Rico escribió:
Spoiler: Mostrar
Vamos a demostrar que la mayor suma posible es $\frac {1}{n}$.

Primero que nada vemos que no es posible que entre los $n$ números haya algún ${x_y}\leq {0}$ ya que en ese caso por lo menos dos de los sumandos estarían restando o serían $0$. El único caso en el que habiendo un número negativo en el conjunto original ningún sumando resta se da cuando todos los $x$ son negativos, pero dado que su suma es igual a 1 eso no es posible.

Vamos a escribir todos los números como $\frac {1}{r}$ con $r$ real, por ejemplo, si tuivéramos el número $\frac {2}{3}$ lo escrbiríamos como $\frac {1}{1,5}$ que podemos ver son iguales. También veamos que para todo número $i$ irracional, $r=\frac{1}{i}$.
Es conocido que entre dos números $a$ y $b$, con $a+b=k$, el menor $ab$ posible se tendrá cuando $a=b\Rightarrow {ab={a^2}={b^2}}$. Por lo tanto, el mayor sumando que podemos obtener de dos números $\frac {1}{r_1}$ y $\frac {1}{r_2}$ se conseguirá cuando ${r_1}={r_2}$, ya que ${\frac {1}{r_1}}\times{\frac {1}{r_2}}={\frac {1}{r_1}}\times{\frac {1}{r_1}}={\frac {1}{{r_1}^2}}$. Sigue que ${r_y}={r_{y+1}}={n}$. Entonces estaremos sumando $n$ $veces$ ${\frac {1}{n^2}}={\frac {n}{n^2}}={\frac {1}{n}}$. Y como esta es la mayor suma posible, queda demostrado que no se podrán ordenar los números de forma que la suma sea mayor a $\frac {1}{n}$, que es lo que pide el problema.


En realidad es posible ordenar los números para alcanzar $\frac {1}{n}$. Basta con tomar de ejemplo los números $0.5$, $0,45$, $0,03$, $0,01$ y $0,01$ y ubicar $0,5$ y $0,45$ uno al lado del otro para obtener una suma mayor a $0,2$, ya que en particular su producto es mayor.

jujumas
 
Mensajes: 297
Registrado: Dom 26 Oct, 2014 8:30 pm
Medals: 5
OFO - Mención OFO - Medalla de Plata FOFO 6 años - Medalla Especial OFO - Oro perfecto
FOFO Pascua 2017 - Medalla
Nivel: 2

Re: FOFO de Pascua 2017 - Problema 5

UNREAD_POSTpor jujumas » Dom 16 Abr, 2017 9:52 pm

Solución:
Spoiler: Mostrar
Nota previa: Si $n=1$ la demostración es trivial. Para el caso $n=2$, cuando tomamos $(n-2)!$ tomamos simplemente $1$ (para evitar confusiones sobre el valor de $0!$). En la demostración no se menciona la posibilidad de que los reales sean negativos hasta el final, pero esto no cambia la demostración en si.

Sea $A$ una distribución de los números en la circunferencia, decimos que la suma de los $n$ productos de dos números vecinos es el "valor" de la distribución.

Supongamos que nuestros números en la circunferencia son $y_1$, $y_2$, $\dots$ $y_n$ de modo que dos términos consecutivos se consideren en el producto, al igual que $y_1$ y $y_n$. Notemos que tenemos $n!$ formas de poner las sucesiones $x_i$ e $y_i$ en correspondencia, por lo que existen $n!$ distribuciones.

Notemos que si demostramos que la suma de los valores de las $n!$ es menor o igual a $(n-1)!$ estamos, ya que esto implica por palomar que al menos una distribución tiene valor menor o igual a $\frac{1}{n}$, por lo que vamos a tratar de demostrar esto.

Notemos que por simetría, la cantidad de apariciones del sumando $x_ix_j$ para $i$ y $j$ cualesquiera es la misma para toda elección de $i$ y $j$ distintos. Para trabajar con comodidad, vamos a suponer que $x_ix_j$ y $x_jx_i$ son parejas distintas. Luego, $x_i$ puede estar en cualquiera de los $y_i$, $x_j$ esta determinado en función de donde esta $x_i$, y los otros $n-2$ reales pueden estar en cualquier lugar, por lo que $x_ix_j$ aparece un total de $n((n-2)!)$ veces. Luego, la suma de todos los productos que empiezan con $x_i$ resulta ser $n((n-2)!)(x_i(\sum x_j)$ para $j$ distinto de $i$, y como la suma de los $n$ números es $1$, tenemos que esto es igual a $n((n-2)!)(x_i(1-x_i))$.

Luego, la suma de todos los valores resulta ser $n((n-2)!)\sum_{i=1}^{n} x_i(1-x_i)$, que es igual a $n((n-2)!)(\sum_{i=1}^{n} x_i - \sum_{i=1}^{n} (x_i)^2)$, por lo que dividiendo por $(n-2)!$ queremos ver que $n(\sum_{i=1}^{n} x_i - \sum_{i=1}^{n} (x_i)^2) \leq n-1$.

Volviendo a usar que $\sum_{i=1}^{n} x_i=1$, tenemos que el problema se reduce a probar que $n-n(\sum_{i=1}^{n} (x_i)^2) \leq n-1$, que es equivalente a probar que $\sum_{i=1}^{n} (x_i)^2 \geq \frac{1}{n}$. Para esto usaremos la desigualdad entre la media cuadrática y la media aritmética, la cual también se mantiene con reales negativos (ya que al cambiar $x_i$ por $-x_i$ la media cuadrática se mantiene constante y la aritmética decrece), que nos dice que $\sqrt{\frac{\sum_{i=1}^{n} (x_i)^2}{n}} \geq \frac{\sum_{i=1}^{n} (x_i)}{n}$, que como $\sum_{i=1}^{n} (x_i)=1$, implica al elevar al cuadrado que $\frac{\sum_{i=1}^{n} (x_i)^2}{n} \geq \frac{1}{n^2}$, que multiplicado por $n$ nos da lo que queríamos demostrar.

A xyz le gusta este mensaje.

jujumas
 
Mensajes: 297
Registrado: Dom 26 Oct, 2014 8:30 pm
Medals: 5
OFO - Mención OFO - Medalla de Plata FOFO 6 años - Medalla Especial OFO - Oro perfecto
FOFO Pascua 2017 - Medalla
Nivel: 2


Volver a Problemas

¿Quién está conectado?

Usuarios navegando por este Foro: Google [Bot] y 2 invitados