Ejemplos de patrones que acaban fracasando

Question

A menudo, cuando intento describir las matemáticas a los profanos, me veo en apuros para convencerles de la importancia y las consecuencias de las "pruebas". Recibo respuestas como: "seguramente si Collatz es cierto hasta $20×2^{58}$ y "la secuencia del número de aristas de un grafo completo empieza por $0,1,3,6,10$ por lo que el siguiente plazo debe ser 15, etc.".

Es cierto que esta segunda afirmación es menos ilógica que la primera, ya que no es difícil ver la razón por la que la secuencia debe continuar como tal; sin embargo, la afirmación se basa en una premisa que se reduce a que "los patrones interesantes siempre deben continuar".

Intento contrarrestar esta lógica creando un argumento ridículo como "los números $1,2,3,4,5$ son inferiores a $100$ por lo que seguramente todos los números lo son", pero esto no suele resultar convincente.

Entonces, ¿hay algún ejemplo de patrones no triviales que parezcan ser ciertos para un gran número de casos pequeños, pero que luego fallen para algún caso más grande? Una buena respuesta a esta pregunta debería:

1. que pueda explicarse a los profanos en la materia sin tener que someterlos a 24 clases magistrales de material de base, y
2. tienen como contraejemplo mínimo un caso que no puede (factiblemente) comprobarse sin el uso de un ordenador.

Creo que las condiciones 1. y 2. hacen que mi pregunta sea lo suficientemente específica como para tener en cierto sentido una respuesta "correcta" (o al menos "no errónea"); pero estaré encantado de aclararlo si no es así. Supongo que espero una respuesta de la teoría de números, pero veo que áreas como la teoría de grafos, la combinatoria en general y la teoría de conjuntos podrían ofrecer respuestas adecuadas.

Answer 1

Traduciré una entrada en el blog Gaussianos ("Gaussianos") sobre la conjetura de Polya, titulada:

UNA CREENCIA NO ES UNA PRUEBA.

Diremos que un número es de tipo par si en su factorización prima aparece un número par de primos. Por ejemplo $6 = 2\cdot 3$ es un número par. Y diremos que un número es de tipo impar si el número de primos en su factorización es impar. Por ejemplo, $18 = 2·3·3$ es de tipo impar. ( $1$ se considera de tipo par).

Sea $n$ cualquier número natural. Consideraremos los siguientes números:

1. $E(n) =$ número de enteros positivos menor o igual que $n$ que son de la misma clase.
2. $O(n) =$ número de enteros positivos menor o igual que $n$ que son de tipo impar.

Consideremos $n=7$ . En este caso $O(7) = 4$ (el propio número 2, 3, 5 y 7) y $E(7) = 3$ ( 1, 4 y 6). Así que $O(7) >E(7)$ .

Para $n = 6$ : $O(6) = 3$ y $E(6) = 3$ . Así $O(6) = E(6)$ .

En 1919, George Polya propuso el siguiente resultado, conocido como la conjetura de Polya:

Para todos $n > 2$ , $O(n)$ es mayor o igual que $E(n)$ .

Polya había comprobado esto por $n < 1500$ . En los años siguientes se probó hasta $n=1000000$ por lo que se podría pensar que la conjetura es cierta. Pero eso es erróneo.

En 1962, Lehman encontró un contraejemplo explícito: para $n = 906180359$ tenemos $O(n) = E(n) – 1$ así que..:

$$O(906180359) < E(906180359).$$

Mediante una búsqueda exhaustiva, el contraejemplo más pequeño es $n = 906150257$ encontrado por Tanaka en 1980.

Por tanto, la conjetura de Polya es falsa.

¿Qué aprendemos de esto? Pues muy sencillo: desgraciadamente en matemáticas no podemos fiarnos de la intuición ni de lo que ocurre para un número finito de casos, por muy grande que sea el número. Hasta que no se demuestre el resultado para el caso general, no tenemos la certeza de que sea cierto.

Answer 2

De "Experimentation in Mathematics" Borwein, Bailey y Girgensohn 2004 : $$\sum_{n=1}^{\infty} \lfloor n\cdot e^{\frac{\pi}3\sqrt{163}}\rfloor 2^{-n}=1280640\ \ \text{(correct to at least half a billion digits!)}$$ Utilización de la $\mathrm{sinc}$ función ( $\mathrm{sinc}(x)=\frac{\sin(x)}x$ y esto papel ) : $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdot \mathrm{sinc}\left(\frac x5\right)\,\mathrm dx=\frac{\pi}2$$ $$\cdots$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdot \mathrm{sinc}\left(\frac x5\right)\cdots \mathrm{sinc}\left(\frac x{13}\right)\,\mathrm dx=\frac{\pi}2$$ $$\int_0^{\infty} \mathrm{sinc}\left(\frac x1\right)\cdot \mathrm{sinc}\left(\frac x3\right)\cdots \mathrm{sinc}\left(\frac x{15}\right)\,\mathrm dx=\frac{467807924713440738696537864469}{ 935615849440640907310521750000}\pi$$

---

De hecho, la historia no acaba aquí. Se descubrió (véase el artículo de Baillie y Borweins "Sumas e integrales sorprendentes de Sinc" ) que podrías sustituir las integrales por las correspondientes $\frac 12 + \sum_1^{\infty}$ serie : $$\frac 12 + \sum_{m=1}^{\infty} \prod_{k=0}^N \mathrm{sinc}\left(\frac m{2k+1}\right)=\int_0^{\infty} \prod_{k=0}^{N} \mathrm{sinc}\left(\frac x{2k+1}\right)\,\mathrm dx.$$

para los valores anteriores de ( $N=0,1,2,3\cdots 7$ ) pero también para valores mayores de $N$ hasta $40248$ . Para $N\gt 40248$ ¡la parte izquierda siempre es mayor que la integral de la derecha!

En este punto, los recíprocos de los números enteros Impares podrían sustituirse por otros valores (véanse en el documento las condiciones necesarias para que se cumpla la igualdad), por ejemplo, por los recíprocos de los números primos. Ahora bien, debido a la divergencia lenta en este caso, la igualdad sólo se rompe para $N \approx 10^{176}$ (cuando la suma de valores cruza lentamente el $2\pi$ barrera) y con un error inferior a $\displaystyle 10^{-10^{86}}$ .

Answer 3

El documento fundamental al respecto es el de Richard Guy La poderosa ley de los números pequeños Proclamando que "no hay suficientes números pequeños para satisfacer las muchas demandas que se les hacen", enumera $35$ patrones que no dan resultado. Otros han ampliado la "ley de los números pequeños", como por ejemplo aquí (y algunos enlaces más en esa página)

Un ejemplo especialmente bueno es el del segundo enlace:

• $\gcd(n^{17}+9, (n+1)^{17}+9)$ parece estar siempre $1$ . De hecho, si tuvieras tu ordenador comprobando esto por $n=1, 2, 3, \dots$ sucesivamente, nunca encontraría un contraejemplo. Esto se debe a que el primer contraejemplo es $$8424432925592889329288197322308900672459420460792433\;.$$

Answer 4

Elige n puntos alrededor de la circunferencia de un círculo y une cada punto con cada uno de los demás mediante un segmento de recta. Suponiendo que no coincidan tres de los segmentos de recta, ¿en cuántas regiones divide esto el círculo?

Hay un patrón bastante obvio, que se rompe en n=6.

Answer 5

Reclamación: Los polinomios ciclotómicos $\phi_n(x)$ tienen coeficientes en el conjunto $$\{ -1, 0, 1 \}$$

Se cumple para cualquier número que no tenga al menos $3$ factores primos Impares distintos, lo que significa que el contraejemplo más pequeño es $3 \cdot 5 \cdot 7 = 105$ . Así que un estudiante ingenuo probablemente nunca verá un contraejemplo a menos que se le muestre específicamente $\phi_{105}$ .