Manual electrónico de matemáticas discretas. Foro científico dxdy. Teorema de la paridad del número de vértices impares

Hola, estoy usando este foro para probar la siguiente prueba. En general, este problema es, pero escuché que los escolares lo resuelven en la Olimpiada.

Una tarea.
Hay 100 ciudades en el país, algunos pares de ciudades están conectadas por carreteras. Para cuatro ciudades cualesquiera, hay al menos dos caminos entre ellas. Se sabe que no existe una ruta que pase por cada ciudad exactamente una vez.
Demuestre que es posible elegir dos ciudades de tal manera que cualquiera de las ciudades restantes esté conectada por una carretera con al menos una de las dos ciudades elegidas.

Prueba.
Las ciudades son cumbres. Las costillas son caminos.

Averigüe si la gráfica se puede desconectar. Si la componente es mayor que 3, entonces seleccionamos 2 vértices de uno, uno del otro y uno más del tercero. Resulta que pueden conectarse como máximo por un borde. Se viola la condición de la tarea.
Sean dos componentes, cada uno de los cuales consta de más de un vértice. Entonces deben estar completos. Si este no es el caso, entonces tomamos dos vértices no adyacentes del primero, dos cualesquiera del otro. Solo se pueden conectar dos ciudades en un conjunto de este tipo. Contradicción. Lo mismo para el otro componente. Así que ambos están completos. Bien, entonces tomamos cualquier vértice del primero y cualquiera del segundo componente. La condición de la tarea se cumple.
Deje ahora que un componente sea solo un vértice de grado 0. Entonces resulta que el otro componente será de 99 vértices. Si se eliminan más de dos aristas de cualquier vértice, la condición se viola inmediatamente: tomamos un vértice de grado 0, un vértice sin dos aristas y vértices para los que no hay aristas (habrá 1 arista). Esto significa que solo se puede eliminar un borde de cada vértice. Pero si haces esto, entonces cada vértice tendrá un grado impar (antes de eso, cada uno tenía 98). Y solo puede haber un número par de grados impares, así que eliminamos dos aristas en algún lugar y se viola la restricción de 4 ciudades, o dejamos todas las aristas y luego el vértice completo.

Llamemos a las ciudades desde las que hay caminos a todas las demás ciudades q y p.

A continuación, demostramos por inducción que para cualquier grafo conexo con una restricción de 4 ciudades y un r.path, la condición se cumplirá.
Base. de 4 vértices es obvio: tomamos cualquier árbol de expansión y elegimos un vértice que sea diferente de una hoja, y el segundo es una hoja.

Transición. Sea un gráfico de vértices. Entonces, para todos los gráficos más pequeños que el tamaño para el cual se satisface la condición del problema, todo está probado.

Necesitamos probar que podemos usar la hipótesis de inducción.
Llamemos al vértice que será expulsado como .
Si hay un gráfico desde arriba, donde para 4 ciudades debe haber dos caminos, entonces esto también debe ser cierto para las ciudades: consideraremos todas las ciudades sin uno. Lo principal es que el grafo no pierda conectividad, y esto siempre se puede hacer quitando solo el vértice colgante, si lo hay.

Si resulta que se formó un r.path en , entonces no se podría conectar a uno de sus extremos (de lo contrario, el r.path en el gráfico). Entonces, para la eliminación, este es un vértice colgante en el árbol de expansión. Si resultó que esto todavía es imposible: estaba conectado a través de un vértice al extremo que se eliminó, luego eliminamos el otro. Al mismo tiempo, no podría resultar que el vértice esté conectado a través de un vértice a ambos extremos: sería un gráfico en 3 vértices (y si hay un segundo camino hacia el final, entonces hay una r. camino), pero se prueba para grafos de más de 4 vértices.
Es obvio que a partir de la eliminación del vértice colgante en el árbol de expansión, la conectividad no se pierde.

Ahora se prueba que si hay algún grafo, se duplicó. condición, luego puede elegir un vértice, después de eliminarlo, se obtendrá un gráfico más pequeño que satisfaga la condición inicial. Entonces podemos usar la hipótesis de inducción.

Ahora hay , conectado a un gráfico de vértices, este país de ciudades tiene su propia p y q. Está claro que si hay una arista de to p o q, entonces no es necesario probar nada. Entonces que no haya caminos de p a q.
El conjunto al que hay caminos desde p se llamará A, y el conjunto al que hay caminos desde q se llamará B.
Que no haya camino de p a q. Entonces que la ciudad no esté conectada por carretera a la ciudad. Pero entonces debe tener caminos hacia p y q, de lo contrario tomamos los vértices , , p y q.
Entonces resulta que la ciudad no se puede conectar por carreteras con ciudades de
Pero luego puedes hacer de la ciudad una nueva p, y dejar q igual (o viceversa).

Por lo tanto, solo queda un caso: p y q están conectados por una carretera.
Dejamos los nombres de los conjuntos igual.
Por la hipótesis de inducción: el gráfico no tiene un camino hamiltoniano.
Una vez más, si hay caminos desde hacia el conjunto completo o hacia el conjunto completo, entonces todo ya está probado.

Ahora hay un par de vértices y , desde los cuales no hay aristas hasta .
Si solo hay , entonces todo lo que q no cubre, entonces p. Entonces - una nueva gran ciudad.
Si está vacío, entonces está conectado y todo está probado.

Si no hay arista entre y, entonces tomamos , y p - habrá una arista. Así es. Ahora resulta que es un subgrafo completo, sin embargo, así como (de lo contrario, tomamos o , p o q, si es necesario, y vértices inconexos).
Ahora considere un subgrafo en vértices de . Intentemos cubrir todo el conjunto de vértices de forma sencilla.
Deje que la cubierta se componga de solo 4 caminos simples. Tomemos un vértice extremo de cada uno: si hay un borde, entonces fue posible conectar dos vértices extremos y obtener un camino más largo. El resultado es una anti-camarilla en cuatro vértices. Contradicción.
Ahora sabemos que el conjunto está cubierto por 3 caminos simples como máximo. Consideraremos cada vértice simple como un vértice: si puede llegar a cualquiera de los extremos, puede pasar por cada vértice dentro de él una vez; es simple, pero puede hacerlo, porque cada vértice de puede ser alcanzado tanto por p como por q. Ahora solo hay como máximo 3 vértices.
Un camino puede tener uno o más vértices. Si es más, entonces identificamos todo el camino con su único vértice extremo.
Llamemos al conjunto izquierdo - , derecho - , medio - (los caminos se comprimen en vértices).
Podemos olvidarnos del vértice: si resulta que el i-path tiene, entonces ya habrá una contradicción con la hipótesis de inducción.
Caso 1. El conjunto del medio está vacío. Luego simplemente (simplemente a lo largo de los vértices) damos la vuelta al conjunto de la izquierda, comenzando desde cualquier vértice que no sea , terminamos en , luego en p , luego inmediatamente en q, luego en y simplemente damos la vuelta al conjunto de la derecha. Resultó ser un camino.
Caso 2. Hay un vértice en el conjunto medio. Todo es igual, pero de p a q pasamos por este vértice.
Caso 3. Ahora hay vértices en el conjunto medio

1. El tablero tiene forma de cruz, que se obtiene quitando los cuadrados de las esquinas del tablero cuadrado $4 \times 4$. ¿Es posible rodearlo con el movimiento del caballo de ajedrez y volver al campo original, habiendo visitado todos los campos exactamente una vez?
2. Hay 9 ciudades en el país de Digit con los nombres 1, 2, 3, 4, 5, 6, 7, 8, 9. Un viajero descubre que dos ciudades están conectadas por una aerolínea si y solo si los nombres de estas ciudades es divisible por 3. ¿Es posible ir de la ciudad 1 a la ciudad 9?
3. Hay 15 teléfonos en la ciudad de Chico. ¿Se pueden conectar por cables de modo que cada teléfono esté conectado exactamente a otros cinco?
4. Hay 100 ciudades en el estado, y de cada una salen 4 caminos. ¿Cuántas carreteras hay en el estado?
5. Hay 30 personas en la clase. ¿Será que 9 de ellos tienen 3 amigos (en esta clase), 11 tienen 4 amigos y 10 tienen 5 amigos?
6. Hay 15 teléfonos en la ciudad de Chico. ¿Se pueden conectar con cables de manera que haya 4 teléfonos, cada uno conectado a otros tres, 8 teléfonos, cada uno conectado a seis, y 3 teléfonos, cada uno conectado a otros cinco?
7. El rey tiene 19 barones vasallos. ¿Será que cada baronía vasalla tiene 1, 5 o 9 baronías vecinas?
8. ¿Puede haber exactamente 100 carreteras en un estado en el que salen 3 carreteras de cada ciudad?
9. John, habiendo llegado de Disneyland, dijo que hay 7 islas en el lago encantado, cada una de las cuales conduce a 1, 3 o 5 puentes. ¿Es cierto que al menos uno de estos puentes conduce necesariamente a la orilla del lago?
10. Demuestra que el número de personas que alguna vez vivieron en la Tierra y estrecharon la mano de un número impar es par.
11. ¿Es posible dibujar 9 segmentos en un plano de modo que cada uno se cruce exactamente con otros tres?
12. Hay 15 ciudades en el país de los Siete, cada una de las cuales está conectada por carreteras con al menos otras 7. Demuestre que es posible llegar de cualquier ciudad a cualquier otra (quizás pasando por otras ciudades).
13. Demuestra que un grafo con $n$ vértices, cada uno de grado al menos $(n - 1)/2$, es conexo.
14. En Far Far Away solo hay un modo de transporte: la alfombra voladora. Hay 21 líneas de alfombras que salen de la capital, una alfombra de la ciudad de Dalniy y 20 de todas las demás ciudades. Demuestre que es posible volar desde la capital a Dalniy (posiblemente con transferencias).
15. Hay 100 caminos que van desde cada ciudad del país, y desde cualquier ciudad puedes llegar a cualquier otra. Un camino estaba cerrado por reparaciones. Demuestra que incluso ahora es posible ir de cualquier ciudad a cualquier otra.
16. a) Dado un trozo de alambre de 120 cm de largo, ¿es posible, sin romper el alambre, hacer un marco de un cubo con una arista de 10 cm?
    b) ¿Cuál es el menor número de veces que se tendrá que romper el alambre para seguir haciendo el marco requerido?
17. Demuestra que un grafo en el que dos vértices cualesquiera están conectados por exactamente un camino simple es un árbol.
18. Demuestre que dos vértices cualesquiera de un árbol están conectados exactamente por un camino simple.
19. Demuestre que hay un vértice en el árbol del que sale exactamente un borde (dicho vértice se llama colgante).
20. Todos los vértices de la gráfica tienen grado 3. Demuestra que tiene un ciclo.
21. Demuestra que quitar cualquier borde de un árbol lo convierte en un gráfico desconectado.
22. Hay 101 ciudades en el país de Treeland, y algunas de ellas están conectadas por carreteras. Al mismo tiempo, exactamente un camino conecta dos ciudades cualesquiera. ¿Cuántas carreteras hay en este país?
23. Demostrar que un grafo conexo cuyo número de aristas es uno menos que el número de vértices es un árbol.
24. La red de voleibol parece un rectángulo de $50 \times 600$ cuadrados. ¿Cuál es el mayor número de hilos que se pueden cortar sin que la red se deshaga?
25. Hay 30 ciudades en un determinado país, cada una conectada a cada carretera. ¿Cuál es el mayor número de caminos que se pueden cerrar por reparaciones para que sea posible viajar de cada ciudad a cada una?
26. Demostrar que en cualquier grafo conexo es posible quitar un vértice junto con todas las aristas que salen de él para que permanezca conexo.
27. Hay 100 ciudades en el país, algunas de las cuales están conectadas por líneas aéreas. Se sabe que desde cualquier ciudad se puede volar a cualquier otra (posiblemente con transbordos). Demuestra que es posible visitar todas las ciudades con no más de
    a) 198 vuelos;
    b) 196 vuelos.
28. Hay 7 lagos en el país de Ozernaya, interconectados por 10 canales, y de cualquier lago puedes nadar a cualquier otro. ¿Cuántas islas hay en este país?
29. Se marcaron 20 puntos en el cuadrado y se conectaron entre sí y con los vértices del cuadrado entre sí y con los vértices del cuadrado para que el cuadrado se dividiera en triángulos. ¿Cuántos triángulos obtuviste?
30. Un grafo que tiene 5 vértices, cada uno de los cuales está conectado por una arista a cualquier otro, no es plano.
31. ¿Es posible construir tres casas, cavar tres pozos y conectar caminos de cada casa a cada pozo para que los caminos no se crucen?
32. Demostrar que un grafo con 10 vértices, cada uno de grado 5, no es plano.
33. Demostrar que la gráfica plana tiene un vértice cuyo grado no excede de 5.
34. Cada borde de un gráfico completo con 11 vértices está coloreado en uno de dos colores: rojo o azul. Demuestre que el gráfico "rojo" o "azul" no es plano.
35. El heptágono se divide en pentágonos y hexágonos convexos de tal forma que cada uno de sus vértices es vértice de al menos dos polígonos del tabique. Demuestra que el número de pentágonos en la partición es al menos 13.

2. Resuelva el siguiente problema de recorrido de grafos:

Algún país tiene una capital y otras 100 ciudades. Algunas ciudades (incluida la capital) están conectadas por carreteras de un solo sentido. Hay 20 caminos que salen de cada ciudad no capital y 21 caminos que ingresan a cada ciudad no capital. Demuestra que es imposible llegar a la capital desde cualquier ciudad.

Que un camino entre en la capital. Entonces el número total de caminos "entrantes" es igual a 21 100 + a , y el número total de caminos "salientes" es como máximo

20 100 + (100-a). Por lo tanto, 21 100 + a 20 100 + (100 - a), es decir, 2a 0.

Entonces a = 0.

3.3.2.1. El dígrafo G1 (V,E): V=(a, b, c, d, e, f), se define como un sistema algebraico.

a) Para la relación reducida, defina un dígrafo geométricamente. b) Construya la matriz de adyacencia del dígrafo.

0) R = ((a, b), (b, a), (b, c), (c, b), (c, a), (a, c), (d, e), (e, d) );

1) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (c, a), (a, c) );

2) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (d, e), (e, d) );

3) R = ((a, b), (b, c), (a, c), (b, e), (c, f), (c, d), (d, f), (f, e) );

4) R = ((b, c), (a, d), (b, a), (d, c), (b, d), (c, a), (f, d), (f ,c) );

5) R = ((b, a), (a, a), (b, c), (c, d), (d, c), (d, b), (d, a), (d, e) );

6) R = ((a, b), (a, c), (a, d), (c, a), (d, e), (e, d), (c, c), (d, b) );

7) R=((b, a), (c, c), (a, d), (c, a), (d, e), (e, c), (d, b), (e, f) );

8) R = ((a, b), (a, c), (a, d), (e, a), (d, e), (e, d), (c, b), (d, d) );

9) R = ((a, e), (a, a), (a, d), (c, a), (d, e), (d, d), (c, c), (b, d) ).

3.3.2.2. El dígrafo se da geométricamente. Especifique la valencia de los vértices.

8) 1

3.3.2.3. Se da la matriz de adyacencia de un dígrafo. a) Especificar un dígrafo geométricamente, c) construir una matriz de incidencia.

        

001100

001000

3.3.2.4. Se da la matriz de incidencia de un dígrafo. a) Especificar un dígrafo geométricamente, c) construir una matriz de adyacencia.

3.3.2.5. Resuelve los siguientes problemas de recorrido de grafos:

0) Dima, habiendo llegado de Vrunland, dijo que allí hay varios lagos, interconectados por ríos. Tres ríos fluyen de cada lago y cuatro ríos desembocan en cada lago. Demuestra que está equivocado.

1) En algún estado, cada ciudad está conectada a cada camino. El rey loco quiere introducir el tráfico de un solo sentido en las carreteras para que, habiendo salido de cualquier ciudad, sea imposible volver a ella. ¿Es posible hacerlo?

2) Se dice que en una empresa de cinco personas cada uno conoce a otros dos. ¿Es posible una empresa así?

3) Hay 101 ciudades en un determinado estado. Todas las ciudades están conectadas por caminos de sentido único, con 50 caminos que entran a cada ciudad y 50 caminos que salen de cada ciudad. Demuestre que es posible llegar de cualquier ciudad a cualquier otra conduciendo como máximo por dos caminos.

4) Se dan 6 puntos en un plano de modo que tres de ellos no estén en la misma línea recta. Cada par de puntos está conectado por una línea azul o roja. Demostrar que entre los puntos dados es posible elegir tres de modo que todos los lados del triángulo formado por ellos estén coloreados del mismo color.

5) Hay 101 ciudades en un determinado estado. Algunas ciudades están conectadas por caminos de un solo sentido, con 40 caminos que ingresan a cada ciudad y 40 caminos que salen de cada ciudad. Demuestre que es posible llegar de cualquier ciudad a cualquier otra conduciendo no más de tres caminos.

6) ¿Es posible dibujar 10 rutas de autobús en la ciudad y establecer paradas en ellas de modo que, independientemente de las 8 rutas que se tomen, haya una parada que no se encuentre en ninguna de ellas, y 9 rutas cualesquiera pasen por todas las paradas?

7) El escarabajo se arrastra por los bordes del cubo. ¿Puede atravesar todos los bordes secuencialmente, recorriendo cada borde exactamente una vez? Pista: piensa en la pregunta: ¿cuántas veces puede un escarabajo visitar cada vértice?

8) El artista pintó un cuadro "El contorno de un cuadrado y sus diagonales". ¿Podría hacer su dibujo sin quitar el lápiz del papel y dibujar la misma línea dos veces? Sugerencia: de cada punto, con la excepción del principio y el final del recorrido del lápiz, debe emanar un número par de líneas.

9) Arkadi, Boris. Vladimir, Grigory y Dmitry se dieron la mano en la reunión (cada uno se dio la mano con cada uno una vez). ¿Cuántos apretones de manos se dieron en total?

3.3.2.6. Resuelve los siguientes problemas de recorrido de grafos:

0) El metro de Uryupinsk consta de tres líneas y tiene al menos dos estaciones terminales y al menos dos centros de transferencia, y ninguna de las estaciones terminales es una estación de transferencia. Puede pasar de una línea a otra en al menos dos lugares. Dibuja un ejemplo de un mapa de metro de este tipo, si sabes que se puede hacer sin levantar el lápiz del papel y sin dibujar el mismo segmento dos veces. Pista: no olvides que hay líneas de llamada.

3) El tablero tiene forma de cruz, que se obtiene quitando las celdas de las esquinas de un tablero cuadrado de 4 × 4. ¿Es posible rodearlo con el movimiento del caballo de ajedrez y volver al campo original, habiendo visitado todos los campos exactamente una vez?

4) Un peatón caminó por seis calles de una ciudad, pasando cada una exactamente dos veces, pero no pudo sortearlas, pasando cada una solo una vez. ¿Podría ser?

5) Un escarabajo se sienta en el centro del cubo 3 3 3. Demuestre que, mientras se arrastra por los bordes, no podrá dar la vuelta a todos los cubos 1 1 1 una vez.

6) Se marcan varias celdas en un cuadrado de 6×6 para que se pueda ir de una marcada a otra marcada, pasando únicamente por los lados comunes de las celdas marcadas. Una celda marcada se llama terminal si limita por el lado exactamente una marcada. Marque varias celdas para obtener a) 10, b) 11, c) 12 celdas.

7) Una mosca se posa en uno de los vértices de a) un octaedro b) un cubo. ¿Puede gatear sobre todas sus costillas exactamente una vez y volver a

tapa original? (Nota: un octaedro son dos pirámides cuadrangulares pegadas en las bases).

8) ¿Cómo, sin levantar el lápiz del papel, dibujar seis segmentos de tal manera que se tachen 16 puntos ubicados en los vértices de una cuadrícula de 4 por 4 cuadrados?

9) ¿Es posible dibujar una diagonal en cada cuadrado en la superficie del cubo de Rubik para obtener un camino que no se corte a sí mismo? Pista: hay 54 cuadrados en la superficie de un cubo de Rubik.

3.4. Problemas de optimización de grafos

Si un arco de un grafo dirigido G 1 (V ,E) está asociado con algún número real a (u ,v ), llamado peso, entonces la secuencia de vértices v 0 ,v 1 ,...,vp define un camino a G 1 y su longitud

definida como la suma de los pesos:

Si en forma arbitraria

columna, el peso de cada arco es igual a uno, entonces la longitud del camino es igual al número de arcos. El problema del camino más corto surge con mayor frecuencia al resolver

transporte y problemas discretos programación dinámica etc. La longitud del camino más corto se denota por r (v i ,v j ) y se llama la distancia de vi a v j (la distancia puede ser negativa). Para cualquier dígrafo, uno puede construir matriz de distancia R=r(i, j). La matriz se llena fila por fila, seleccionando el vértice de la izquierda (derecha). El valor es el menor número de arcos que conectan el vértice izquierdo con uno de los vértices de la fila.

Si no hay un camino de vi a v j , entonces establecemos r (v i ,v j ) = . Si cada contorno de nuestro gráfico tiene una longitud positiva, entonces el camino más corto siempre será un camino elemental, es decir no habrá repeticiones en la secuencia v 1 ,...,v p.

La desviación media del vértice vi del centro del gráfico D(vi ) es igual a:

D(vi )1 r(vi , v),

m v v

donde m - el número de arcos en el gráfico, v - pasa por los vértices del gráfico, n - el número de vértices del gráfico, i = 1..n.

El vértice para el que D(vi ) resulta ser mínimo se denomina centro del gráfico (son posibles varios vértices: el centro del gráfico).

camino o ruta en un grafo G1 (V,E) es una secuencia de sus vértices y aristas v1e1v2e2v3…vnen vn+1 en la que

dos elementos cualesquiera adyacentes son incidentes. Un camino se dice simple si la plata y todos sus vértices, excepto el primero y el último, son diferentes.

Una ruta se llama cadena si todos sus bordes son distintos. Una ruta se llama camino simple si todos sus vértices, y por lo tanto los bordes, son diferentes.

Un ciclo en un grafo es un camino en el que el vértice inicial coincide con el vértice final y que contiene al menos una arista.

Un ciclo se llama simple si no tiene vértices idénticos, excepto el primero y el último, es decir si los vértices son diferentes.

Si no hay ciclos en el gráfico, entonces se llama acíclico.

Ahora podemos definir el concepto de árbol de manera diferente. Un grafo conexo sin ciclos se llama árbol.

Ejemplos de completar tareas

D(2)=D(3)=6/8=3/4;

Entonces, el centro del gráfico son los vértices 2 y 3.

2. El pueblo está construido en forma de cuadrado de 3 manzanas por 3 manzanas (las manzanas son cuadrados de lado b, 9 manzanas en total). (Los lados de la plaza también son calles).

Arroz. 6. Atajo

Es claro que la longitud del recorrido del adoquín es de al menos 24, ya que debe pasar por cada calle al menos una vez. Probemos que tendrá que pasar por lo menos cuatro calles dos veces. Un número impar de calles se cruzan exactamente en ocho intersecciones.

Por lo tanto, cualquier ruta circular de adoquines debe pasar dos veces por lo menos 8/2 = 4 calles.La longitud mínima de una ruta de adoquines es de 28; una de las rutas posibles se muestra en la Figura 6.

3. Establezca el gráfico geométricamente y resuelva el problema:

Después de salir corriendo al patio después de la escuela, cada estudiante arrojó una bola de nieve exactamente a otro estudiante. Demuestre que todos los estudiantes se pueden dividir en tres equipos para que los miembros de un equipo no se lancen bolas de nieve entre sí.

Marcamos a los escolares en el avión con puntos y los conectamos con una flecha si uno arrojó al segundo. La imagen resultante se verá como varios ciclos con "cuernos" (caminos que conducen de un punto a un ciclo). Cada una de estas figuras se puede dividir fácilmente en tres grupos: rompiendo el ciclo, asignamos un estudiante al primer grupo y dividimos los árboles resultantes en vértices pares e impares.

Tareas para la autorrealización

3.4.1. Escriba: 1) cualquier camino que no sea una cadena; 2) cadena y cadena simple; 3) bucle, bucle simple, si lo hubiere.

3.4.2. El dígrafo se da geométricamente. Construya una matriz de distancia. Calcular el centro del dígrafo.

GRÁFICOS DE EULER.

Demuestre que se puede colocar un juego completo de fichas de dominó de acuerdo con las reglas del dominó.

"Lema sobre bailes redondos". En alguna empresa, cada persona tiene exactamente dos amigos. Demuestre que si todos los amigos se dan la mano, forman uno o más bailes redondos.

Hay más de 101 ciudades en el país. La capital está conectada por líneas aéreas con 100 ciudades, y todas las ciudades excepto la capital están conectadas con exactamente diez ciudades (la línea aérea opera en ambas direcciones). Se sabe que desde cualquier ciudad se puede llegar a cualquier otra (quizás con transbordos). Demostrar que es posible cerrar la mitad de las líneas aéreas que vienen de la capital, por lo que quedará la oportunidad de ir de cualquier ciudad a cualquier.

Demuestra que se puede dibujar un gráfico conexo con 2n vértices impares quitando el lápiz del papel exactamente n–1 veces y sin dibujar ninguna arista dos veces.

Hay 3 ferrocarriles que salen de cada ciudad del país. Dos empresas quieren privatizarlos a todos. El Comité Antimonopolio exige que las carreteras de ambas empresas salgan de cada ciudad. Acreditar que las empresas pueden ponerse de acuerdo entre sí para que se cumpla el requerimiento del Comité Antimonopolio.

Dado un grafo conexo G con k aristas. Demuestre que es posible enumerar las aristas con todos los números 1, 2, ..., k de modo que para cada vértice de grado al menos dos, el conjunto de números que etiquetan las aristas de este vértice tiene mcd igual a 1.

En un torneo de fútbol realizado entre 20 equipos de diferentes ciudades, cada equipo jugó un partido en casa y no más de dos partidos fuera. Demuestre que fue posible organizar el calendario de juegos de modo que cada equipo no jugara más de un juego por día y que todo el torneo se llevara a cabo en tres días.

GRÁFICO DE HAMILTON.

En la superficie del cubo se dibuja una polilínea cerrada de ocho secciones, cuyos vértices coinciden con todos los vértices del cubo. ¿Cuál es el menor número de enlaces de esta polilínea que pueden coincidir con las aristas del cubo?

Un cubo está formado por ocho cubos pequeños. ¿Es posible, partiendo del centro del cubo grande y desplazándose por las aristas de los cubos pequeños, dar la vuelta a todos los vértices de los cubos pequeños, visitando cada uno exactamente una vez?

Tablero dado 55. ¿Puede el caballero dar la vuelta a todas las celdas, visitar cada una una vez y volver a su posición original?

¿Puede un rey cojo (un rey que no puede moverse en diagonal) dar la vuelta a todas las celdas del tablero, comenzando en la esquina inferior izquierda y terminando en la esquina superior derecha?

¿Puede el caballo hacer 8 movimientos y volver a su casilla original, habiendo visitado todas las horizontales y verticales del tablero de ajedrez?

pero). Las fichas blancas y negras se colocan en dos celdas del tablero de ajedrez. Está permitido moverlos por turnos, cada movimiento desplazando la siguiente ficha a cualquier campo adyacente libre vertical u horizontalmente. ¿Pueden todas las posiciones posibles de estas dos piezas coincidir en el tablero como resultado de tales movimientos exactamente una vez? B). ¿Y si está permitido mover las fichas en cualquier orden (no necesariamente por turnos)?

¿Cuál de los siguientes tres hechos es el más "fuerte"?

En algún estado, cada 2 ciudades están conectadas por una carretera. Solo se permite una dirección en cada carretera. Demostrar que existe una ciudad desde la cual es posible viajar por todo el estado, habiendo visitado cada ciudad exactamente 1 vez.

En algún país, todas las ciudades están conectadas a todas las carreteras de sentido único. Demuestra que hay una ciudad desde la que puedes llegar a cualquier otra.

Hay 100 ciudades en un determinado estado, y cada una está conectada a cada carretera de sentido único. Demuestre que es posible cambiar la dirección del movimiento en una carretera para que sea posible ir de cualquier ciudad a cualquier otra.

Demuestre el hecho más "fuerte" y sus dos corolarios.

En un torneo de ajedrez de una ronda, cada participante jugó un juego con cada uno. Demuestre que los participantes se pueden numerar de tal manera que nadie pierda directamente contra el siguiente jugador numerado.

Hay N ciudades en el país. Entre dos cualesquiera de ellos, se coloca una carretera o un ferrocarril. Un turista quiere viajar por el país, habiendo visitado cada ciudad exactamente una vez, y regresar a la ciudad desde la que inició su viaje. Demostrar que el turista puede elegir la ciudad desde la que iniciará su viaje y la ruta de tal forma que tenga que cambiar de modo de transporte como máximo una vez. (Olimpiada de toda Rusia, 2003)

Una secuencia de 36 ceros y unos comienza con 5 ceros. Entre los cinco números consecutivos, existen las 32 combinaciones posibles. Encuentra los últimos cinco dígitos de la secuencia.

"Caballeros en la corte del Rey Arturo" - Teorema de Dirac. Hay 2n caballeros en la mesa redonda del Rey Arturo, cada uno de los cuales no tiene más de (n–1) enemigos entre los demás. Demuestra que el consejero del rey, Merlín, puede sentar a los caballeros de tal manera que los enemigos no se sienten uno al lado del otro. Formule el teorema de Dirac en forma general.

2n personas asistieron a la conferencia, cada una de las cuales conoce al menos a otras n. Demostrar que los participantes pueden alojarse en habitaciones dobles de tal manera que en cada habitación vivan personas que se conocen.

Te dan n fichas de varios colores, y no hay más de n/2 fichas de cada color. Demuestra que se pueden colocar en un círculo de tal manera que no queden dos piezas del mismo color una al lado de la otra.

En un estado federal de dos repúblicas, cada dos ciudades están conectadas por una carretera de sentido único; al mismo tiempo, moviéndose por las carreteras, puede ir de cualquier ciudad a cualquier otra. Ofertas de la agencia de viajes "Hamilton" norte diversas rutas turísticas por las ciudades de la primera república y metro- por ciudades de la segunda (cualquiera de estas rutas implica visitar cada ciudad de la república exactamente una vez y regresar a la ciudad de origen, y todo ello sin salir de la república). Demostrar que la Agencia Hamilton podría ofrecer nada menos que Minnesota rutas turísticas similares por las ciudades de toda la federación.

Los torneos son gráficos completos.

Hay 28 estudiantes en la clase. El maestro puede transferir estudiantes, pero cada estudiante se sienta con el mismo estudiante durante el día escolar. ¿Cuál es el menor número de días que cada estudiante podrá sentarse juntos?

La suma de 1000 números reales es 0. Demuestra que al menos 999 sumas por pares de estos números no son negativas.

Hay 25 piedras en una pila. Se divide en dos partes, luego una de las partes se vuelve a dividir en dos, etc., hasta obtener 25 piedras tumbadas por separado. Cada vez que uno de los montones se divide en dos partes, se escribe en la pizarra el producto del número de piedras en estas partes. Demuestra que al final la suma de todos los números de la pizarra será 300.

Hay 1996 niños estudiando en la escuela. Cada uno de ellos como exactamente k de los estudiantes restantes de 1995. ¿A qué valores k¿Se puede argumentar que seguramente habrá dos estudiantes de esta escuela que se agraden o que no se agraden?

El astrónomo observa 50 estrellas, la suma de las distancias entre pares es igual a S. Una nube subió y cubrió 25 estrellas. Demuestre que la suma de las distancias por pares entre las estrellas visibles es menor que S/2.

En un país con 25 ciudades, tres aerolíneas quieren que para cualquier par de ciudades, todos los vuelos sin escalas entre estas ciudades sean operados por una sola de las aerolíneas, pero cualquier aerolínea puede llevar pasajeros de cualquier ciudad a cualquier otra con una escala en no más de una ciudad intermedia. Demuestra que se puede hacer.

La comisión está formada por 49 personas. Exactamente tres miembros de la comisión participan en cada reunión. ¿Es posible programar el trabajo de la comisión de modo que dos miembros de la comisión se reúnan exactamente una vez?

CONECTIVIDAD MÍNIMA.

En la ciudad de N, desde cualquier estación de metro puedes ir a cualquier otra (posiblemente con transbordos). Demostrar que una de las estaciones de metro se puede cerrar por reparaciones sin derecho a transitar por ella para que se pueda llegar de cualquiera de las estaciones restantes a cualquier otra.

Demostrar que en cualquier grafo conexo es posible quitar un vértice junto con todas las aristas que salen de él para que permanezca conexo.

En un grupo de varias personas, algunas personas se conocen y otras no. Cada noche, uno de ellos organiza una cena para todos sus amigos y se los presenta. Después de que cada persona organizó al menos una cena, resultó que dos personas aún no se conocían. Demuestra que en la próxima cena tampoco podrán verse.

Hay 30 ciudades en un país, y cada ciudad está conectada a cada carretera. ¿Cuál es el número máximo de caminos que se pueden cerrar por reparaciones para que uno pueda viajar de una ciudad a otra, posiblemente pasando por otras ciudades?

Un modelo de un triángulo de once lados está hecho de alambre, desde un vértice del cual se dibujan todas las diagonales. Los dos se turnan para comer un cable a la vez. El ganador es aquel después del cual el modelo primero se divide en dos partes. ¿Quién gana cuando se juega correctamente: el que mueve primero o su compañero?

Inicialmente, hay una ficha en cada campo del tablero 1n. Se permite el primer movimiento para mover cualquier ficha a una celda adyacente (una de las dos, si la ficha no está en el borde), de modo que se forme una columna de dos fichas. Luego, con el siguiente movimiento, cada columna se puede mover en cualquier dirección tantas celdas como fichas haya en ella (dentro del tablero); si la columna toca una celda que no está vacía, se coloca encima de la columna que está allí y se fusiona con ella. Demuestre que en n-1 movimientos es posible juntar todas las fichas en una casilla.

Hay 101 latas de comida enlatada que pesan 1001 g, 1002 g, ..., 1101 g Las etiquetas con los pesos se pierden, pero al gerente de abastecimiento le parece que recuerda qué lata pesa cuánto. Quiere comprobar esto en el menor número de pesajes. Hay dos escalas de pan: una es precisa, la otra es gruesa. Se pueden comparar dos latas en un pesaje. Las escalas precisas siempre muestran qué frasco es más pesado y las escalas aproximadas, solo si la diferencia es más de 1 g (de lo contrario, muestran el equilibrio). El administrador de suministros solo puede usar una balanza. ¿Cuál debería elegir? (A.Shapovalov)

La red de voleibol tiene la forma de un rectángulo con un tamaño de 50600 celdas. ¿Cuál es el mayor número de cuerdas simples (entre nudos) que se pueden cortar para que la malla no se rompa en pedazos?

Hay una cuadrícula de cuerdas en forma de un cuadrado de 8x8 dividido en celdas de 1x1. ¿Cuál es la cuerda más larga que puedes cortar? (Se puede cortar cualquier extremo de los nudos sin romper la conexión de los demás, pero no se puede cortar un nudo para que no se formen extremos).

La hoja del cuaderno fue pintada en 23 colores por celdas. Un par de colores se considera bueno si hay dos celdas vecinas en el lado que están llenas de estos colores. ¿Cuál es el número mínimo de buenos pares?

Llamemos a un laberinto un tablero de ajedrez de 8x8, donde se insertan particiones entre algunos campos. Si la torre puede dar la vuelta a todos los cuadrados sin saltar sobre las particiones, entonces el laberinto se llama bueno, de lo contrario se llama malo. ¿Qué laberintos son más buenos o malos?

Hay 100 ciudades en el país, algunas de las cuales están conectadas por líneas aéreas. Se sabe que desde cualquier ciudad se puede volar a cualquier otra (posiblemente con transbordos). Demostrar que es posible visitar todas las ciudades haciendo como máximo: a). 198 vuelos; B). 196 vuelos.

En un tablero de ajedrez, inicialmente vacío, los peones se colocan de acuerdo con las siguientes reglas: se seleccionan cuatro celdas vacías, cuyos centros son los vértices de un rectángulo con lados paralelos a los lados del tablero, después de lo cual se coloca un peón en una de estas celdas. Luego se seleccionan cuatro celdas vacías similares, se coloca nuevamente un peón en una de ellas, y así sucesivamente. ¿Cuál es el mayor número de peones que se pueden colocar en el tablero siguiendo estas reglas?

La anfitriona horneó un pastel para los invitados. Puede haber p o q personas en la mesa. ¿Cuál es el número mínimo de piezas (no necesariamente iguales) que debe cortarse previamente la tarta para que en todo caso pueda repartirse equitativamente entre los invitados si: a). pyq son coprimos; B). p y q tienen el máximo común divisor d?

El objeto secreto es un cuadrado de 8x8 en planta, dividido por pasillos en cuadrados de 1x1. En cada vértice de dicho cuadrado hay un interruptor. Al hacer clic en el interruptor, se actúa inmediatamente sobre todos los corredores de un metro de largo que emergen de este vértice, cambiando su iluminación a los opuestos. El vigilante está en la esquina de un objeto completamente sin luz. Solo puede caminar en pasillos iluminados y accionar interruptores cualquier número de veces. ¿Puede el vigilante permitirle pasar de un interruptor a otro sin accionar los interruptores?

En un grafo conexo 2 norte vértices, y todos ellos son de grado 3. Demostrar que es posible elegir norte+1 borde, de modo que la coloración correcta de 3 colores de los bordes seleccionados especifica de forma única la coloración correcta de 3 colores de todos los bordes del gráfico (la coloración es correcta si dos bordes con un vértice común tienen colores diferentes).

GRÁFICOS BIPARTITOS.

Demuestre que un grafo es bipartito si y solo si todos los ciclos en él son pares.

Demuestra que un árbol (un grafo conexo sin ciclos) es un grafo bipartito.

En cierto grupo de personas, todos tienen un enemigo y un amigo. Demostrar que estas personas se pueden dividir en dos compañías para que cada compañía no tenga enemigos ni amigos.

16 equipos juegan en el Campeonato Ruso de Fútbol. En la primera ronda, todos los equipos jugaron un partido cada uno. En la segunda ronda, todos los equipos también jugaron un partido. Demuestre que es posible nombrar 8 equipos tales que ninguno de ellos juegue entre sí.

Se marca un conjunto finito M de nodos en una hoja de papel cuadriculado. ¿Siempre es posible colorear algunos puntos del conjunto M de blanco y el resto de rojo, de modo que en cada línea de cuadrícula la diferencia entre el número de nodos blancos y rojos no exceda de 1 en valor absoluto? (OMI, 1986)

Se dan 1997 puntos en el avión. Dos personas se turnan para conectar estos puntos con segmentos, y un segmento no se puede dibujar dos veces. El perdedor es aquel después del cual se forma por primera vez una línea discontinua cerrada con un número impar de enlaces. ¿Quién gana con la jugada correcta?

Se tomaron 10 puntos en el círculo. ¿Cuál es el mayor número de segmentos con extremos en estos puntos que se pueden dibujar para que tres de estos segmentos no formen un triángulo con vértices en estos puntos?

En el pueblo de Martyshkino, cada chico conoce a todas las chicas que conoce. Cada niña entre sus conocidos tiene más niños que niñas. Demuestra que en Martyshkino no hay menos niños que niñas.

Las hidras están formadas por cabezas y cuellos (cualquier cuello conecta exactamente dos cabezas). Un golpe de espada puede cortar todos los cuellos que salen de alguna cabeza A de la hidra. Pero al mismo tiempo, un cuello crece instantáneamente desde la cabeza de A hacia todas las cabezas con las que A no está conectado. Hércules derrota a la hidra si logra cortarla en dos partes que no están conectadas por sus cuellos. Encuentre la N más pequeña tal que Hércules pueda derrotar a cualquier hidra de 100 cuellos con N golpes como máximo. (RosOl, 2002)

En una empresa de 2n+1 personas, para cualquier n personas, hay una persona diferente que conoce a cada una de ellas. Demuestra que hay una persona en esta empresa que conoce a todos. (RosOl, 2002)

GRÁFICOS PLANOS.

Hay 5 puntos en un plano, de los cuales tres no están en la misma línea recta. Demostrar que unos cuatro de ellos se encuentran en los vértices de un cuadrilátero convexo.

Hay 5 círculos en el plano, cada dos de los cuales se cruzan. Demuestre que tres de ellos tienen un punto en común.

Hay 6 puntos en el plano (3 azules y 3 rojos cada uno), de los cuales tres no se encuentran en la misma línea recta. Demostrar que en los vértices de un cuadrilátero convexo se encuentran 2 puntos azules y 2 rojos.

En el campo de cuadros se encuentra un juego completo de fichas de dominó (cada ficha ocupa 2 celdas). Llamemos región un conjunto de cuadrados que tienen el mismo número de fichas de dominó. Llamemos a la región enlace, si desde alguna de sus casillas una torre coja puede dar en cualquier otra. ¿Cuál es el mayor número de regiones conectadas que pueden estar en el campo?

ORDEN PARCIAL.

Hay 12 niñas y 12 niños en la clase, todos de diferentes alturas. En la lección de educación física, se construyeron en dos filas (una detrás de la otra): niños, en altura de izquierda a derecha, y niñas, en altura de derecha a izquierda. Luego, de cada pareja de niño-niña, se llamaba a uno superior. Demuestra que has convocado a los doce estudiantes más altos.

Dados varios números naturales diferentes. Se sabe que entre tres cualesquiera de ellos es posible elegir dos para que uno sea divisible por el otro. Demostrar que todos los números se pueden colorear con dos colores, de modo que para dos números cualesquiera del mismo color, uno es divisible por el otro.

Demuestre que de 17 números naturales diferentes, o hay 5 números a, b, c, d, e tales que cada uno de los números de este cinco, excepto el último, es divisible por el número que está detrás, o hay cinco números tales que ninguno de ellos no es divisible por el otro.

Los números 1, 2, 3, ..., 101 están dispuestos en fila en algún orden. Demuestre que siempre es posible tachar 90 números de esta serie para que los 11 restantes estén en orden ascendente o descendente.

ALGORITMOS.

Demostrar que los vértices de un árbol de expansión se pueden escalonar.

En un grupo de personas, todos tienen un conocido. Demuestre que este grupo se puede dividir en dos para que cada persona tenga un conocido de otro grupo.

En el pueblo, algunas casas están conectadas por cables. Los vecinos son dos personas cuyas casas están conectadas por cables. ¿Siempre será posible instalar en cada casa a una persona, un mentiroso o un caballero, para que todos respondan a la pregunta: "¿Hay mentirosos entre tus vecinos?" - respondió afirmativamente. (Todo el mundo sabe de cada uno de sus vecinos, sea mentiroso o no).

Demostrar que los números naturales se pueden ordenar en los vértices de un poliedro de tal manera que en cada dos vértices conectados por una arista hay números que no son coprimos, pero en cada dos vértices que no están conectados por una arista, hay números coprimos.

EN Puerto Aventura 16 agentes secretos fueron abandonados. Cada uno de ellos mantiene un ojo en algunos de sus colegas. Se sabe que si un agente PERO siguiendo al agente EN, entonces el agente EN no sigue al agente PERO. Cualquier 10 agentes se pueden volver a numerar de tal manera que el primero sigue al segundo, el segundo - el tercero, ..., el décimo - el primero. Demuestre que unos 11 agentes se pueden numerar de la misma manera.

en que norte puedes colorear todos los bordes norte-prisma de carbón (base - norte-gons) en tres colores de modo que en cada vértice las aristas de los tres colores converjan y cada cara (incluidas las bases) tenga aristas de los tres colores?

pero). Demuestra que los vértices de un prisma 3n-gonal se pueden colorear con tres colores de modo que cada vértice esté conectado por aristas a vértices de los tres colores. B). Demuestra que si los vértices de un prisma n-gonal se pueden colorear con tres colores de modo que cada vértice esté conectado por aristas a los vértices de los tres colores, entonces n es divisible por 3.

"ANTÍGRAFA".

En una empresa de 2n+1 personas, para cualquier n personas, hay una persona diferente que conoce a cada una de ellas. Demuestra que hay una persona en esta empresa que conoce a todos.

GRAFOS Y POLINOMIOS.

Dado un número natural k y polinomios R(X) Y S(X) con coeficientes enteros. Se sabe que para cualquier número entero X número R(S(X)) – X dividido por k. Demostrar que el número S(R(X)) – X también se divide en k para cualquier todo X.

¿Existen cuatro polinomios tales que la suma de tres cualesquiera tenga al menos una raíz y la suma de dos cualesquiera no tenga raíces?

CICLO.

Hay 2.000 shorties en la Ciudad de las Flores. Cada shorty le da un regalo a cada uno de sus amigos todos los días. Para evitar la ruina, se permite dar más adelante el regalo, pero no a quien te dio este regalo. Znayka calculó que ninguno de los regalos que le dieron el viernes podrían devolverle antes del próximo viernes. Demuestra que algún bajito no tiene más de 13 amigos. (E.Cherepanov)

Hay 100 ciudades en el estado. Algunos pares de ciudades están conectadas por carreteras y hay al menos cuatro rutas cíclicas. Demostrar que existe una ruta cíclica que pasa a lo sumo por 51 ciudades.

Hay 100 ciudades en el país, algunos pares de ciudades están conectadas por carreteras y hay 200 carreteras en total. Resultó que cualquier ruta cíclica tiene una longitud de al menos cinco. Demuestre que hay dos rutas cíclicas que no se cruzan.

Hay muchos ascensores en el edificio de la Universidad de Moscú, y cada ascensor transporta pasajeros solo entre unos dos pisos (pero en cada piso puedes ir a cualquier ascensor que se detenga en él). Se sabe que es posible llegar de cualquier piso a cualquier otro utilizando un número par de ascensores y sin pasar dos veces por un piso. Demuestre que, si se desea, se puede hacer lo mismo utilizando un número impar de ascensores.

Hay varios castillos en Oz, cada uno con tres caminos. El caballero errante abandonó su castillo ancestral y se embarcó en un viaje por todo el país. El caballero ama la variedad, por lo tanto, cuando llega al siguiente castillo, gira a la izquierda cada vez que giró a la derecha la vez anterior, y gira a la derecha si giró a la izquierda antes. (Al pasar el primer castillo en su camino, el caballero puede girar en cualquier dirección). Demuestra que un día el caballero volverá a su castillo.

Una secuencia infinita de números del 1 al 9 está impresa en una cinta sin fin. Demuestre que alguna combinación de números se repite 10 veces seguidas, o que se pueden cortar 10 números de cien dígitos en orden descendente.

TEOREMA DE LA PARIDAD DEL NÚMERO DE VÉRTICES IMPAR.

Los vértices de un poliedro convexo, cuyas caras son todos triángulos, están pintados en tres colores. Demuestra que el número de caras que tienen los tres colores diferentes es par.

El número de costillas.

Dibuja un cuadrado de 12 x 12 en una hoja blanca de papel cuadriculado. Dos celdas se consideran adyacentes si tienen un lado común. Sasha pinta sobre una celda a la vez, ingresando en cada celda sombreada el número de sus vecinos pintados previamente. ¿Cuál será la suma de todos los números cuando se llenen todas las celdas? (A.Shapovalov)

Coloreó una hoja interminable de papel cuadriculado, excepto el cuadrado 77. En este cuadrado, Vasya pintó una celda con exactamente una celda adyacente (al lado) coloreada, luego otra celda, que ahora tiene exactamente una celda adyacente coloreada, y así sucesivamente. ¿Cuál es el mayor número de celdas que Vasya puede colorear de esta manera?

en que norte>1 puede pasar que en una empresa de norte+1 chicas y norte niños, todas las niñas conocen un número diferente de niños y todos los niños conocen el mismo número de niñas?

MEZCLA.

En alguna reunión asistieron norte humano. Se sabe que cada dos conocidos entre ellos no tienen conocidos mutuos, y cada dos personas que no se conocen tienen exactamente dos conocidos mutuos. pero). Demostrar que todos los presentes tienen el mismo número de conocidos. B). en que norte condición posible de la tarea?

La ciudad de la "Diversidad" es el hogar de 10.000 habitantes, cada dos de los cuales son enemigos o amigos entre sí. Todos los días, no más de un residente de la ciudad puede "comenzar una nueva vida", es decir, pelea con todos tus amigos y hazte amigo de todos tus enemigos; mientras que tres residentes pueden hacerse amigos entre sí. Para demostrar que todos los residentes sin excepción pueden hacerse amigos entre sí. ¿Cuál es el menor número de días que seguramente será suficiente para esto?

k Y norte son números naturales mayores que 1. En el grupo de kn cada persona está más familiarizada que con ( k–1)norte del resto Demuestra que puedes elegir k+1 persona para que todos se conozcan. ( Olimpiadas polacas, 68)

Se marcan 100 puntos en el plano. Dos personas juegan, se turnan. En un movimiento, puede conectar dos puntos con una flecha si no se han conectado antes. Al mismo tiempo, está prohibido dibujar una flecha, después de la aparición de la cual desde cualquier punto será posible pasar las flechas a cualquier otro. Pierde el que no puede hacer el siguiente movimiento sin violar las reglas. ¿Quién gana con la jugada correcta: el que se mueve primero o su compañero? ( SI. Rostov)

En el condado de One-Side, hay caminos de un solo sentido entre algunas (pero desafortunadamente no todas) las granjas. Al mismo tiempo, cuando aparece cualquier carretera nueva (también con circulación en un solo sentido) entre urbanizaciones que antes no estaban conectadas por una carretera, resulta que uno puede ir de cualquier urbanización a cualquier otra sin infringir las normas. Demostrar que tal posibilidad ya existe ahora. ( SI. Rostov; San Petersburgo, ciudad 2000)

Conocí a algunos amigos. Cada uno de ellos estrechó la mano de todos menos de Fedot Burcheev, quien, al estar de mal humor, estrechó la mano de unos y de otros no. Hubo 197 apretones de manos en total. ¿Cuántos apretones de manos hizo Fedot? ( ES. Rubanov)

Hay 100 ciudades en el país, al menos una carretera sale de cada ciudad. Demuestre que es posible cerrar varias carreteras de modo que todavía haya al menos una carretera que salga de cada ciudad y al menos una carretera que salga de al menos 67 ciudades. ( EA Girsh, SV Ivanov, DV Kárpov)

Hay 40 aulas en la escuela, que se abren con 5 tipos diferentes de llaves, y la cantidad de llaves de diferentes tipos es diferente. Las 40 llaves estaban encerradas en las habitaciones, de modo que en cada habitación hay una llave bloqueada, que no se puede usar para abrir esta habitación. Watchman Sergeev tiene un duplicado de la llave de una de las habitaciones. Demuestra que puede abrir todas las habitaciones. ( )

La escuela cuenta con 40 aulas que se abren con 4 tipos diferentes de llaves. Las 40 llaves se guardaron con llave en las habitaciones, de modo que en cada habitación hay una llave que no se puede usar para abrir esta habitación. El vigilante Sergeev sabe dónde está la clave. Demuestra que el vigilante Sergeev puede duplicar las llaves de dos armarios, que pueden usarse para abrir todas las habitaciones. ( REAL ACADEMIA DE BELLAS ARTES. Ismailov, S.L. Berlov, DV Kárpov)

(S. Berlov, San Petersburgo, ciudad, 2001, 6-1) En la exhibición de gatos, 19 gatos y 10 gatos estaban sentados en fila, y al lado de cada gato había un gato que era más gordo que él. Demuestra que al lado de cada gato había un gato más delgado que él.

(S.Bérlov) El continente cuadrado está dividido en 19 países en forma de polígonos convexos, y no hay puntos en los que convergerían las fronteras de cuatro o más países. De tres fronteras que convergen en un punto, una está cerrada y dos están abiertas al tráfico. Demuestra que es imposible viajar por todos estos países, visitando cada uno de ellos una vez y volviendo al país de origen.

En el país de Fulkersonia, algunas ciudades están conectadas por líneas aéreas y es imposible llegar de la ciudad A a la ciudad B con menos de diez transbordos. Demuestre que todas las líneas aéreas se pueden vender a 11 líneas aéreas de tal manera que cualquier ruta de A a B utilizará líneas propiedad de las 11 líneas aéreas. (Folklore, 100)

Cada estudiante de la clase está en dos círculos, y por cada tres estudiantes hay un círculo al que van juntos. Demostrar que existe un círculo en el que participan todos los alumnos. (Olimpiadas DalFO 2001, 104)

. Diez personas vinieron a visitarnos en chanclos. Salieron uno a la vez, y cada uno se puso un par arbitrario de chanclos en los que podía caber (es decir, no más pequeños que los suyos). ¿Cuál es el mayor número de personas que no podían usar chanclos?

En el fabuloso país de Perra-Terra, entre otros habitantes, viven Karabas y Barabas. Cada karabas está familiarizado con seis karabas y nueve barabas. Cada barabas está familiarizado con diez karabas y siete barabas. ¿Quién es más en este país, Karabas o Barabas?

En un grupo de 100 personas, entre tres cualesquiera hay una persona que está familiarizada con las otras dos. Demuestre que de este grupo es posible elegir una empresa de 50 personas en la que todos se conozcan. (S. Berlov)

20 señores vinieron al club, algunos con sombrero, otros sin. Entonces de vez en cuando uno de los señores se quitaba el sombrero y se lo ponía en la cabeza a otro señor, que en ese momento no tenía sombrero. Una hora después, 10 caballeros dijeron: “¡Di mi sombrero más veces de las que lo recibí!”. ¿Cuántos señores llegaron al club con sombreros? ( SLB, Yu.M. mierdas; SPb-02)

Alguna empresa tiene más de 10 personas, y cada una de ellas tiene un número de conocidos divisible por 10. Demostrar que hay al menos 11 personas con el mismo número de conocidos. ( SLB basado en Moldavia)

En la Olimpiada se propusieron 8 (6) tareas. Cada participante resolvió exactamente 3 de ellos, y no hubo dos participantes que resolvieran más de un problema común. ¿Cuál es el mayor número de participantes en la Olimpiada? ( Vía Báltica, 01)

para una empresa de norte persona, se cumple la siguiente condición: si unas 2 personas tienen conocidos iguales, entonces cada uno de los demás conoce exactamente a uno de ellos. en que norte¿Es posible? ( Vía Báltica, 2000)

19 invitados vinieron a la fiesta. Entre 3 de ellos hay 2 conocidos. Demuestre que los invitados se pueden dividir en 5 grupos, en cada uno de los cuales todos están familiarizados por pares. ( V.L.Dolnikov, SLB, SVI)

(Folklore) El país tiene varias ciudades y varias carreteras de sentido único. Cada camino conecta dos ciudades y no pasa por las demás. Al mismo tiempo, no importa qué dos ciudades tome, al menos desde una de ellas puede conducir a la otra sin violar las normas de tránsito. Demuestra que hay una ciudad desde la que puedes conducir a cualquier otra ciudad sin infringir las normas de tráfico.

Entre 11 personas, dos tienen exactamente un conocido común. Demostrar que al menos uno de ellos está familiarizado con todos los demás.

(Lapok) Entre 5 personas, dos cualesquiera tienen exactamente un amigo en común. Demostrar que al menos uno de ellos está familiarizado con todos los demás.

(Juradobasado en hechos clásicos) Hay 120 ciudades en el país. Algunos pares de ciudades están conectadas por carreteras que no pasan por otras ciudades. Hay al menos tres caminos que salen de cada ciudad. Demostrar que existe una ruta cíclica que no se interseca a sí misma y consta de 11 ciudades como máximo.

(Yu.M. Lifshitz) En el país de Jurland, algunas ciudades están conectadas por carreteras (sin pasar por otras ciudades), y desde cualquier ciudad puedes llegar a cualquier otra. Un desafortunado día, una malvada tribu subchik capturó cierta ciudad. Cada día siguiente, el subchiki capturaba la ciudad adyacente a uno de los capturados o liberaba la ciudad capturada, todos los vecinos fueron capturados. Al mismo tiempo, ninguna ciudad fue capturada más de una vez. Demuestra que si los subchiks ya no pueden capturar nada, entonces al menos una de las dos ciudades vecinas ha sido capturada.

(Yu.M. Lifshitz) Al banquete asistieron 14 miembros del jurado, quienes bebieron 17 botellas de limonada. Los miembros del jurado bebieron cada botella de limonada en cuatro. Demostrar que hay dos miembros del jurado que no bebieron limonada de la misma botella.

(Folklore) Cada uno de los 7 miembros del equipo no tiene más de dos amigos cercanos. Una vez en la misma habitación, dos amigos cercanos comienzan a charlar sin cesar y todo el trabajo en esta habitación se detiene. Demuestra que tres habitaciones son suficientes para que el capitán asegure el buen funcionamiento de todo el equipo.

(Yu.M. Lifshitz) 10 jugadores de ajedrez jugaron un torneo de una ronda, cada uno ganó, perdió y empató 3 juegos cada uno. Se sabe que no hay tres ajedrecistas que anotaron exactamente 1 punto en partidos entre ellos. Demuestre que los diez jugadores de ajedrez se pueden colocar en un círculo de tal manera que cada uno de ellos le gane al que está a su derecha. El ajedrez vale 1 punto por victoria, 0,5 puntos por empate y 0 puntos por derrota.

(Yu.M. Lifshitz) 10 jugadores de ajedrez jugaron un torneo de una ronda, cada uno ganó y perdió 4 juegos y empató un juego. Demuestre que es posible elegir tres jugadores de ajedrez y colocarlos en un círculo de modo que cada uno de ellos le gane al que está a su derecha.

Los pulpos viven en el Mar de las Lluvias, cada uno con uno o dos amigos. Cuando salió el sol, todos los pulpos que tenían dos amigos se volvieron azules y todos los que tenían un amigo se volvieron rojos. Resultó que dos amigos cualesquiera son multicolores. Luego, 10 pulpos azules se tiñeron de rojo y, al mismo tiempo, 12 pulpos rojos se tiñeron de azul, después de lo cual dos amigos cualesquiera se volvieron del mismo color. ¿Cuántos pulpos hay en el Mar de las Lluvias?

Hay 12 pilares en el patio. El electricista Petrov recibió la tarea de conectar los polos con cables de tal manera que cada cable conectara exactamente dos polos, dos polos no estarían conectados dos veces y, lo que es más importante, que para cuatro polos habría exactamente tres cables estirados entre sí. estos postes. Demuestre que el electricista Petrov no podrá hacer frente a esta tarea.

Cada una de las 24 personas conoce al menos a 11 de las otras. ¿Siempre es posible alojarlos en habitaciones dobles del hotel para que cada uno se aloje con su conocido?

El planeta Thor tiene forma de dona. Tiene 5 ciudades. ¿Es posible conectar cada par de estas ciudades con caminos para que los caminos no se crucen en ninguna parte?

En la isla de Nueva Babilonia se hablan 45 idiomas, y cada habitante conoce al menos cinco de ellos. Se sabe que dos habitantes cualquiera pueden mantener una conversación entre sí, posiblemente con la mediación de varios traductores. Demuestre que entonces dos isleños cualesquiera pueden hablar entre sí usando no más de 15 intérpretes.

En un grupo de 100 personas, algunos se conocen entre sí, y cada miembro del grupo conoce al menos a otros 20. Demuestre que es posible elegir 40 miembros del grupo y dividirlos en 20 pares para que las personas de cada par estén familiarizadas.

Sobre el kn Las tarjetas tienen números del 1 al 1 en ambos lados. norte 2 cada uno k una vez cada uno. Demuestre que estas tarjetas se pueden colocar sobre la mesa de modo que cada número se escriba exactamente en la parte superior. k una vez.

Hay 201 ciudades en el país, cada una con exactamente 10 caminos, y desde cualquier ciudad puedes llegar a cualquier otra. Demuestre que es posible elegir 20 ciudades, de las cuales dos no están conectadas por una carretera.

Hay varios postes en el patio, algunos de los pares están conectados por cables. total estirado Minnesota alambres, y estos alambres están pintados en norte colores, y los alambres del mismo color no salen de ningún poste. Demuestre que es posible cambiar el color de estos cables para que haya igual número de cables de todos los colores y aún así no salgan dos cables del mismo color de ningún poste. (130, Ucrania 1989)

Hay 36 postes en el patio, inicialmente se estira un cable entre dos postes cualesquiera. Todas las mañanas, de camino a la escuela, el gamberro Vasya corta 35 cables. Todas las noches, el electricista Petrov restaura los cables que se extienden desde un determinado poste. Demuestre que Vasya puede actuar de tal manera que una mañana después de otro acto de vandalismo queden menos de 18 cables. (135, AV. Pastor, San Petersburgo 2000)

Se marcan 100 puntos en el plano. Dos personas juegan, se turnan. En un movimiento, puede conectar dos puntos con una flecha si no se han conectado antes. Al mismo tiempo, está prohibido dibujar una flecha, después de la aparición de la cual desde cualquier punto será posible pasar las flechas a cualquier otro. Pierde el que no puede hacer el siguiente movimiento sin violar las reglas. ¿Quién gana con la jugada correcta: el que se mueve primero o su compañero?

De los números enteros del 1 al 100, se eligieron varios números diferentes. Llamemos al indicador de divisibilidad de un número dado el número de números elegidos por los cuales el número dado es divisible. Resultó que todos los números elegidos tienen diferentes índices de divisibilidad. ¿Cuál es la mayor cantidad de números que se pueden elegir?

norte los círculos están dispuestos de modo que el centro de cada uno de ellos se encuentra exactamente dentro de uno de los otros, y dentro de cada uno se encuentra exactamente el centro de uno de los otros. Encuentra todos los números norte para los que esto es posible.

22 escolares participaron en el congreso de jóvenes escritores. Después del congreso, cada uno de ellos leyó las obras de tres jóvenes escritores que asistieron al congreso. Demuestre que es posible formar una comisión de 4 personas de los delegados del congreso de tal manera que nadie en la comisión haya leído los trabajos de sus otros miembros.

Hay 1999 veraneantes en la casa de descanso. Algunos de ellos están familiarizados entre sí, y dos desconocido tener un amigo común entre los veraneantes. ¿Cuál es el menor número posible vapor veraneantes familiares?

Hay 1000 ciudades en el planeta, entre las cuales hay capitales de estados. Algunas ciudades están conectadas por caminos de tal manera que cualquier camino conecta exactamente dos ciudades, y de cualquier ciudad a cualquier otra se puede llegar por caminos. Al mismo tiempo, para ir de una capital a otra, debe conducir al menos 21 caminos. Demuestra que no hay más de 90 capitales en el planeta.

1997 se clavan clavos en el tablero. Los dos se turnan para hacer movimientos. El movimiento consiste en que el jugador conecta con un cable dos clavos cualesquiera que no hayan sido conectados antes. El que pierde, después de cuyo movimiento, por primera vez, es posible pasar por cable de cualquier clavo a cualquier otro. ¿Quién ganará con la jugada correcta: el que haga el primer movimiento o su compañero?

Gráfico conectado GRAMO permanece conectado al eliminar 18 vértices cualesquiera (junto con todos los bordes que emergen de ellos). Llamemos Corte cualquier conjunto de 19 vértices, al eliminarlos, el gráfico pierde conectividad, y pedazo cualquier componente conectado que se forma cuando se quita el corte. Se sabe que cualquier pieza que contenga menos de 10 vértices no está contenida en ninguna sección. Demuestre que ninguna pieza está contenida dentro del corte.

Grafico GRAMO conectado. Llamemos Corte el conjunto mínimo (con respecto a la inclusión) de vértices, al eliminarlos (junto con todos los bordes que salen de ellos) el gráfico pierde conectividad. Se sabe que al quitar los vértices cortados R vértices del corte S aparecen en el mismo componente conectado. Demostrar que al quitar los vértices cortados S vértices del corte R aparecen en el mismo componente conectado.

En papel cuadriculado, se marcan 49 nodos de cuadrícula, dispuestos en forma de un cuadrado de 66. ¿Cuál es el número mínimo de segmentos unitarios con extremos en los nodos marcados que se deben dibujar para que entre cualquier par de nodos vecinos haya un camino no mayor a 3?

en una empresa de norte una persona donde todos están familiarizados con al menos uno de los otros, todos igualmente familiares (se cree que si PERO está familiarizado con EN, entonces y EN está familiarizado con PERO). Demostrar que entre los miembros de esta empresa puede elegir al menos norte/3 pares de conocidos no superpuestos.

En una empresa, cada dos personas tienen exactamente cinco conocidos mutuos. Demostrar que el número de conocidos (parejas de conocidos) es múltiplo de tres. ( Yu.M. Lifshitz)

En el torneo de una ronda, dos participantes abandonaron la competencia después de la quinta ronda. Como resultado, se jugaron 38 juegos en el torneo. ¿Se las arreglaron estos dos para jugar entre sí? ( Bulgaria, 1982)

En el torneo de una ronda, seis participantes abandonaron la competencia después de la sexta ronda. Como resultado, se jugaron 67 juegos en el torneo. Demuestre que al menos dos de los abandonos no jugaron entre sí. ( K. A. toque)

¿Cuál es el menor número posible de aristas en un gráfico de 100 vértices tal que entre 11 vértices cualesquiera haya uno que esté conectado a los otros 10? ( R. Fiódorov)

En el grafo conexo 2 norte vértices, el grado de cada vértice es tres. Demuestre que el número de formas de colorear los bordes de este gráfico con tres colores para que los bordes de diferentes colores converjan en cada vértice no exceda de 32 norte .

En algún estado 4 norte aeropuertos, de cada aeropuerto salen exactamente 3 aerolíneas (una aerolínea conecta dos aeropuertos). Desde cualquier aeropuerto puedes volar a cualquier otro (posiblemente con transbordos). Permitir PARA - número de formas de vender todos líneas aéreas a tres líneas aéreas para que tres líneas aéreas de diferentes líneas aéreas salgan de cada aeropuerto. Pruebalo PARA 32 3 norte .

Ocho jugadores de ajedrez jugaron el torneo en una ronda. Se sabe que en cualquier trío de ajedrecistas había dos que jugaban tablas entre sí. ¿Cuál es el menor número de empates que pudo haber en este torneo?

En los vértices de la plaza hay 4 ordenadores conectados a sus vecinos a los lados de la plaza. En el momento inicial, llegaron noticias importantes a cada computadora (para cada una, la suya). Cada segundo, una computadora puede transmitir todas las noticias que conoce a una computadora vecina, recibir información relevante de una computadora vecina o permanecer inactiva. ¿Cómo pueden todas las computadoras obtener todas las noticias en el sistema en el menor tiempo posible?

En la tierra de Elenia norte residentes Se unen en círculos de interés. Hay exactamente tres personas en cada círculo, y dos de ellas son miembros de exactamente un círculo al mismo tiempo. Pruebalo norte Cuando se divide por 6, el resto es 1 o 3.

Llegué al campamento metro chicos y D muchachas. Cada niña conoce a no más de 10 niños, y cada niño conoce al menos a una niña. Resultó que cada chico tiene más chicas que conoce que cualquier chica que conoce conoce a chicos. Pruebalo D 1.1 metro. (DV Kárpov)

Dé un ejemplo de catorce edros, cada una de las cuales es un cuadrado o un triángulo regular. ( SI. Kramarenko)

Hay 2000 puntos negros en el espacio, de los cuales cuatro no se encuentran en el mismo plano. Algunos de los puntos están conectados por flechas. Se sabe que no hay camino siguiendo las flechas y pasando por todos los puntos (aunque es posible pasar por el mismo punto varias veces). Demuestre que algunos de los puntos (al menos uno, pero no todos) se pueden volver a colorear de azul para que ninguna flecha lleve del punto azul al negro. ( Bielorrusia, 1992)

El gráfico tiene un árbol de expansión con exactamente norte vértices colgantes y un árbol de expansión con exactamente metro tapas colgantes, norte  k  metro. Demuestre que esta gráfica tiene un árbol generador con exactamente k picos colgantes.

En una empresa de 200 personas, cinco personas cualesquiera se pueden sentar en una mesa redonda para que cada uno se siente entre dos conocidos (se supone que si A está familiarizado con B, luego B está familiarizado con A). ¿Cuál es el menor número de parejas de conocidos que puede haber en esta empresa?

Demostrar que para todo poliedro es posible colorear dos caras de rojo y las otras dos de azul, de modo que las caras rojas tengan lados iguales y las caras azules tengan los mismos lados.

En el grafo conexo 3 k vértices, todos tienen grado 3, y cada vértice está incluido en exactamente un triángulo. Se han eliminado algunos bordes del gráfico para obtener un árbol. Demuestre que este árbol tiene como máximo k+2 vértices de grado 1.( DV Kárpov)

en el reino norte ciudades y r caminos (cada camino conecta dos ciudades, y desde cualquier ciudad se puede llegar a cualquiera de los caminos). Los mensajeros viven en las ciudades. Al comienzo de cada año, una de las ciudades envía un mensajero a todas las ciudades vecinas (es decir, conectadas a ella por carreteras). (Dicha ciudad debería tener una cantidad suficiente de mensajeros para esto). Después de unos pocos (más de cero) años, cada ciudad tenía la misma cantidad de mensajeros que tenía originalmente. ¿Cuál es el menor número de mensajeros que puede tener un reino? ( yo Bogdánov)

Dado un gráfico cuyo grado de cualquier vértice es al menos k(donde k2). Demuestre que este gráfico contiene un ciclo simple de longitud al menos k+1. ()

En una banda de terroristas, todos sospechan al menos de otros 10 de traición. Demostrar que en esta banda es posible identificar al menos a 11 terroristas y numerarlos de modo que el primero sospeche del segundo, el segundo, el tercero,... , el penúltimo - el último, y el último - el primero. ( basado en elKozepiskolai Matematikai Lapok)

En un gráfico, dos ciclos simples cualesquiera de longitud impar no tienen aristas comunes. Demuestra que los vértices de este gráfico se pueden colorear con dos colores para que cada vértice esté conectado por una arista a, como máximo, un vértice del mismo color.( S.L. Bérlov)

Hay 100 ciudades en el país. Algunos pares de ciudades están conectadas por carreteras, pero ninguna ciudad está conectada con todas. Es posible llegar de cualquier ciudad a cualquier otra, llamando en el camino a no más de una ciudad. ¿Cuál es el menor número de carreteras en este país? ( )

Hay 25 ciudades en el país. Algunos pares de ciudades están conectadas por carreteras, pero ninguna ciudad está conectada con todas. Es posible llegar de cualquier ciudad a cualquier otra, llamando en el camino a no más de una ciudad. Demuestra que hay al menos 35 carreteras en este país. ( Kozepiskolai Matematikai Lapok)

Hay 9 ciudades en el país. Algunos pares de ciudades están conectadas por carreteras, pero ninguna ciudad está conectada con todas. Es posible llegar de cualquier ciudad a cualquier otra, llamando en el camino a no más de una ciudad. ¿No puede haber más de 13 carreteras en este país? S.L. Berlov, DV Karpov, basado en Közepiskolai Matematikai Lapok)

Grados de todos los vértices del gráfico GRAMO menos (donde norte> 2), y entre cualquiera norte+ 1 hay dos vértices no adyacentes. Llamemos cuadra conjunto de norte vértices de gráficos adyacentes por pares GRAMO.Se sabe que dos bloques cualesquiera tienen un vértice común. Demuestra que todos los bloques tienen un vértice común.( CL Bérlov)

Bordes de un gráfico completo con norte los vértices están pintados en varios colores, y los colores no son menos de norte. Demuestra que hay tres vértices, todos los bordes entre los cuales están coloreados de diferentes colores. ( PENSILVANIA. Kozhevnikov)

Bordes de un gráfico completo con norte los vértices están coloreados en varios colores de tal manera que cada color ocurre como máximo norte- 2 veces. Demuestre que hay tres vértices, todos los bordes entre los cuales están coloreados en diferentes colores.( AMM)

en el gráfico GRAMO se seleccionan conjuntos de vértices S 1 , S 2 , S 3 con 100 vértices cada uno. Se sabe que cuando se eliminan todos los vértices de cualquiera de estos tres conjuntos (y todas las aristas que salen de ellos), los vértices restantes del gráfico caen en exactamente dos componentes conectados, y cuando se eliminan 99 vértices, el gráfico permanece conectado. Demostrar que todo lo que no está incluido en los conjuntos S 1 , S 2 y S 3 vértices del gráfico GRAMO se puede dividir en 6 grupos de tal manera que los vértices de un grupo terminan en la misma componente conexa al eliminar cualquiera de los conjuntos del gráfico de vértices S 1 , S 2 o S 3 .(DV Kárpov)

King Pea tiene 20 cortesanos. Intrigando unos contra otros, formaron una serie de sociedades secretas. El jefe de la policía secreta, estudiando estas sociedades, descubrió tres patrones. Primero, para cualesquiera dos sociedades secretas, todos los cortesanos que son simultáneamente miembros de ambas sociedades forman una sociedad secreta. En segundo lugar, para dos sociedades secretas cualesquiera, todos los cortesanos que son miembros de al menos una de ellas forman una sociedad secreta. En tercer lugar, para cualquier sociedad secreta, todos los cortesanos que no son miembros de ella forman una sociedad secreta. ¿Puede haber exactamente 2002 sociedades secretas en la corte de Peas? ( Putnam 1961, reformulación)

Las aristas del dodecaedro están numeradas del 1 al 30 sin repetición. Contemos el número de líneas quebradas formadas por tres aristas del dodecaedro y tales que los números de los eslabones estén en orden ascendente. Encuentre el número mínimo posible de tales líneas discontinuas. (yo Bogdanov, G. R. Chelnokov basado en la tarea de la Olimpiada polaca-89/90 )

Los números del 1 al 12 se colocan en los bordes del cubo sin repeticiones. Contemos el número de líneas quebradas que forman las tres aristas del cubo y que los números de los eslabones están en orden ascendente. Encuentre el número mínimo posible de tales líneas discontinuas. (Polonia-89/90)

En una empresa de 20 personas por cada tres hay una persona que los conoce a todos. Demostrar que hay una persona que tiene al menos nueve conocidos. ( S. L. Berlov, I. I. Bogdanov)

En una empresa de 10 personas por cada tres hay una persona que los conoce a todos. Demostrar que hay una persona que tiene al menos seis conocidos.

Al simposio asistieron 100 personas. De estos, 15 son franceses, cada uno de los cuales está familiarizado con al menos 70 participantes del simposio, y 85 son alemanes, cada uno de los cuales está familiarizado con no más de diez participantes. Se instalaron en 21 habitaciones. Demostrar que no hay parejas de conocidos en ninguna de las habitaciones. ( Y. Lifshitz)

Hay 22 atletas en la empresa. Parejas de atletas que son amigos entre sí: catorce. Resultó que entre 11 atletas hay al menos un par de amigos. Demuestra que todos pueden dividirse en dos equipos de fútbol para que cada par de amigos esté en el mismo equipo. ( Simplificando la tarea de 10 grandes ligas)

En la columna 4 k picos 3 k costillas Se sabe que entre 2 k hay dos de sus vértices conectados por una arista. Demostrar que los vértices de la gráfica se pueden dividir en dos grupos de 2 k vértices en cada uno de modo que no haya dos vértices de diferentes grupos conectados por una arista. (RA Brualdi, S. Mellendorf)

Un rey de ajedrez borracho nunca hace dos movimientos seguidos en la misma dirección. Comenzando desde la esquina, caminó alrededor del tablero de ajedrez de 9x9, visitó cada celda una vez y regresó a la celda original. ¿Cuál es el menor número de movimientos diagonales que podría hacer? ( S.L. Berlov basado en el problema de O.Yu. Lanina, FML Olimpiada No. 239, 2002GRAMO.)

Hay 7 ciudades en el país, entre las cuales vuelan 7 aviones. El avión vuela de cada ciudad a cualquier otra durante exactamente 1 hora, e inmediatamente después de aterrizar puede volar a la siguiente ciudad (mientras los pasajeros en tránsito permanecen en el avión). Haz un horario de vuelo para que cualquier pasajero, sin cambiar de avión en el camino, pueda volar de cualquier ciudad a cualquier otra en no más de 5 horas de haber llegado al aeropuerto. (Juegos Olímpicos de Grossman)

Los cinco vértices del cubo están coloreados de rojo. ¿Es cierto que necesariamente hay tres aristas que tienen extremos rojos en ambos extremos?

Fedya tiene un gráfico desconectado. Eliminó un vértice de este gráfico por todos los medios posibles y dibujó cada uno de los gráficos resultantes en una hoja de papel separada, después de lo cual le dio todas estas hojas a Dima. Demuestra que Dima puede restaurar el gráfico original usando estas hojas. ( DV Karpov, basado en la hipótesis de Ulam)

Fedya tiene varias cajas que contienen bolas. Saca una bola a la vez de las cajas, escribe un conjunto de números en una hoja de papel separada: la cantidad de bolas que quedan en cada caja, si queda algo (sin especificar qué número corresponde a qué caja), y luego devuelve la pelota a su lugar. Sacando cada bola una vez, le da todas las hojas a Dima. Demuestra que Dima puede determinar cuántos globos hay en cada caja. ( DV Kárpov)

norte- número impar. vértices convexos norte-Los gons están coloreados en varios colores para que cada dos vértices vecinos sean de un color diferente. probar que esto norte-gon se puede dividir en triángulos mediante diagonales que no se intersecan, ninguna de las cuales tiene extremos del mismo color. ( Kurszak-1978, №2)

Dada una gráfica de norte picos Demostrar que todas sus aristas se pueden dividir en a lo sumo norte 2/4 conjuntos, cada uno de los cuales consta de un borde o es un triángulo. ( Bogdanov, Karpov)

Las ciudades A, B, C están conectadas por vuelos. Entre dos ciudades cualesquiera hay al menos un vuelo y todos los vuelos son de ida y vuelta (si puede volar de A a B, entonces el mismo vuelo puede volar de B a A). Además, se sabe que el número total de formas para ir del punto A al punto C (incluidas las rutas con un cambio en B) es 11, y el número total de formas para llegar del punto A al punto B (incluidas las rutas con un cambio en B) un cambio en C) es 13. vuelos sin escalas entre estas ciudades?

Dado un cuadrado ajedrezado cuyo lado contiene norte nodos. Un camino sin retorno es un camino a lo largo de los bordes, cuya intersección con cualquier línea horizontal o vertical es un segmento, un punto o un conjunto vacío. ¿Cuál es el menor número de caminos no recursivos que pueden cubrir todos los vértices? ( I. Pushkarev, I. Bogdanov, G. Chelnokov)

Dado un grafo conexo que permanece conexo cuando se elimina cualquier vértice. Se sabe que tiene un triángulo. En cada vértice, excepto uno, hay una ficha (todas las fichas son diferentes). Está permitido mover una ficha de un vértice adyacente a uno vacío a uno vacío. Demuestre que mediante tales acciones se puede obtener cualquier configuración de chips a partir de cualquier configuración. ( M.Mazin)

En la ciudad, 10 calles corren de norte a sur y 11 de oeste a este, formando 110 intersecciones. Por orden del alcalde, cualquier ruta de autobús en la ciudad puede ir en no más de dos direcciones (este-sur, este-norte, oeste-sur u oeste-norte). ¿Es posible conectar todas las intersecciones de la ciudad con siete rutas de autobús? (Basado en I. Pushkarev, I. Bogdanov, G Chelnokov)

¿Cuál es el menor número de vértices que puede tener un poliedro convexo, exactamente tres de cuyas caras son pentágonos? ( USAMTS 2003)