Problema ramsey
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de julio de 2021; las comprobaciones requieren 2 ediciones .El problema de Ramsey [1] [2] [3] , el problema de citas de seis personas [4] es un teorema matemático en la teoría de Ramsey , un caso especial del teorema de Ramsey .
Declaración
Que haya 6 personas en la fiesta. Si dos personas se han conocido al menos una vez antes, se les llama conocidos, si no, desconocidos. Según el problema de Ramsey:
En cualquier empresa de seis personas, o tres personas se conocen en parejas, o tres personas no se conocen en parejas.
Convertir una condición en un gráfico
La demostración se puede realizar mediante un gráfico, escribiendo la condición del teorema de esta forma.
El gráfico tendrá 6 vértices , cada par de vértices está conectado por una arista . Tal gráfico se llama gráfico completo (es imposible dibujarle nuevos bordes, ya que ya se han realizado todas las conexiones posibles). Un gráfico completo con vértices se denota por .
En este ejemplo, puede construir un gráfico . Este gráfico tiene 15 aristas. 6 vértices representan 6 personas mencionadas en el enunciado del problema.
Además, para la prueba, es necesario colorear los bordes. El borde será de color rojo si las dos personas no se conocen, o azul si se conocen. Teniendo en cuenta estas transformaciones, se puede reformular el enunciado del teorema:
Independientemente del color de los bordes, el gráfico tendrá un triángulo rojo (un triángulo en el que todos los bordes son rojos) o un triángulo azul (en el que todos los bordes son azules). El triángulo rojo significará que 3 personas son extraños por parejas, y el triángulo azul significará que 3 personas son familiares por parejas. Si esta afirmación es verdadera, entonces la afirmación original también lo será.Fin de la prueba
A continuación, para la prueba, se elige un vértice arbitrario P. Del vértice emergen cinco aristas. Según el principio de Dirichlet , al menos tres aristas del mismo color (si las aristas de uno de los colores son menos de 3, las aristas del otro color son más de 3).
A , B , C - vértices, otros extremos de los bordes mencionados anteriormente. Si al menos una de las aristas AC, BC, AB es azul, entonces puedes obtener un triángulo de un solo color (usando dos aristas de P y el vértice que acabamos de mencionar). Si ninguno de estos bordes es azul, entonces todos son rojos, y de ellos puedes obtener un triángulo rojo ABC , etc.
Notas de Ramsey
En 1930, en el artículo "Sobre un problema de lógica formal", Ramsey demostró un teorema más general (conocido como el teorema de Ramsey ), este teorema es un caso especial del mismo. La teoría de Ramsey , una de las ramas de la combinatoria , se basa en el teorema de Ramsey .
Otros casos
Si la empresa no tiene 6 personas, sino solo 5, es posible que no se lleve a cabo la consecuencia mencionada en el problema de Ramsey.
Para mostrar la posibilidad de tal caso, es necesario construir un contraejemplo . Un contraejemplo es un pentágono que rodea una estrella de cinco puntas . El pentágono debe ser de color rojo y la estrella azul. Por tanto, el número mínimo de vértices para los que la propiedad especificada en la tarea es verdadera es 6.
En la teoría de Ramsey, este hecho se escribe de la siguiente manera:
Literatura
Visvanatha Krishnamurthy. Cultura, emoción y relevancia de las matemáticas . — Wiley Oriental, 1990-01-01. — 348 pág. — ISBN 9788122402728 .
Notas
- ↑ Evgeny Vechtomov. Filosofía de las Matemáticas 2ª ed. Libro de texto para estudios de grado y posgrado . Litros, 2018-12-20. — 318 pág. — ISBN 9785041182014 .
- ↑ Novikov Fyodor Alexandrovich. Matemáticas discretas: libro de texto para escuelas secundarias. 2ª ed. Estándar de tercera generación . - Editorial "Pedro", 2012-09-10. — 400 s. — ISBN 9785496000154 .
- ↑ Irina Leonidovna Babinskaya. Problemas de Olimpiadas Matemáticas . - Nauka, 1975. - 120 p.
- ↑ Zhukovsky ME, A.A. Glibichuk, A.M. Raygorodsky, Shkredov I.D., A.B. Dainyak, D. G. Ilyinsky, D. V. Musatov, A. V. Savvateev http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Archivado el 5 de febrero de 2018 en Wayback Machine .