Hanoi no recursivo

Matemáticas 4 Comentarios »
Tags: ,

Si quieres saber cómo resolver el problema de las torres de Hanoi, puedes alardear de una cabeza prodigiosa o memoria con este método ¡no hace falta un ordenador! Podrías proponerte batir el record Guiness en número de piezas en el menor tiempo posible.

  1. Si el número de piezas es par, hay que seguir la secuencia 3-4-5 (3,4,5,3,4,5,3,4,5…)
  2. Y si el número de piezas en impar, hay que seguir la secuencia 4-3-5 (4,3,5,4,3,5,4,3,5…)

Así de simple.

Yo llamo a la primera base origen “1″, a la intermedia “2″ y a la final “3″ El movimiento “3″ significa (3=1+2) mover de 1 a 2 o de 2 a 1. El movimiento “4″ (4=1+3) significa mover de la 1 a la 3 o de la 3 a la 1. Y el movimiento “5″ (5=2+3) mover de 2 a 3 o de 3 a 2.
¿Qué movimiento elegir? Pues la pieza menor se pone encima de la mayor. No hay confusión.

¿Hasta cuando hay que parar? Está claro, cuando la pirámide mayor esté en la base 3. En 2^n - 1 movimientos.

Lee el resto de esta entrada »

Ordenando los números racionales

Matemáticas 2 Comentarios »

Ordenando las tonterías que tenía escritas desde hacía mucho, me he dado cuenta que hice un decubrimiento y en 2004 otro tipo lo publicó. Me refiero a una biyección de los positivos naturales con los positivos racionales.

En la “On-Line Encyclopedia of Integer Sequences” (un sitio genial: tú pones los términos de una sucesión y te dice como se llama) aparecen tanto la secuencia de los numeradores (A020650) como de los denominadores (A020651). Me parece que el descubridor “oficial” es Antti Karttunen, pero no estoy muy seguro del año, ya que es él mismo el que lo da de alta en la enciclopedia en 2004.

Su definición en la enciclopedia es de una sencillez absoluta:

Numerators in recursive bijection from positive integers to positive rationals (the bijection is f(1) = 1, f(2n) = f(n)+1, f(2n+1) = 1/(f(n)+1)).

Debe ser algo fácil de descubrir, por ejemplo, hay un tipo que dice en un foro que se le ocurrió así de repente: “Simple bijection N <-> Q

A mí también, pero mucho antes. ¿Pruebas? Presenté un trabajo en Inteligencia Artificial las funciones numerador y denominador (a saber dónde está) Un amigo arquitecto colgó en la pared de su estudio un árbol con los primeros 8 niveles (a saber dónde está) A algunos compañeros y amigos les expliqué mi descubrimiento (a saber qué recuerdan)

También es posible que fuera inventado en el siglo XVII dada mi ignorancia.

Lee más, haz clic aquí ahora:

Lee el resto de esta entrada »

Perdiendo la fe en… Cantor (III)

Matemáticas 3 Comentarios »
Tags: ,

Esto, más que una demostración es una duda que tengo. Aunque soy matemático soy bastante ignorante en estos temas y es una manera de lanzar a debate esta cuestión.

A ver si me explico.

Supongamos que existe una función biyectiva:

f:\mathbb N \longrightarrow \mathbb R

Es decir, que puedo ordenar los número reales de alguna manera (son numerables). Y definimos la función Di(s) como el dígito i-ésimo del número real s. Podemos entonces considerar un número real r, tal que

D_i(r) = (D_i(f(i))+1) \mod 10

Con esto conseguimos la famosa “diagonalización”

Según hemos definido f, y como es un número real, existe un número k natural tal que f(k) = r Pero no sabemos cuál es su k-ésimo decimal, es decir cuánto vale Dk(r) porque:

D_k(r) = (D_k(f(k))+1) \mod 10 = (D_k(r) + 1) \mod 10

Por tanto no es un número real, no está bien definido. Pero al no estar incluido en el conjunto de los reales, al estar “fuera” de \mathbb R puedo definir correctamente r, es decir puedo diagonalizar con toda paz… con lo que sería un número real y volveríamos al principio.

En el teorema de la diagonalización de Cantor se concluye que no existe tal función f, es decir, que \mathbb R no es numerable. Pero yo concluyo que sencillamente r está mal definido porque no puedo decir que pertenece a un conjunto y a la vez no, vamos, una paradoja.

Sigamos con nuestro razonamiento…

Para que se me entienda en mi razonamiento no hace falta tratar con conjuntos infinitos. Vamos a definir un conjunto C de números reales formado por todos los números reales que se puedan expresar en menos de mil palabras. Por ejemplo, “dos”, “tres”, “la media aritmética de los 10.000 primeros dígitos de Pi”, “raíz de dos”, etc. Podemos decir que es un conjunto finito ya que el lenguaje es limitado, está limitado por letras y aunque podríamos definir un lenguaje más específico o más matemático, nos limitamos al español, con tal de que entendamos qué numero es el que representamos en una expresión.

Pues bien, sea una función g biyectiva:

g:\mathbb N_c \longrightarrow C

Donde \mathbb N_c son los números naturales del 1 hasta el cardinal de C. Es decir que pueda ordenar los elementos de C, esto es posible ya que es un conjunto finito y puedo ordenarlo alfabéticamente, por ejemplo.

Sea s un número tal que:

D_i(s) = (D_i(g(i))+1) \mod 10 (Diagonalizamos C)

Siempre que i sea menor que card(C) (cardinal de C) y mayor o igual que uno. Con un cero como parte entera y ceros a partir del (card(C)+1)-ésimo dígito.

¿Podemos decir que s pertenece a C? Podemos, ya que su definición nos ha llevado menos de mil palabras. Pero como lo hemos definido, no puede pertenecer a C, ya que por definición de g, debe tener una posición n-ésima tal que g(n) = s

Con esta contradicción, ¿debemos concluir que no existe la función g? ¿y qué puede significar? ¿que C es infinito?

Creo que la diagonalización hace contradecir la definición de un número real, y por tanto no es un método bueno. Pero claro, esto es un punto de vista muy tontorrón, es posible que me haya equivocado en cosas muy básicas. ¿Quién me ayuda en esta paradoja?

Perdiendo la fe en… Cantor (II)

Matemáticas No hay Comentarios »
Tags:

Después de volver a leer y recordar las magistrales clases del profesor J.R. Jimenez  sobre teoría de conjuntos cantoriana aplicada a la lógica. Bueno, ya ni me acuerdo.

He encontrado pequeños artículos que pueden venir bien para saber de qué hablo:

Gödel en una cáscara de nuez: La diagonalización de Cantor

Paradoja de Russell

Que son artículos que no me convencen de lo contrario de mi postura. ¿No será que me estoy convirtiendo en un Crank?

Yo no sabía qué era eso pero está muy ligado el “anti-Cantorismo” y los “Cranks” He aquí una definición muy buena de lo que es un “crank”

Jo tía, qué fuerte (¡segundo intento!)

Y he aquí un sitio divertido sobre cranks: www.crank.net Hay, como no, artículos sobre el último teorema de Fermat y sobre “Cantor was wrong”

Perdiendo la fe en… Cantor

Matemáticas No hay Comentarios »
Tags:

Pues venga, que es gerundio, que tenía que escribir algo en este Blog. Comentar que desde hace un tiempo llevo dudando sobre el tema del infinito y los alephs, los cardinales de N y R, etc.

No me acaba de convencer la demostración de la “diagonalización” y tengo unas teorías acerca del infinito. En mi opinión, el infinito debería ser intocable. Pero ahora no me voy a meter. Estoy leyendo un artículo que promete interesante:

“La Controversia entre L. Kronecker y G. Cantor acerca del Infinito”

Me seguiré informando a ver si hay alguien más de mi opinión (seguro)

Diseñado por j david macor.com. WP Theme & Icons originales por N.Design Studio. Traducido por Trazos Web.
Entradas RSS Comentarios RSS Iniciar sesión