El problema más fácil, en términos de enunciado de preguntas, es el problema de la teoría de Ramsey, aunque la (s) solución (es) a las preguntas de la teoría de Ramsey pueden ser bastante complejas, la pregunta es muy simple.
Digamos que estás en una fiesta; una colección de personas que se conocen o no se conocen (una situación binaria). Ahora que tiene una situación de sí o no, cuántas personas se requieren, de modo que se garantiza que n número de personas se conozcan o no (en este ejemplo) .Utilizando un gráfico completo, un gráfico en el que cada vértice es adyacente ( conectado) a cualquier otro vértice en el gráfico (estos son los gráficos utilizados en situaciones de teoría de Ramsey), comencemos con n = 3.
Los números de Ramsey no se describen como el número más bajo donde es posible que la condición se vuelva verdadera, porque este sería el gráfico completo K_3, y ya estaríamos listos. Entonces expandimos el gráfico a K_4 (el gráfico completo en 4 vértices). Al marcar, sí es posible, crear un gráfico en 4 vértices donde tres de las personas no se conocen, pero no se garantiza que se cumpla esta condición, por lo que aumentamos el tamaño a 5 vértices. Aplicamos el mismo concepto que con 4 y llegamos a la misma conclusión, no es posible crear un gráfico completo en 5 vértices donde 3 personas se conocerán o no.
- ¿Cómo verificamos la inexistencia de un camino hamiltoniano?
- ¿Cuál es la explicación rigurosa de por qué n / m es el factor de carga en una tabla hash?
- Cómo usar el lenguaje C para escribir un programa para hacer una matriz de multiplicación que permita 1, 2, 3, 4, 5, 6 o 7 hilos que corren paralelos
- ¿Cómo sabe la CPU que estamos usando el complemento de uno o el complemento de dos para representar números negativos?
- ¿Por qué Matlab no le permite llamar a las funciones dos veces o indexarlas como en f (x) (y)?
Finalmente, nos movemos a 6 vértices. Comenzamos con una persona indicada {1}, y establecemos una conexión entre ellos y otra {2}, digamos que se conocen. Ahora, pasamos de {1} a otra persona {3}, ellos también se conocen. Finalmente, pasamos de {1} a otra persona, {4}. Estamos tratando de evitar que tres personas conozcan a otras tres personas, por lo que {2} no puede saber {3}, de manera similar, {3} no puede saber {4}. Además, {2} no puede saber {4} porque de lo contrario 3 personas se conocerían entre sí. Sin embargo, al hacer esto, hemos demostrado que tres personas no se conocen, por lo que el número de Ramsey de 3 es 6, o en notación estándar, R (3,3) = 6
La prueba en Wikipedia es satisfactoria y probablemente sea más fácil de seguir ya que he realizado algunos cambios en el idioma para que esta prueba sea más accesible. http://en.wikipedia.org/wiki/Ram…
Esta es solo mi experiencia y fue el primer problema que me presentó mi asesor de investigación de pregrado. Si alguien tiene otra idea o si esto no es lo que deseaba, avíseme y haré todo lo posible para hacer ajustes o agregar otra respuesta completa hasta que esté satisfecho.
