¿Cuáles son algunos problemas realmente fáciles de explicar que son increíblemente difíciles de resolver?

Este es un dato divertido: si [math] 6 [/ math] personas están en una fiesta, entonces [math] 3 [/ math] se conocen unas a otras, o [math] 3 [/ math] de todas ellas no no se conocen Además, esto no es cierto si [math] 6 [/ math] es reemplazado por [math] 5 [/ math]. Esto dice que el número de Ramsey [math] R (3, 3) [/ math] es igual a [math] 6 [/ math] (ver el teorema de Ramsey para una definición más completa).

De manera similar, si [math] 18 [/ math] personas están en una fiesta, entonces [math] 4 [/ math] se conocen entre sí, o [math] 4 [/ math] no saben El uno al otro. Además, esto no es cierto si [math] 18 [/ math] es reemplazado por [math] 17 [/ math]. Esto dice que el número de Ramsey [math] R (4, 4) [/ math] es igual a [math] 18 [/ math].

Es un problema abierto determinar el valor de [math] R (5, 5) [/ math].

Este es particularmente frustrante porque, a diferencia de muchos de los otros ejemplos aquí, en principio, resolver este problema implica verificar muchos casos. ¡Pero hay demasiados casos!

Permítanme citar una de mis otras respuestas:

Un estadístico deshonesto quiere probar que la probabilidad de que una moneda salga cara es significativamente mayor que la mitad. Puede lanzar la moneda cualquier número de veces y detenerse de acuerdo con cualquier regla que no dependa de los resultados futuros. Sin embargo, una vez que se detiene, tiene que informar la proporción exacta de cabezas que tiene. ¿Cuál es su mejor estrategia para maximizar su proporción esperada?

A menos que esto se resolviera en el último año, sigue siendo un problema abierto. Creo que sí tenemos respuesta al análogo continuo del problema, y ​​que es solo la discreción de esta versión lo que lo hace difícil.

Cuboide perfecto

¿Existe un cuboide ( es decir , una caja rectangular) cuyos bordes, diagonales de cara y diagonal de cuerpo tienen longitudes de enteros?

Se ha demostrado que todo lo siguiente es posible:

  • Todos los bordes y diagonales de cara de longitud entera (ladrillo de Euler), pero no diagonal del cuerpo
  • Todos los bordes y dos de las tres diagonales de cara de longitud entera, junto con la diagonal del cuerpo
  • Todas las diagonales de la cara y la diagonal del cuerpo de longitud entera, pero solo dos de los tres bordes
  • Paralipípedo con todos los bordes, diagonales de cara y diagonal del cuerpo de longitud entera, donde cuatro de las seis caras son rectangulares

Pero a partir de ahora, nadie ha encontrado un cuboide perfecto, ni nadie ha demostrado que uno no pueda existir.

Encuentre 157 subconjuntos, cada uno de tamaño 13, de un conjunto X que a su vez tiene un tamaño de 157, de manera que cada par de subconjuntos tenga exactamente un elemento en común.

Tal colección correspondería a un plano proyectivo (finito) de orden 12 (note que 157 = 12 ^ 2 + 12 + 1). Se sabe que para cada potencia principal q existe un plano proyectivo de orden q, es decir, una colección de (q + 1) -subsets de un conjunto de tamaño q ^ 2 + q + 1 con la propiedad de que cada par de subconjuntos tienen exactamente un elemento en común. Y si conoce algún álgebra lineal básica sobre campos finitos, entonces es fácil construir un plano proyectivo de este tipo.

El teorema de Bruck-Ryser-Chowla muestra que si existe un plano proyectivo de orden n y n deja un resto de 1 o 2 cuando se divide entre 4, entonces n debe ser una suma de dos cuadrados. Esto excluye la posibilidad de un plano proyectivo de orden 6. El número más pequeño que se escapa a este teorema es 10. Desde 1980 a 1989, Lam y sus colaboradores trabajaron en una búsqueda por computadora para encontrar un plano proyectivo de orden 10 usando varias ideas y resultados. De la teoría de la codificación, la teoría de grupos y la geometría finita. Finalmente demostraron que no existe tal plano proyectivo. Vea esta bonita encuesta de Lam: la búsqueda de un plano proyectivo finito de orden 10.

El siguiente caso más pequeño a considerar es el orden 12. Y estamos atascados. Casi no ha habido ningún progreso significativo en la resolución de ese problema (consulte esta publicación de Mathoverflow: Proyective Plane of Order 12). La conjetura es que no existe tal plano. Y una versión más sólida de esta conjetura es que los planos proyectivos finitos existen solo para el orden de poder principal. Esta es la llamada conjetura de poder primordial.

El problema del vendedor ambulante.
Problema de vendedor ambulante

“Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen? Es un problema NP-difícil en la optimización combinatoria, importante en la investigación de operaciones y teoria computacional “.

Creo que el teorema de los cuatro colores es una opción obvia. Muestre que cualquier gráfico plano es de 4 colores (a menudo se explica como: puede colorear cualquier país en un mapa con un máximo de 4 colores distintos, de manera que no haya dos países adyacentes del mismo color). Se ha comprobado, pero es bastante complicado.

Sin embargo, cuando se trata de afirmaciones simples que son difíciles de probar, no hay una mina de oro más grande que las primas . Aquí hay unos ejemplos:

  • ¿Existen infinitas p para que p y p + 2 sean primos? Esto está abierto: conjetura prima gemela.
  • Para cualquier a y b, existen infinitos n tales que a + bn es primo. Esto se conoce como el teorema de Dirichlet. Es difícil, pero se probó en 1837, y creo que puedes leer la prueba si solo sabes algo de teoría y análisis de números.
  • Existen secuencias aritméticas arbitrariamente largas (a, a + b, …, a + bn) de primos. Este es el teorema de Green-Tao. Fue probado en 2004, por lo que es un poco más difícil que el de Dirichlet. Realmente no sé lo que está involucrado.

Sin duda, el teorema de la curva de Jordania.

Declaración: “Cualquier curva cerrada divide el plano en una parte interna y una parte externa”.
Prueba: Realmente, realmente no es trivial. Ver la topología de Munkres para una buena presentación.

Un candidato es la conjetura de Goldbach. Es una de las conjeturas más antiguas y más conocidas de la teoría numérica, que establece que

Cada número par mayor que 2 puede expresarse como la suma de dos primos.

Hay una conjetura más débil, llamada acertadamente la débil de Goldbach, que también atrajo mucha atención y finalmente fue probada por Harald Helfgott tan recientemente como en 2013.

Cada número impar mayor que 5 puede expresarse como la suma de tres primos.

También hay una novela muy buena que romantiza el esfuerzo de un hombre por atacar este problema: la tesis de Tío Petros y Goldbach: una novela de obsesión matemática.

P vs. NP

Conceptualmente, ¿una solución a un problema que puede ser verificada rápidamente por una computadora también puede ser resuelta rápidamente por una computadora?

Este problema es lo suficientemente difícil como para que aún no se haya resuelto, y hay una recompensa de $ 1 millón para quien demuestre que P = NP o P ≠ NP.

Nota: di una definición informal del problema, pero aquí hay algunos detalles más.

En términos más técnicos, rápidamente significa tiempo polinomial. Resolver significa encontrar la solución en una máquina de Turing determinista y verificar significa encontrar la solución en una máquina de Turing no determinista.

Aquí están algunas:

La conjetura de Twin Prime.

Los números primos son aquellos unicornios mágicos que solo son divisibles por sí mismos y 1. Por lo que sabemos, hay un número infinito de números primos, y los matemáticos están trabajando duro para encontrar constantemente el siguiente número primo más grande.

Pero, ¿hay una cantidad infinita de pares de números primos que difieran en dos, como 41 y 43? A medida que los números primos se hacen más y más grandes, estos números primos gemelos son más difíciles de encontrar, pero en teoría, deberían ser infinitos … el problema es que nadie ha podido demostrarlo todavía.

El problema del sofá móvil

Esto es algo con lo que la mayoría de nosotros hemos luchado antes: te estás mudando a un nuevo apartamento e intentando llevar tu viejo sofá. Pero, por supuesto, tiene que maniobrar en una esquina antes de que pueda sentirse cómodo en su sala de estar.

En lugar de darse por vencido y simplemente comprar una bolsa de frijoles, en este punto, los matemáticos quieren saber: ¿cuál es el sofá más grande que podrías colocar alrededor de una esquina de 90 grados, independientemente de la forma, sin que se doble? (Aunque están mirando todo desde una perspectiva bidimensional).

La conjetura de Collatz.

La conjetura de Collatz es uno de los problemas matemáticos no resueltos más famosos, porque es muy simple, puedes explicárselo a un niño en edad de escuela primaria, y probablemente estarán lo suficientemente intrigados como para intentar encontrar la respuesta por sí mismos.

Así es como va: elige un número, cualquier número.

Si es par, divídalo entre 2. Si es impar, multiplíquelo por 3 y agregue 1. Ahora repita esos pasos nuevamente con su nuevo número. Eventualmente, si continúa, terminará con 1 cada vez (pruébelo usted mismo, esperaremos).

Tan simple como suena, realmente funciona. Pero el problema es que a pesar de que los matemáticos han demostrado que este es el caso de millones de números, no han encontrado ningún número que no se adhiera a las reglas.

“Es posible que haya un número realmente grande que llegue al infinito, o tal vez un número que se atasque en un bucle y nunca llegue a 1”, explica Thompson. “Pero nadie ha podido demostrarlo con certeza”.

La conjetura de Beal.

La conjetura de Beal básicamente es así …

Si A ^ x + B ^ y = C ^ z

Y A, B, C, x, y y z son todos enteros positivos (números enteros mayores que 0), entonces A, B y C deberían tener un factor primo común.

Un factor primo común significa que cada uno de los números debe ser divisible por el mismo número primo. Entonces, 15, 10 y 5 tienen un factor primo común de 5 (todos son divisibles por el número primo 5).

Hasta ahora, tan simple, y parece algo que habrías resuelto en el álgebra de la escuela secundaria.

Pero aquí está el problema. Los matemáticos nunca han sido capaces de resolver la conjetura de Beale, con x, y, yz, todos mayores que 2.

Por ejemplo, usemos nuestros números con el factor primo común de 5 de antes …

5 ^ 1 + 10 ^ 1 = 15 ^ 1

pero

5 ^ 2 + 10 ^ 2 ≠ 15 ^ 2

Actualmente hay un premio de US $ 1 millón en oferta para cualquier persona que pueda ofrecer una prueba revisada por pares de esta conjetura … así que calcule.

El problema de la plaza inscrita

Este requiere un pequeño dibujo. En una hoja de papel, dibuje un bucle, no tiene que ser una forma determinada, solo un bucle cerrado que no se cruce por sí solo.

De acuerdo con la hipótesis del cuadrado inscrito, dentro de ese bucle, deberías poder dibujar un cuadrado que tenga las cuatro esquinas tocando el bucle, como en el diagrama de arriba.

Suena simple … pero matemáticamente hablando, hay muchas formas de bucle posibles por ahí, y actualmente es imposible decir si un cuadrado podrá tocarlas todas.

La conjetura de Goldbach.

Similar a la conjetura de Twin Prime, la conjetura de Goldbach es otra pregunta aparentemente simple acerca de los números primos y es famosa por lo engañosamente fácil que es. La pregunta aquí es: ¿es cada número mayor que 2 la suma de dos números primos?

Parece obvio que la respuesta sería sí, después de todo, 1 + 2 = 3, 3 + 1 = 4, y así sucesivamente.

Pero, una vez más, nadie ha podido probar que este siempre será el caso, a pesar de los años de intentos.

La realidad es que, a medida que continuamos calculando números cada vez más grandes, podemos encontrar uno que no sea la suma de dos números primos … o los que desafían todas las reglas y la lógica que tenemos hasta ahora. Y puedes estar seguro de que los matemáticos no dejarán de buscar hasta que lo encuentren.

Los pares de números primos que están separados por solo 2, como 3 y 5, 5 y 7, 11 y 13, o 101 y 103, se llaman primos gemelos. ¿Hay infinitos primos gemelos?

Este problema simple todavía es una conjetura abierta. Hace solo dos años, Yitang Zhang logró demostrar que para un entero N menor a 70 millones, hay infinitos primos que difieren en N. Tal vez 2 es uno de esos enteros.

Ver Twin Prime para más información.

Puede obtener una lista bastante completa aquí:

No especialmente famosos, problemas abiertos que cualquiera puede entender.

Números de Ramsey !!

Estás organizando una fiesta. Cada par de asistentes es un par de amigos o un par de enemigos. Se dice que un grupo de personas son amigos mutuos (enemigos) si cada pareja en el grupo es amigo (enemigos).

¿Cuántas personas debes tener en la fiesta para garantizar que tienes 3 amigos comunes o 3 enemigos comunes?

La respuesta a esta pregunta es 6. (Más sobre cómo mostrar esto más adelante). Cualquier grupo de 6 personas tendrá 3 amigos comunes o 3 enemigos comunes. Para establecer una notación, acordemos que [math] R (3,3) = 6 [/ math], donde los primeros 3 denotan el número de amigos y los segundos 3 denotan el número de enemigos.

Entonces [math] R (k, j) [/ math] es el número de asistentes que necesitarás para garantizar [math] k [/ math] mutuo amigos o [math] j [/ math] mutuo enemigos.

El Teorema de Ramsey se puede usar para mostrar que [math] R (k, j) [/ math] es finito para cada [math] k, j [/ math]. Sin embargo, el cálculo del valor exacto de [math] R (k, j) [/ math] solo se ha realizado en algunos casos especiales.

Veamos nuevamente [math] R (3,3) [/ math]. Considere colocar un punto en el plano para cada persona en la fiesta y conectar los puntos entre cada grupo de amigos con una línea roja y los puntos entre cada grupo de enemigos con una línea azul. Considere la siguiente colección de 5 personas o puntos.
Puede verificar que ninguna colección de 3 puntos forme un triángulo con todos los lados del mismo color. Por lo tanto, en esta fiesta, no hay ninguna colección de 3 amigos comunes o 3 enemigos comunes. Debemos tener que [math] R (3,3)> 5 [/ math]. ¿Cómo podemos realmente probar que el valor verdadero es 6?

  • Toma cualquier gráfico de 6 vértices donde todos los bordes hayan sido de color rojo o azul.
  • Elija uno de los 6 vértices y considere todos los bordes que se extienden desde este vértice. Como hay otros 5 puntos, hay 5 bordes que se extienden desde el vértice.
  • Al menos 3 aristas deben tener el mismo color. Digamos que al menos 3 aristas son azules.
  • Ahora considera los 3 puntos al final de estos bordes azules. Si alguno de ellos está conectado por una línea azul, estos dos puntos y el primer punto forman un triángulo azul, por lo que encontraremos 3 enemigos mutuos.
  • La única otra opción es que ninguno de estos tres puntos esté conectado por una línea azul. Entonces estos 3 puntos están todos conectados por líneas rojas. ¡Así, forman un triángulo rojo! Tres amigos mutuos!

Hemos demostrado que cualquier grupo con 6 personas debe tener 3 amigos comunes o tres enemigos comunes, por lo que [math] R (3,3) = 6 [/ math].

Probablemente parece que se podrían hacer argumentos similares para encontrar otros valores [math] R (k, j) [/ math]. Resulta que no es tan fácil. El número de gráficos con vértices [math] n [/ math] que están conectados por un solo borde rojo o azul es [math] 2 ^ {\ frac {n (n-1)} {2}} [/ math] , y aunque muchos de estos son fácilmente verificables o removibles por argumentos de simetría, el número de gráficos crece tan rápido que sin una teoría sólida para eliminar muchos de estos gráficos, ni siquiera podemos diseñar un algoritmo para verificar todos los gráficos de un cierto tamaño

Se ha demostrado que [math] R (4,4) = 18 [/ math]. Tenga en cuenta que esto requiere producir una gráfica con 17 vértices donde no haya grupos de 4 vértices mutuamente de color rojo o azul. Existen
[math] 2 ^ {17 * 16/2} = 8.7… * 10 ^ {40} [/ math] gráficas con 17 vértices, por lo que no hay posibilidad de realizar una búsqueda exhaustiva en una computadora para encontrar dicha gráfica. Una vez que tengamos este ejemplo, todavía tenemos que demostrar que cada gráfico con 18 vértices tiene las propiedades requeridas.

Aún más interesante es que [math] R (k, k) [/ math] aún se desconoce para todos [math] k> 4 [/ math]. Se sabe que [math] R (5,5) [/ math] está entre 43 y 49, pero aún no podemos encontrar el valor exacto.

El famoso Paul Erdos tuvo un maravilloso comentario sobre estos números.

“Supongamos que los extraterrestres invaden la tierra y amenazan con destruirla en un año, a menos que los seres humanos puedan encontrar el número Ramsey para el cinco rojo y el azul cinco. Podríamos reunir a las mejores mentes del mundo y las computadoras más rápidas, y dentro de un año probablemente podríamos calcular el “Si los alienígenas exigieran el número de Ramsey para el seis rojo y el azul seis, no tendríamos más remedio que lanzar un ataque preventivo”.

-Como se cita en “La teoría de Ramsey” por Ronald L. Graham y Joel H. Spencer, en Scientific American (julio de 1990), pág. 112-117

Puedo añadir la conjetura de Collatz:

1) Comience con cualquier entero positivo [math] n [/ math].
2) Si [math] n [/ math] es 1, deténgase.
3) Si [math] n [/ math] es par, divídelo entre dos.
4) Si [math] n [/ math] es impar, multiplíquelo por tres y agregue 1.
5) Vaya al paso 2.

La conjetura de Collatz es: este algoritmo siempre se detendrá, es decir, el número 1 siempre aparecerá con el tiempo.

Muy simple de proponer, pero es tan difícil probar que nadie lo ha logrado todavía. El notable matemático Erdös una vez ofreció $ 500 para su solución.

a) Números de Lychrel:

Un número de Lychrel es un número natural que no puede formar un palíndromo mediante el proceso iterativo de invertir repetidamente sus dígitos y sumar los números resultantes.

En la base diez, aún no se ha demostrado que existan números de Lychrel, pero muchos, incluso 196, son sospechosos por razones heurísticas y estadísticas.

b) ¿Hay infinitos números primos de la serie Fibonacci?

Un primo de Fibonacci es un número de Fibonacci que es primo, un tipo de primo de secuencia de enteros.

c) Demostrar que 10 es un número solitario.

En teoría de números, los números amigos son dos o más números naturales con una abundancia común, la relación entre la suma de los divisores de un número y el número en sí. Dos números con la misma abundancia forman un par amistoso; N números con la misma abundancia forman un amistoso n- tupla.
Ser mutuamente amigables es una relación de equivalencia, y por lo tanto induce una partición de los naturales positivos en clubes (clases de equivalencia) de números mutuamente amigables.
Un número que no forma parte de ningún par amigo se llama solitario.

Mención de Honor:

La conjetura abc

La conjetura abc (también conocida como la conjetura Oesterlé-Masser ) es una conjetura en la teoría de los números, propuesta por primera vez por Joseph Oesterlé (1988) y David Masser (1985) como un análogo entero del teorema de Mason-Stothers para polinomios. La conjetura se expresa en términos de tres enteros positivos, a , byc (de ahí el nombre), que no tienen factores comunes mayores que 1 y satisfacen a + b = c . Si d denota el producto de los distintos factores primos de abc , la conjetura esencialmente dice que d no suele ser mucho menor que c . En otras palabras: si a y b se componen de grandes poderes de primos, entonces c no suele ser divisible por grandes poderes de primos. La declaración precisa se da a continuación.

Fuentes:
Lista de problemas no resueltos en matemáticas.
Problemas sin resolver
Numero de Lychrel
Numero amistoso
Fibonacci Prime
conjetura abc
La teoría matemática más compleja del mundo ‘agrietada’
Número solitario – de Wolfram MathWorld

El Teorema del mapa de cuatro colores, dicho de manera simple, dice que solo se necesitan cuatro colores para colorear cualquier mapa, de modo que ninguna región que comparta un borde común tenga el mismo color. Un niño de cinco años puede entender esto, pero la prueba más corta conocida es tan larga e intrincada que se requiere una computadora para la verificación de una manera esencial.

Para plantear el problema precisamente en el lenguaje matemático, un “mapa” debe definirse como una separación de un plano en regiones, y las regiones no pueden ser extrañas, como tener un área finita pero bordes infinitamente ondulados.

El problema cautivó a los matemáticos durante más de 100 años, hasta que finalmente fue probado en 1976 por Appel y Haken. Este fue el primer ejemplo de un importante teorema matemático al que se le debe dar una prueba que requiere una computadora para su verificación.

Teorema de cuatro colores

Dado un conjunto de enteros que no tienen divisores comunes, por lo tanto, si se da [math] A = \ {2,3,5 \} [/ math], ¿qué podemos decir acerca de los números que se pueden desglosar como una suma? de (posiblemente múltiple) [math] 2 [/ math] ‘s, [math] 3 [/ math]’ s, y [math] 5 [/ math] ‘s? ¿Qué tan grandes pueden ser estos números? Resulta que para números lo suficientemente grandes podemos expresarlos todos como una suma de estos números. Pero ¿qué pasa si alguien pregunta “Bueno, ¿qué tan grandes deben ser los números?” Luego puede mirar el número más pequeño, de modo que cada número posterior sea una suma de su conjunto original, llame a este [math] F (A) [/ math], o puede ver el número más grande que no se puede expresar como suma de números de su conjunto, llame a [math] G (A) [/ math]. Resulta que [math] F (A) = G (A) +1 [/ math] pero para un conjunto arbitrario [math] A [/ math] encontrar uno de estos es un problema abierto.

Por lo tanto, una aplicación del mundo real es si su pollo McNuggets que lo solicita, que viene en tamaños de [math] \ {4,6,9,20 \} [/ math], ¿qué número de McNuggets no puede ordenar?

Cuando los números que estamos multiplicando están separados por 2 (ejemplo 7 y 5), multiplique el número en el medio por sí mismo y reste uno.

(6 * 6 – 1 en este caso)

Por ejemplo :
5 × 5 = 25 es solo uno más grande que 6 × 4 = 24
6 × 6 = 36 es solo uno más grande que 7 × 5 = 35
7 × 7 = 49 es solo uno más grande que 8 × 6 = 48
8 × 8 = 64 es solo uno más grande que 9 × 7 = 63


Multiplicando por nueve

Cuando esté multiplicando por 9, en sus dedos (comenzando con su pulgar) cuente el número por el que está multiplicando y mantenga presionado ese dedo. El número de dedos antes de que se mantenga presionado es el primer dígito de la respuesta y el número de dedos después de que se mantenga presionado es el segundo dígito de la respuesta.


Multiplica hasta 19X19 en tu cabeza

Digamos que necesitas multiplicar 15X13

1.) Siempre coloca en tu mente el número mayor de los dos (15 en este caso)

2.) Agréguelo con el segundo dígito del número más bajo (15 + 3 = 18 – Llamémoslo A )

3.) Resta el número inferior por su segundo dígito (13-3 = 10 – Llamémoslo B)

4.) Ahora multiplica A por B (18 * 10 = 180 – Llamémoslo C

5.) Ahora multiplica el segundo dígito de ambos números (5 * 3 = 15 – Llamémoslo D )

6.) Agregue C & D para ver su respuesta (180 + 15 = 195)

El Problema P v. NP. Es un problema fundamental para los informáticos y matemáticos. Pregunta si un problema en el que se puede verificar fácilmente la solución también se puede encontrar fácilmente usando una computadora. Una solución si se encuentra, tendría enormes implicaciones. Por ejemplo, los mensajes cifrados se basan en ser difíciles de resolver.

Si está buscando problemas que sean fáciles de expresar, creo que la conjetura de Goldbach es de la misma variedad. La conjetura es que cualquier entero par n> 2 se puede expresar como la suma de 2 números primos.

Esta conjetura actualmente es un problema sin resolver en matemáticas.

Otro resultado simple que requiere cierto trabajo para demostrarlo es el cambio de la fórmula de variables en múltiples dimensiones (una declaración más completa del teorema está en el enlace) [math] \ int _ {\ phi (U)} f (\ textbf {u} ) d \ textbf {u} = \ int_U f (\ phi (\ textbf {u})) | det J_ \ phi | d \ textbf {u} [/ math] para el cual se muestra una prueba aquí http://www.math.ualberta.ca/~xic