Problema 18 junio 2013 JUAN

Pongo tres por que creo que no están difíciles, y los podrían haber visto.

PROBLEMA 1: En Combilandia, el combidiablo se enojó porque no pudo salir, y mandó un terremoto que destruyó 166 ciudades, de modo que solo quedaban 500 ciudades, y TODAS las calles quedaron destrozadas. Se construyeron nuevas calles, de modo que al final quedaron 2013 calles, todas de doble sentido. Dos ciudades  A y B son semivecinas si existe C tal que AC y CB son calles. Resulta que un matemático no puede caminar exactamente 4 calles (iniciando en una ciudad) y terminar en la misma ciudad en la  que inició. Demuestra que existe una ciudad en Combilandia que es semivecina de al menos 57 ciudades.

VERSIÓN CHAFA: Grafo simple (sin dobles aristas, no dirigido y sin aristas tipo V-V). 500 vértices, 2013 aristas. No hay ciclo de longitud 4. Muestra que hay un vértice A tal que existen al menos 57 otros vértices tales que existe un camino iniciando en A y terminando en ese vértice, de longitud 2.

PROBLEMA 2: Ana y Bruno juegan un juego. $P_n$ es el conjunto de los naturales $m$ que cumplen $p \in \mathbb{P}, p\textgreater 3 \Rightarrow v_p(m)=0$ y $v_3(m)+v_2(m)=n$. Si $X$ es un subconjunto de $P_n$, $S_X$ es la suma de los elementos de $X$. $S_{\{\}}=0$. Ana escoge un  número real $0 \le y \le 3^{n+1}-2^{n+1}$. Si Bruno encuentra un $Y$ subconjunto de $P_n$ tal que $0 \le y - S_Y \textless 2^n$, Bruno gana. De lo contrario, gana Ana. ¿Quién tiene estrategia ganadora?

PROBLEMA 3: $a,b,c$ reales positivos cuyas potencias cuartas suman a 3. Demuestra que $\sum_{cyc} \frac{1}{4-ab} \le 1$.