5 Una sucesión de círculos distintos $\omega_1, \omega_2, \cdots$ está inscrita en la parábola $y=x^2$ de modo que $\omega_n$ y $\omega_{n+1}$ son tangentes para todo $n$ . Si $\omega_1$ tiene diámetro $1$ y toca a la parábola en $(0,0)$ , halle el diámetro de $\omega_{1998}$ .

4 sí, tienes razón; el problema oficial es el siguiente: hay 1998 ciudades en Rusia, cada una conectada (en ambos sentidos) por vuelos con otras tres ciudades. cualquier ciudad puede ser alcanzada desde cualquier otra ciudad mediante una sucesión de vuelos. la KGB planea cerrar 200 ciudades, sin que dos de ellas estén unidas por un solo vuelo. demuestre que esto puede hacerse de modo que cualquier ciudad abierta pueda ser alcanzada desde cualquier otra ciudad abierta mediante una sucesión de vuelos que pase solo por ciudades abiertas. Solución. comenzamos con algo de terminología. definimos un trigrafo como un grafo no dirigido conexo en el que todo vértice tiene grado a lo sumo $ 3$ . un vértice trivalente de tal grafo es un vértice de grado $ 3$ . con esta formulación, el problema se convierte en: tenemos un trigrafo $ G$ con $ 1998$ vértices, todos ellos trivalentes. queremos eliminar $ 200$ vértices, sin que dos de ellos sean adyacentes, de modo que los vértices restantes permanezcan conexos. eliminamos los vértices uno a la vez. supongamos que hemos borrado $ k$ de los $ 1998$ vértices, sin que dos de ellos sean adyacentes, de modo que el trigrafo $ G'$ inducido por los vértices restantes sea conexo. mostraremos que si $ K < 200$ , siempre podemos borrar un vértice trivalente de $ G'$ de modo que el grafo permanezca conexo. este vértice no puede ser adyacente en $ G$ a ninguno de los otros $ k$ vértices borrados, porque entonces su grado en $ G'$ sería menor que $ 3$ . por lo tanto, repitiendo esto $ 200$ veces obtenemos el conjunto de vértices deseado. Lema. sea $ G$ un trigrafo tal que la eliminación de cualquier vértice trivalente desconecta a $ G$ . entonces $ G$ es plano. además, $ G$ puede dibujarse de tal manera que todo vértice se encuentre en la cara "exterior"; en otras palabras, para cualquier punto $ P$ exterior a algún conjunto acotado, cada vértice $ v$ de $ G$ puede unirse a $ P$ mediante una curva que no interseca ninguna arista de $ G$ (excepto en $ v$ ) . Demostración. hacemos inducción sobre el número de vértices trivalentes de $ G$ . si $ G$ no contiene ningún vértice trivalente, entonces $ G$ debe ser un camino o un ciclo y el enunciado es obvio. supongamos entonces que $ G$ contiene $ n\geq 1$ vértices trivalentes y que todo trigrafo con menos vértices trivalentes puede dibujarse como se ha descrito. si $ G$ es un árbol el enunciado es obvio, así que supongamos que $ G$ contiene un ciclo; sean $ v_1,\ldots ,v_k$ $ (k\geq 3)$ un ciclo minimal. sea $ S = \{v_1,\ldots ,v_k\}$ , y sea $ T = \{i\mid v_i \textrm{ is trivalent }\}$ . ( $ T$ no puede ser vacío, porque entonces ningún $ v_i$ estaría conectado a un vértice de grado $ 3$ . ) para cada $ i\in T$ , sea $ w_i$ el tercer vértice adyacente a $ v_i$ (distinto de $ v_{i - 1}$ y $ v_{i + 1}$ ) , y sea $ S_i$ el conjunto de vértices de $ G$ que pueden alcanzarse desde $ w_i$ sin pasar por $ S$ . (para $ i\not\in T$ , sea $ S_i = \emptyset$ . ) afirmamos que los conjuntos $ S,S_1,\ldots ,S_k$ particionan los vértices de $ G$ . primero, notemos que si $ v$ es un vértice de $ G$ que no está en $ S$ , entonces hay un camino más corto que une $ v$ con un vértice $ v_i$ de $ S$ ; el penúltimo vértice de este camino debe ser $ w_i$ , de modo que $ v\in S_i$ . ahora supongamos que $ v\in S_i\cap S_j$ para algún $ i\neq j$ ; entonces $ v_i$ y $ v_j$ son trivalentes y existen caminos $ w_i\to v$ , $ w_j\to v$ que no pasan por $ S$ . mostraremos que existe un camino desde todo vértice de $ G - \{v_i\}$ hasta $ v$ que no pasa por $ v_i$ . para $ k\neq i$ hay un camino $ v_k\to v_j\to w_j\to v$ ; si $ w\in S_k$ para $ k\neq i$ , entonces hay un camino $ w\to w_k\to v_k\to v$ ; si $ w\in S_i$ , hay un camino $ w\to w_i\to v$ . como $ S\cup S_1\cup\ldots\cup S_k = G$ , hemos mostrado que el grafo obtenido de $ G$ al borrar $ v_i$ es conexo, una contradicción, pues $ v_i$ es trivalente. por lo tanto $ S_i\cap S_j = \emptyset$ para $ i\neq j$ . obviamente $ S_i\cap S$ es vacío para todo $ i$ ; por lo tanto $ S,S_1,\ldots ,S_k$ particionan los vértices de $ G$ . sean $ G',G_1,\ldots ,G_k$ los subgrafos inducidos de $ S,S_1,\ldots ,S_k$ en $ G$ , respectivamente. por construcción, las únicas aristas de $ G$ que no están en ninguno de los grafos $ G',G_1,\ldots ,G_k$ son las aristas $ v_iw_i$ para $ i\in T$ . ahora $ G_i$ es un trigrafo con menos de $ n$ vértices trivalentes, ya que al menos uno de los $ n$ vértices trivalentes de $ G$ está en $ S$ . por lo tanto, por la hipótesis inductiva, podemos dibujar cada $ G_i$ en el plano de tal manera que todo vértice se encuentre en la cara exterior. como $ v_1,\ldots ,v_k$ era un ciclo minimal, no hay aristas "extra" entre estos vértices, de modo que el grafo $ G'$ es un $ k$ - ciclo. ahora coloquemos los vértices de $ S$ en los vértices de un pequeño $ k$ - gono regular lejos de todos los grafos $ G_i$ ; entonces podemos dibujar una curva que una cada par $ v_i,w_i$ . es fácil comprobar que esto nos da un dibujo de $ G$ con las propiedades deseadas. $ \square$ ahora supongamos que hemos eliminado $ k$ vértices de $ G$ , sin que dos de ellos sean adyacentes, de modo que el trigrafo $ G'$ inducido por los vértices restantes sea conexo, y supongamos que eliminar cualquier vértice trivalente de $ G'$ desconecta al grafo; debemos mostrar que $ k\geq 200$ . por el lema, $ G'$ es plano. llamaremos "cara propia" a toda cara distinta de la exterior. sea $ F$ el número de caras propias de $ G'$ ; como $ G'$ tiene $ 1998 - k$ vértices y $ 2997 - 3k$ aristas, $ F\geq 1 - (1998 - k) + (2997 - 3k) = 1000 - 2k$ . mostramos ahora que dos caras propias no pueden compartir un vértice. observemos que cada vértice pertenece a lo sumo a tantas caras como su grado; así, los vértices de grado $ 1$ están solo en la cara exterior. dos caras propias no pueden intersecarse en un vértice de grado $ 2$ , pues ese vértice no estaría en la cara exterior, contradiciendo el lema. si dos caras propias se intersecaran en un vértice trivalente $ v$ , cada cara daría un camino entre dos de los vecinos de $ v$ , de modo que eliminar $ v$ no desconectaría al grafo, por un argumento similar al del lema. como cada cara propia contiene al menos $ 3$ vértices y no hay dos que compartan un vértice, tenemos $ 3F\leq 1998 - k$ . combinando esto con la desigualdad anterior obtenemos $ 3000 - 6k\leq 3F\leq 1998 - k$ de modo que $ 1002\leq 5k$ y $ k\geq 200$ , como se deseaba. BaBaK

3 Se da en el plano un conjunto $\mathcal S$ de trasladados de un triángulo equilátero, y cualesquiera dos tienen intersección no vacía. Demuestre que existen tres puntos tales que todo triángulo de $\mathcal S$ contiene uno de estos puntos.

2 Sea $ABC$ un triángulo con circunferencia circunscrita $w$ . Sea $D$ el punto medio del arco $BC$ que contiene a $A$ . Defina $E$ y $F$ de manera análoga. Sea la circunferencia inscrita de $ABC$ tangente a $BC,CA,AB$ en $K,L,M$ respectivamente. Demuestre que $DK,EL,FM$ son concurrentes. stef

8 Cada casilla de un tablero $(2^n-1) \times (2^n-1)$ contiene $1$ o $-1$ . Tal disposición se llama exitosa si cada número es el producto de sus vecinos. Halle el número de disposiciones exitosas.

7 Sea n un entero al menos 4. En un n-ágono convexo, NO hay cuatro vértices que se encuentren sobre una misma circunferencia. Un círculo se llama circunscrito si pasa por 3 vértices del n-ágono y contiene a todos los demás vértices. Un círculo circunscrito se llama fronterizo si pasa por 3 vértices consecutivos; un círculo circunscrito se llama interior si pasa por 3 puntos dos a dos no consecutivos. Demuestre que el número de círculos fronterizos es 2 más que el número de círculos interiores.

6 Una operación binaria $*$ sobre los números reales tiene la propiedad de que $(a * b) * c = a+b+c$ para todo $a$ , $b$ , $c$ . Demuestre que $a * b = a+b$ .

5 Inicialmente los números $19$ y $98$ están escritos en un pizarrón. Cada minuto, cada uno de los dos números se eleva al cuadrado o se aumenta en $1$ . ¿Es posible obtener dos números iguales en algún momento?

4 Sea $k$ un entero positivo. Algunos de los subconjuntos de $2k$ elementos de un conjunto dado están marcados. Suponga que para cualquier subconjunto de cardinalidad menor o igual que $(k+1)^2$ , todos los subconjuntos marcados contenidos en él (si los hay) tienen un elemento común. Demuestre que todos los subconjuntos marcados tienen un elemento común.

3 En el triángulo escaleno $\triangle ABC$ , la tangente trazada desde el pie de la bisectriz del $\angle A$ a la circunferencia inscrita de $\triangle ABC$ , distinta de la recta $BC$ , toca a la circunferencia inscrita en el punto $K_a$ . Los puntos $K_b$ y $K_c$ se definen análogamente. Demuestre que las rectas que unen $K_a$ , $K_b$ , $K_c$ con los puntos medios de $BC$ , $CA$ , $AB$ , respectivamente, tienen un punto común sobre la circunferencia inscrita.