Problemas 22 de junio

1. Probar que existe una permutación $x_1, x_2, \ldots, x_{2014}, x_{2015}=x_1$ de $1,2, \ldots, 2014$ tal que, para todo $1 \le k \le 2014$ se tiene que

$ x_{k+1} \in \{ 2x_k, 2x_k-1, 2x_k-2014, 2x_k-2015 \}$.

2. Se tiene una gráfica de $n$ vértices tal que no existen cuatro vértices que todos se conocen entre sí (no hay $K_4$'s). Encontrar el máximo número posible de triángulos ($K_3$'s) que puede tener dicha gráfica.

3. (**) Para un natural $n$, sea $f(n)$ el mayor número posible de aristas que una gráfica de $n$ vértices puede tener si no tiene cuadrados. Probar que existen infinitos enteros $n$ tales que

$f(n) \ge \frac{n^{3/2}}{2}-n$.

(Un cuadrado es un conjunto de 4 vértices distintos $A,B,C,D$ tal que $AB, BC, CD$ y $DA$ son aristas).