En Gaussianos ya hemos hablado del principio de inducción en alguna ocasión. En este post vamos a ver una curiosa propiedad de los números naturales y vamos a demostrarla por este método.
Comencemos volviendo a enunciar el principio de inducción:
Supogamos que tenemos un subconjunto A de números naturales que verifica lo siguiente:
1.- 0 pertenece a A
2.- Si k pertenece a A entonces k+1 pertenece a A
Entonces A es el propio conjunto N de los números naturales
Si cambiamos 0 por cualquier otro número natural, digamos m, en el punto 1.- obtendríamos que el conjunto A sería exactamente el subconjunto de los números naturales cuyo elemento mínimo es m. Por ejemplo, si m=4 y se cumplen 1.- y 2.- entonces A={4,5,6,7,…}.
En esta ocasión volveremos a utilizarlo de la misma forma que se hizo en el post que enlazamos en el primer párrafo, pero comenzando en 1: si nuestra propiedad se cumple para el 1 y en el caso de que se cumpla para cierto número natural n entonces se cumple para n+1 se tiene que se cumple para todos los números naturales a partir del 1.
Vamos ahora con la propiedad de la que hablamos al comienzo:
(Sigue leyendo …)
En Gaussianos ya hemos hablado unas cuantas veces de Leonhard Euler (véanse, por ejemplo, la identidad de Euler y el problema de Basilea). Es uno de los matemáticos más grandes de la historia, y el que más publicaciones matemáticas tiene a su nombre. Se interesó por muchas de las ramas de las matemáticas y realizó aportaciones a muchas de ellas. Pero todo esto no le da fiabilidad total. Veamos cómo los genios también se equivocan.
Esta conjetura de Euler está inspirada en el último teorema de Fermat. Este resultado dice que xn+yn=zn no tiene soluciones enteras positivas cuando n > 2. El resultado que Euler propuso en 1769 puede formularse de la siguiente forma:
No existen n-1 números tal que sus potencias n-ésimas suman otra potencia n-ésima
Esta afirmación dice que, por ejemplo, las siguientes ecuaciones no tienen soluciones enteras positivas:
a4+b4+c4=d4
a5+b5+c5+d5=e5
La relación con el último teorema de Fermat se ve claramente…pero a diferencia de éste la conjetura es falsa. En 1966 Lander y Parkin encontraron el siguiente contraejemplo:
275+845+1105+1335=1445
Es decir, la conjetura es falsa ya que hemos encontrado un contraejemplo para un cierto n, n=5 concretamente. Pero podría ser cierta para n=4. En 1986 Noam Elkies se encargó de refutar la conjetura también para este n encontrando el siguiente contraejemplo mediante un método construido por él mismo:
26824404+153656394+187967604=206156734
En 1988 Roger Frye, usando las técnicas sugeridas por Elkies, encontró el contraejemplo más pequeño para n=4:
958004+2175194+4145604=4224814
En esta página se publican los ejemplos que van encontrando que cumplen alguna de las ecuaciones de este tipo. En esta sección podéis ver algunos. Son los que tienen delante un (n,1, n-1).
Por ejemplo, en marzo de 2006 encontraron el siguiente contraejemplo bestial:
224955952840404+75924319813914+272397916926404=299998579386094
Por tanto aquí tenemos otro ejemplo de conjetura que tiempo después acaba resultando falsa (véase la conjetura de Polya).
Fuente: Math is Good For You
Hace ya tiempo hablamos de una lista de tipos de números, en la cual se exponían un montón de tipos de números.
Hoy toca explicar uno que me he encontrado de casualidad en la wikipedia, el número de Dudeney.
Este es un número entero que es un cubo perfecto y, a su vez, la suma de los dígitos que componen dicho número da como resultado la raíz cúbica de dicho número. El nombre viene de Henry Dudeney, que observó la existencia de estos números en uno de sus rompecabezas.
En la siguiente tabla se muestran algunos, supongo que habrá más, de estos números:
| Cubo perfecto |
Suma de sus dígitos |
| 1 = 1 x 1 x 1 |
1 = 1 |
| 512 = 8 x 8 x 8 |
8 = 5 + 1 + 2 |
| 4913 = 17 x 17 x 17 |
17 = 4 + 9 + 1 + 3 |
| 5832 = 18 x 18 x 18 |
18 = 5 + 8 + 3 + 2 |
| 17576 = 26 x 26 x 26 |
26 = 1 + 7 + 5 + 7 + 6 |
| 19683 = 27 x 27 x 27 |
27 = 1 + 9 + 6 + 8 + 3 |
(Vía Wikipedia)
Elijamos un número natural, digamos n, y realicemos los siguientes cálculos:
- Si n es par dividámoslo por 2
- Si n es impar multipliquémoslo por 3 y sumémosle 1 al resultado
Con el número obtenido repitamos el proceso, y así sucesivamente. Hagámoslo con un ejemplo:
n = 6
La secuencia que obtenemos es:
6, 3, 10, 5, 16, 8, 4, 2, 1
Vemos que en unos cuantos pasos hemos llegado al número 1. Pues eso mismo es lo que dice la conjetura de Collatz (también conocida como conjetura 3n + 1, conjetura de Ulam o problema de Siracusa):
Conjetura de Collatz
Para cualquier número natural n realicemos los siguientes cálculos:
- Si n es par dividámoslo por 2
- Si n es impar multipliquémoslo por 3 y sumémosle 1 al resultado
Repitiendo el proceso con los números obtenidos la secuencia siempre acabará en 1
Ya hemos visto la secuencia que obtenemos comenzando por 6. Si escogemos n = 11 obtenemos:
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Una secuencia algo más larga, pero que también termina en 1. Y con n = 27, un número ciertamente pequeño, obtenemos una secuencia considerablemente grande: 111 pasos
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Imaginad las secuencias que obtendríamos con números grandes.
Este resultado sigue siendo una conjetura ya que no se tiene demostración alguna de su veracidad ni nadie ha encontrado ni contraejemplo ni demostración que demuestre su falsedad. Se ha comprobado que para números hasta 258 la secuencia siempre acaba en 1, es decir, la conjetura es cierta para esos números, pero eso no nos sirve como demostración. Sólo nos podría servir para intuir que podría ser cierto, pero la intuición a veces puede fallar, y si no recordar el caso de la conjetura de Polya.
Si alguien se atreve con el problema y obtiene algún resultado interesante que no dude en comunicárnoslo.
Fuente: Wikipedia (inglés): Collatz conjecture
Actualización: Dos apuntes interesantes:
- Interesante forma de atacar el problema la propuesta por Asier. Puede que desarrollándola no se llegue a nada concluyente, pero es bastante original.
- Enric ha creado un programa para calcular las sucesiones de números que aparecen al comenzar por cualquier número. Tenéis que entrar aquí y escribir http://www.enric.es/php/conjetura-collatz/?f=número-que-queráis. Hasta 1000000000000 lo da bien. A partir de ahí llega al ciclo 4, 2, 1 y lo repite indefinidamente. Y 2000000000010 es el último número para el que ocurre eso. A partir de ahí aparecen números tan grandes que el programa muestra INF de forma indefinida. De todas maneras es muy interesante.
El problema de Basilea consiste en determinar cuál es el valor exacto de la suma de los cuadrados de los inversos de todos los números naturales, es decir, calcular la suma de la siguiente serie:
Este problema fue propuesto por primera vez por el matemático Pietro Mengoli en 1644 y fue popularizado por Jakob Bernoulli en 1689, pero ninguno de los dos lo resolvieron. Otros grandes matemáticos de la época, como Johann Bernoulli, Leibnitz y Wallis tampoco pudieron encontrar la solución (aunque este último calculó su valor con 3 decimales). Este hecho le dio al problema aún más importancia. Al final fue el genial Leonhard Euler quien le puso el cascabel al gato, como en muchas otras ocasiones. De hecho este problema se acabó denominando así porque tanto Euler como los Bernoulli residían allí. Veamos cómo lo hizo.
(Sigue leyendo …)
Vamos a terminar ya con la teoría de números elemental, que se me está haciendo demasiado larga.
Números pseudoprimos
Los matemáticos Chinos de la antigüedad creían que:
n primo 2n-1 ≡ 1 (mod (n))
Sin embargo se equivocaron y su condición sólo es válida en un sentido:
n primo => 2n-1 ≡ 1 (mod (n))
A los números que sin ser primos, cumplen la propiedad se les conoce como pseudoprimos.
Teorema pequeño de Fermat
Sea “p” primo y a ∈ Z no divisible por “p”. Entonces,
ap-1 ≡ 1 (mod (p))
Como podéis ver no es más que una mejora de la propiedad de los números pseudoprimos.
(Más información en Wikipedia)
(Sigue leyendo …)
Aritmética modular
Con las congruencias podemos establecer un conjunto de operaciones aritméticas, como:
Siendo a, b, c, d ∈ Z y m ∈ N, tales que a ≡ b (mod (m)) y c ≡ d (mod (m)). Entonces,
a + c ≡ b + d (mod (m))
a · c ≡ b · c (mod (m))
(Recordemos que el signo ≡ significa “congruente con” y no es lo mismo que el signo = que significa “igual a”)
A partir de esto, podemos definir las propiedades aritméticas para las sumas de congruencias:
- Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))
- Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))
- Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el elemento neutro de la suma)
- Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))
También podemos definir las propiedades aritméticas para el producto de congruencias:
- Propiedad cancelativa: a · c ≡ b · c (mod (m)) y MCD (m, c) = 1, entonces a ≡ b (mod (m))
- Propiedad asociativa: a · (b · c) (mod (m)) = (a · b) · c (mod (m))
- Elemento neutro: Existe un elemento 1 ∈ Zm, tal que a · 1 (mod (m)) = a (mod (m))
- Elemento inverso: Existe un elemento a-1 ∈ Zm para todo a ∈ Zm con MCD (a, m) = 1, tal que a · a-1 = 1 (recordemos que 1 es el elemento neutro del producto)
Además de todas estas propiedades también se cumple la propiedad distributiva: a · (b + c) (mod (m)) = (a · b) + (a · c) (mod (m))
(Más información en la Wikipedia)
Para acabar, os voy a dar unos ejemplos de usos de las congruencias:
- En el DNI: La letra de tu NIF se realiza del siguiente modo: Número DNI (mod 23) y el resultado se pasa a una tabla que relaciona números con letras.
- En la generación de números seudoaleatorios: Los números aleatorios que genera cualquier ordenador se calculan usando una sucesión basada en congruencias: Xn+1 = (a · Xn + c) (mod (m))
- En criptografía: De este tema os hablaré dentro de poco, por ahora saber que las congruencias son la base de toda la criptografía moderna: RSA, El Gamal, …
Hace un tiempo, exactamente en este comentario, dije que en mis primeros de carrera jugábamos a la Escoba en Zm. Este post va a servir para explicar cómo jugábamos.
La Escoba
Comencemos explicando qué es la Escoba (es decir, quien sepa jugar puede saltarse este punto y pasar al siguiente). La Escoba es un juego de cartas que se juega con la baraja española. Al comenzar el juego se reparten 3 cartas a cada jugador y se colocan 4 encima de la mesa. El valor de cada carta es el valor que marca su número, excepto para sota, caballo y rey que valen respectivamente 8, 9 y 10 puntos. El objetivo del juego es sumar 15 puntos con una de las cartas que tenemos en la mano y las cartas que creamos convenientes de las que hay en la mesa. Se juega por turnos. Si en alguno de nuestros turnos no podemos sumar 15 dejamos una de nuestras cartas en la mesa y pasamos el turno. Así hasta que terminan las cartas del mazo. Al final cada jugador cuenta sus puntos teniendo en cuenta que el que tenga más cartas suma 1 punto, el que tenga más oros suma otro, el que tenga más sietes suma otro y el que tenga el siete de oros suma otro. Si en algún momento conseguimos dejar la mesa sin cartas al sumar los 15 obtenemos una Escoba, que nos suma otro punto al final de la partida.
Espero haberme explicado más o menos bien. Si hay alguna duda echad un ojo al enlace que he puesto o preguntadlo en un comentario.
(Comentario: esas son las reglas de puntuación que he usado yo siempre; evidentemente cada persona tendrá su propia forma de puntuar. De hecho en el enlace que he puesto la puntuación es distinta. De todas formas eso no es importante ya que ahora se verá que la forma de puntuación de la Escoba en Zm es esencialmente distinta a todas ellas.)
La Escoba en Zm
La Escoba en Zm tiene las mismas reglas de juego que la Escoba normal. Donde cambia la cosa es en la forma de puntuar al final de cada partida. Quien tenga más oros se sigue llevando un punto, quien tenga más sietes otro y quien tenga el siete de oros otro. Cada Escoba conseguida sigue sumando también un punto. Lo que cambia es la forma de puntuar las cartas obtenidas. Como generalmente jugábamos 4 personas utilizaré ese ejemplo.
Lo primero de todo es saber qué es Zm. Este post de neok ayudará bastante. Suponiendo que ya sabemos de qué va el tema comenzamos:
Al comienzo de la partida se asigna un cierto Zm a cada jugador. Para seguir un orden se puede asignar Z2 al jugador que está a la derecha de quien reparte, Z3 al de su derecha, Z4 al siguiente y Z5 al último, al que reparte las cartas. Se juega la partida normal y al finalizar se cuentan las cartas de cada uno de los jugadores. Digamos que un jugador obtiene k cartas. La puntuación obtenida por ese jugador será k (mód m), siendo m el correspondiente al Zm que se le asignó al principio. Así se hace con todos los jugadores.
Evidentemente para que el juego sea totalmente justo hay que jugar tantas manos con jugadores haya (en nuestro caso 4 manos) y debe cumplirse que al finalizar esas manos todos los jugadores hayan jugado cada una de ellas con un Zm distinto.
Al finalizar cada mano se apuntan los puntos obtenidos por cada jugador y quien más tenga al finalizar todas las manos gana la partida.
Bueno, ¿qué cambia respecto al anterior método de puntuación?. Pues muy sencillo. Antes quien tenía más cartas al finalizar la mano se llevaba un punto. Ahora cabe la posibilidad de que quien tenga más cartas no se lleve ninguno. Veamos un ejemplo:
Jugador A: Z2
Jugador B: Z3
Jugador C: Z4
Jugador D: Z5
Supongamos que al finalizar la partida las cartas queden repartidas de la siguiente forma:
A: 15
B: 12
C: 8
D: 5
En este caso las puntuaciones son:
A: 1 [15 (mód 2) = 1]
B: 0 [12 (mód 3) = 0]
C: 0 [8 (mód 4) = 0]
D: 0 [5 (mód 5) = 0]
En este caso quien tenía más cartas puntúa y el resto no puntúa. Pero veamos este otro ejemplo:
A: 18
B: 10
C: 8
D: 4
Las puntuaciones quedarían así:
A: 0 [18 (mód 2) = 0]
B: 1 [10 (mód 3) = 1]
C: 0 [8 (mód 4) = 0]
D: 4 [4 (mód 5) = 4]
En este caso quien tiene más cartas no puntúa, y además el que saca más puntos es quien llevaba menos cartas.
Se debe cambiar de Zm en cada mano para todos los jugadores porque quien tenga el Zm más grande parte con ventaja, ya que es quien a priori puede conseguir la mayor puntuación (aunque ya hemos visto que no tiene por qué ser así). Y además se debe pedir que quien pueda hacer 15 esté obligado a hacerlo, es decir, no se puede pasar si se tienen posibilidades de hacer 15 en un turno. ¿Por qué?. Muy sencillo. Porque, por ejemplo, el jugador de Z5 puede ir contando las cartas que va obteniendo y, por ejemplo, pararse cuando lleva 9, pasando en todos los turnos siguientes. Así se asegura 4 puntos al finalizar la mano. Se pueden ir contando las cartas que vamos obteniendo para intentar sacar el número que nos interesa (por ejemplo, si tenemos varias opciones para hacer 15 en un turno podemos elegir la que más nos convenga), pero estamos obligados a hacer 15 si podemos.
Y creo que no me dejo nada. Al final de (en nuestro caso) las 4 manos sumamos los puntos de cada jugador en cada mano y quien tenga más puntos gana la partida.
Para hacerlo un poco más friki-matemático podemos jugar con los 4 primeros números primos: Z2, Z3, Z5 y Z7.
Espero haberme explicado bien y que os haya gustado el juego. Y ya sabéis, para cualquier duda, comentario, crítica o lo que queráis usad los comentarios a esta entrada.
En nuestra época de colegio nos dicen que todo número elevado a cero vale uno, y también nos dicen que cero elevado a cualquier número vale cero, es decir:
a0 = 1
0b = 0
Pero siguiendo estas dos afirmaciones nos encontramos con un problema:
¿Cuánto vale 00?
Según la primera de las afirmaciones valdría 1, pero según la segunda valdría 0. ¿Con cuál nos quedamos?.
Muchos diríais: 00 es indeterminación. Sí pero no. No, porque el caso que nos ocupa no es el de una función (sucesión) que tiende a 0 elevada a otra función (sucesión) que tiende también a 0. Es decir, no queremos calcular el límite de cualquier función que dé una indeterminación 00, sino que queremos saber cuál es el valor del número 00 (recalco esto porque es muy importante y suele llevar a errores: no es lo mismo un número que una función cuyo límite es ese número).
¿Cuál es la forma más coherente matemáticamente hablando para dar un valor a 00?. Pues a través de un límite. Sí, cierto, en el párrafo anterior he dicho que no estamos calculando cualquier límite que dé como indeterminación 00, pero no es eso lo que vamos a hacer. Vamos a utilizar una función concreta para encontrar ese valor. ¿Cuál?. Pues la más lógica: xx. Vamos a calcular su límite cuando x tiende a 0. Lo haremos por el procedimiento normal: llamar A al límite y aplicar logaritmo a ambos lados de la igualdad. Utilizando después la regla de L’Hopital llegamos a la solución:
limx->0xx = ” 00 ” = A;
log A = limx->0log (xx) = [Propiedad de los logaritmos] = limx->0x·log x = ” 0·(-infinito) “;
Tenemos otra indeterminación. Para resolverla pasamos x como 1/x al denominador y aplicamos la regla de L’Hopital:
log A = limx->0log x/(1/x) = [L’Hopital] = limx->0(1/x)/(-1/x2) = [Operamos] = limx->0(-x) = 0;
Por tanto log A = 0 –> A = 1
Es decir, el valor más coherente matemáticamente hablando (y por tanto el que se utiliza en los casos en los que es necesario) es:
00 = 1
Algo del estilo ocurre con 0!. Sabemos que n! = n·(n - 1)·(n - 2)·…·2·1. Pero, ¿qué pasa con 0!?. Pues muy sencillo: 0! = 1. Al igual que en el caso anterior se utiliza este valor por convenio, pero la elección no es arbitraria. Podemos ver que es la elección más coherente con este razonamiento:
4! = 3!·4 –> 3! = 4!/4 = 6;
3! = 2!·3 –> 2! = 3!/3 = 2;
2! = 1!·2 –> 1! = 2!/2 = 1;
1! = 0!·1 –> 0! = 1!/1 = 1
Por tanto:
0! = 1
Actualización: Leyendo los comentarios me doy cuenta de que igual no he explicado de la mejor manera posible lo que quería decir. Os acosejo que leáis los comentarios que he hecho explicado un poco más estos dos temas.
Después de mi parón por los examenes de Septiembre, aquí vuelvo para dar la puntilla definitiva a mi serie de posts sobre la teoría de números elemental. Así que aquí viene quizá lo más importante (en mi opinión) de la teoría de números elemental, las congruencias.
¿Qué es una congruencia?
Es una relación de equivalencia (no me quiero meter a explicar que es una relación de equivalencia, por eso os pongo el enlace) que cumple la siguiente propiedad:
Sean a, b ∈ Z, m ∈ N, entonces “a” y “b” son congruentes si:
a mod (m) = b mod (m) ó b - a = K·m (siendo K ∈ Z)
Cuando dos números son congruentes se denota de la siguiente manera:
a ≡ b (mod (m))
Definimos “mod” como la operación módulo, que es el resto de la división euclídea de dos números:
r = a mod (m) a = m·q + r
(Más información en Wikipedia)
Conjuntos cocientes
Como las congruencias son relaciones de equivalencia, se pueden definir para cada elemento del conjunto en el que se da la relación, las clases de equivalencia.
La clase de equivalencia de cualquier elemento “a” perteneciente al conjunto “A”, se define como el conjunto:
[a] = {b ∈ A : aRb} (donde R es la relación de equivalencia)
Aplicando esto a los números enteros y a las congruencias, tenemos que:
a ≡ b (mod (m)) en Z tiene como clases de equivalencia a:
[o] = {…., -2·m, -m, 0, m, 2·m, ….}
[1] = {…., 1-2·m, 1-m, 1, 1+m, 1+2m, ….}
….
[m-1] = {…., -1-m, -1, m-1, 2·m-1, 3·m-1, ….}
(Más información en Wikipedia)
Sabiendo ya que son las clases de equivalencia, podemos pasar a explicar qué son los conjuntos cocientes. El conjunto cociente de A por R, se denota A/R, es el conjunto cuyos elementos son las clases de equivalencia por R de los elementos de A, es decir:
A/R = {[a] : a ∈ A}
Aplicando esto a los números enteros y a las congruencias, tenemos que:
Siendo a ≡ b (mod (m)) y sus clases de equivalencia [0], [1], …, [m-1], su conjunto cociente es:
Zm = {[0], [1], …, [m-1]} [Para los números enteros y las congruencias se denota Zm en lugar de Z/(mod (m))]
(Más información en Wikipedia)
—
Aunque no quería meterme demasiado en el tema de las relaciones de equivalencia, he tenido que explicar que son las clases de equivalencia y conjuntos cocientes sin haber explicado antes nada de relaciones de equivalencia ni de relaciones binarias, lo he hecho lo más sencillo posible y orientado a las congruencias en lugar de a cualquier relación, así que espero que lo entendáis bien, de todos modos ahí tenéis los comentarios para exponer vuestras dudas.
