El afamado explorador Iván Skvarca descubrió una vez el planeta de los Retóricos y los Sofistas (véase aquí la entrada del 5.11.2005). Estos personajes hacen preguntas. Un retórico sólo hace preguntas cuya respuesta conoce, un sofista sólo hace preguntas cuya respuesta desconoce. Tanto los retóricos como los sofistas pueden ser veraces (cuando hacen afirmaciones, siempre son verdaderas) o mentirosos (cuando hacen afirmaciones, siempre son falsas).
En su viaje por allí Spock registró la siguiente situación:
A y B son dos nativos que no se conocen mutuamente.
A dice: ¿Eres sofista?
B responde: No, ¿y tú?
A responde: Tampoco.
¿A qué grupo pertenece cada uno?
31.12.05
Gödel y Turing (Parte 2)
(A la parte 1 - A la parte 3)
El Entscheidungsproblem
En la conferencia inaugural del Congreso Internacional de Matemáticas celebrado en París en el año 1900 el ilustre David Hilbert planteó veintitrés problemas matemáticos abiertos que, él esperaba, podrían ser resueltos a lo largo del siglo XX. De todos ellos, el décimo problema planteaba la siguiente pregunta: ¿es posible diseñar un algoritmo que, dada una ecuación diofántica cualquiera, indique si admite o no alguna solución? (1)
Podemos transformar este pregunta en un problema más general, conocido como el Entscheidungsproblem, y cuyo enunciado es el siguiente: dada una teoría matemática no trivial ¿es posible diseñar un algoritmo que, dada una proposición cualquiera de esa teoría, nos indique si la misma es verdadera o falsa? Enunciado en términos más dramáticos, el Entscheidungsproblem nos pregunta ¿es posible, aunque sea en teoría, diseñar una computadora que reemplace a un matemático?
Tanto en el planteo del décimo problema de la conferencia de París, como en el Entscheidungsproblem, la palabra clave es algoritmo. ¿Qué es un algoritmo? Intuitivamente, un algoritmo es una receta, una serie de instrucciones que nos dice cómo trabajar mecánicamente con cierto conjunto de datos. La palabra “mecánicamente” alude al hecho de que la receta debe indicarnos sin ambigüedades qué debemos hacer en cada circunstancia.
Un algoritmo recibe entonces una entrada ó conjunto de datos iniciales (input, en inglés), procesa esos datos y, tras un tiempo finito, entrega como respuesta una salida ó resultado (output, en inglés). Como decíamos antes, la característica distintiva de un algoritmo es que el procesamiento de los datos se realiza en forma mecánica. Sin embargo, para tratar con el décimo problema o con el Entscheidungsproblem esta noción intuitiva no es suficiente. Necesitamos una definición matemáticamente precisa del concepto de algoritmo, pero eso quedará para la próxima entrada.
Nota:
(1) Una ecuación diofántica es una ecuación polinómica de una o varias variables con coeficientes enteros (es decir una ecuación en la que sólo aparecen números enteros y en la que las únicas operaciones permitidas son la suma, el producto y la potencia con exponente entero positivo) y de la cual se buscan exclusivamente soluciones enteras.
(A la parte 1 - A la parte 3)
El Entscheidungsproblem
En la conferencia inaugural del Congreso Internacional de Matemáticas celebrado en París en el año 1900 el ilustre David Hilbert planteó veintitrés problemas matemáticos abiertos que, él esperaba, podrían ser resueltos a lo largo del siglo XX. De todos ellos, el décimo problema planteaba la siguiente pregunta: ¿es posible diseñar un algoritmo que, dada una ecuación diofántica cualquiera, indique si admite o no alguna solución? (1)
Podemos transformar este pregunta en un problema más general, conocido como el Entscheidungsproblem, y cuyo enunciado es el siguiente: dada una teoría matemática no trivial ¿es posible diseñar un algoritmo que, dada una proposición cualquiera de esa teoría, nos indique si la misma es verdadera o falsa? Enunciado en términos más dramáticos, el Entscheidungsproblem nos pregunta ¿es posible, aunque sea en teoría, diseñar una computadora que reemplace a un matemático?
Tanto en el planteo del décimo problema de la conferencia de París, como en el Entscheidungsproblem, la palabra clave es algoritmo. ¿Qué es un algoritmo? Intuitivamente, un algoritmo es una receta, una serie de instrucciones que nos dice cómo trabajar mecánicamente con cierto conjunto de datos. La palabra “mecánicamente” alude al hecho de que la receta debe indicarnos sin ambigüedades qué debemos hacer en cada circunstancia.
Un algoritmo recibe entonces una entrada ó conjunto de datos iniciales (input, en inglés), procesa esos datos y, tras un tiempo finito, entrega como respuesta una salida ó resultado (output, en inglés). Como decíamos antes, la característica distintiva de un algoritmo es que el procesamiento de los datos se realiza en forma mecánica. Sin embargo, para tratar con el décimo problema o con el Entscheidungsproblem esta noción intuitiva no es suficiente. Necesitamos una definición matemáticamente precisa del concepto de algoritmo, pero eso quedará para la próxima entrada.
Nota:
(1) Una ecuación diofántica es una ecuación polinómica de una o varias variables con coeficientes enteros (es decir una ecuación en la que sólo aparecen números enteros y en la que las únicas operaciones permitidas son la suma, el producto y la potencia con exponente entero positivo) y de la cual se buscan exclusivamente soluciones enteras.
(A la parte 1 - A la parte 3)
30.12.05
Gödel y Turing (Parte 1)
(A la parte 2)
“El lógico matemático Kurt Gödel fue uno de los gigantes intelectuales del siglo XX y, en el supuesto de que la especie se conserve, una de las pocas figuras contemporáneas que serán recordadas dentro de 1.000 años. [...] A pesar de que en todas las disciplinas es corriente alentar una cierta miopía profesional, lo cierto es que esta opinión no es fruto de un caso de autocomplacencia por parte de los matemáticos. Simplemente es la verdad.” (John Allen Paulos, 1991).
En el año 1931 Kurt Gödel, por entonces un joven matemático checo casi desconocido (1), publicó un artículo titulado Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados I (2). En él, Gödel presentó dos teoremas que marcaron un antes y un después en la historia de la Lógica Matemática.
Hablando informalmente, el primero de esos teoremas dice que todo sistema axiomático (sujeto a ciertas restricciones formales que, hasta donde se sabe, garantizan la consistencia de la lógica subyacente) que sea suficientemente amplio como para expresar la aritmética elemental contendrá necesariamente proposiciones indecidibles, es decir, afirmaciones con significado que el sistema es incapaz de decidir si son verdaderas o falsas.
El segundo teorema (3) dice esencialmente que un sistema axiomático (sujeto a las mismas restricciones formales antes enunciadas) es incapaz de demostrar su propia consistencia (4).
Mi intención es exponer, en una serie de entradas, un esbozo de demostración de los dos teoremas mencionados. No será la demostración dada por el mismo Gödel en su famoso artículo, sino que estará basada en ideas concebidas posteriormente a la demostración de Gödel.
Para comenzar a comprender estas ideas debemos hablar de otro de los hombres más brillantes del siglo XX: el inglés Alan Mathison Turing, pero eso quedará para la próxima entrada.
Notas:
(1) Gödel había nacido en Brno (hoy República Checa) en 1906, es decir tenía por entonces menos de 25 años de edad.
(2) El artículo original llevaba por título: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, y fue publicado en el Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173 – 198.
(3) Éste segundo teorema iba a ser expuesto en una segunda parte del artículo, pero posteriormente Gödel no consideró necesario publicarla.
(4) Un sistema axiomático es consistente si está libre de contradicciones, es decir, si no hay en él ninguna proposición P tal que tanto P como su negación sean demostrables a partir de los axiomas.
(A la parte 2)
“El lógico matemático Kurt Gödel fue uno de los gigantes intelectuales del siglo XX y, en el supuesto de que la especie se conserve, una de las pocas figuras contemporáneas que serán recordadas dentro de 1.000 años. [...] A pesar de que en todas las disciplinas es corriente alentar una cierta miopía profesional, lo cierto es que esta opinión no es fruto de un caso de autocomplacencia por parte de los matemáticos. Simplemente es la verdad.” (John Allen Paulos, 1991).
En el año 1931 Kurt Gödel, por entonces un joven matemático checo casi desconocido (1), publicó un artículo titulado Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados I (2). En él, Gödel presentó dos teoremas que marcaron un antes y un después en la historia de la Lógica Matemática.
Hablando informalmente, el primero de esos teoremas dice que todo sistema axiomático (sujeto a ciertas restricciones formales que, hasta donde se sabe, garantizan la consistencia de la lógica subyacente) que sea suficientemente amplio como para expresar la aritmética elemental contendrá necesariamente proposiciones indecidibles, es decir, afirmaciones con significado que el sistema es incapaz de decidir si son verdaderas o falsas.
El segundo teorema (3) dice esencialmente que un sistema axiomático (sujeto a las mismas restricciones formales antes enunciadas) es incapaz de demostrar su propia consistencia (4).
Mi intención es exponer, en una serie de entradas, un esbozo de demostración de los dos teoremas mencionados. No será la demostración dada por el mismo Gödel en su famoso artículo, sino que estará basada en ideas concebidas posteriormente a la demostración de Gödel.
Para comenzar a comprender estas ideas debemos hablar de otro de los hombres más brillantes del siglo XX: el inglés Alan Mathison Turing, pero eso quedará para la próxima entrada.
Notas:
(1) Gödel había nacido en Brno (hoy República Checa) en 1906, es decir tenía por entonces menos de 25 años de edad.
(2) El artículo original llevaba por título: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, y fue publicado en el Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173 – 198.
(3) Éste segundo teorema iba a ser expuesto en una segunda parte del artículo, pero posteriormente Gödel no consideró necesario publicarla.
(4) Un sistema axiomático es consistente si está libre de contradicciones, es decir, si no hay en él ninguna proposición P tal que tanto P como su negación sean demostrables a partir de los axiomas.
(A la parte 2)
28.12.05
Spock y los tripartitos (III)
Recordemos que en el planeta de los tripartitos hay tres grupos de nativos, por un lado están los veraces, que sólo hacen afirmaciones verdaderas; por otro lado están los mentirosos, que sólo hacen afirmaciones falsas. El tercer grupo está formado por los paradójicos, que sólo hacen afirmaciones que ni un veraz ni un mentiroso podría hacer.
Una aclaración sobre el mundo de los tripartitos: la frase "soy paradójico" debe tomarse como abreviatura de "pertenezco a alguno de los subgrupos de los paradójicos" o también "no soy veraz ni mentiroso".
Los veraces y mentirosos forman en conjunto la clase de los normales (que se contrapone a la de los paradójicos). Si alguien dice "soy normal" entonces necesariamente es veraz (recordemos que un paradójico no puede hacer una afirmación que sean posibles para los veraces o los mentirosos). Estos son los grupos del planeta de los tripartitos:
Normales:
* Veraces: hacen afirmaciones verdaderas no paradójicas (es decir, válidas en planetas en los que no existen paradójicos).
* Mentirosos: hacen afirmaciones falsas no paradójicas (misma aclaración).
Paradójicos: Agrupan a todos los nativos que no son normales y se dividen en:
* Paradójicos veraces: hacer afirmaciones verdaderas que los veraces no pueden hacer, como por ejemplo "soy mentiroso o paradójico".
* Paradójicos mentirosos: hacer afirmaciones falsas que los mentirosos no pueden hacer, como por ejemplo "soy mentiroso".
* Paradójicos paradójicos: hacen afirmaciones que ninguno de los grupos anteriores puede hacer.
Paradójicos paradójicos: Son un subgrupo de los paradójicos y se dividen en:
* Paradójicos paradójicos veraces: hacer afirmaciones verdaderas que ni los veraces ni los paradójicos veraces pueden hacer, como por ejemplo "soy mentiroso o paradójico mentiroso o paradójico paradójico".
* Paradójicos paradójicos mentirosos: hacer afirmaciones falsas que ni los mentirosos ni los paradójicos mentirosos pueden hacer, como por ejemplo "soy mentiroso o paradójico mentiroso". * Paradójicos paradójicos paradójicos: hacen afirmaciones que ninguno de los grupos anteriores puede hacer.
Paradójicos paradójicos paradójicos: Son un subgrupo de los paradójicos paradójicos y se dividen en:
* Paradójicos paradójicos paradójicos veraces:...
Etc.
Otros grupos del planeta de los tripartitos:
* Caballeros: Agrupa a los veraces, paradójicos veraces, paradójicos paradójicos veraces, paradójicos paradójicos paradójicos veraces, etc.
* Bribones: Agrupa a los mentirosos, paradójicos mentirosos, paradójicos paradójicos mentirosos, etc.
Transparadójicos: Hacen afirmaciones que ni los normales, ni los paradójicos, ni los paradójicos paradójicos, ni los paradójicos paradójicos paradójicos, etc. pueden hacer. Se dividen en:
* Transparadójicos veraces.
* Transparadójicos mentirosos.
* Transparadójicos paradójicos.
* Transcaballeros: agrupa a los caballeros, a los transparadójicos veraces, a los transparadójicos paradójicos veraces, etc.
* Transbribones: agrupa a los bribones, a los transparadójicos mentirosos, alos transparadójicos paradójicos mentirosos, etc.
Una aclaración sobre el mundo de los tripartitos: la frase "soy paradójico" debe tomarse como abreviatura de "pertenezco a alguno de los subgrupos de los paradójicos" o también "no soy veraz ni mentiroso".
Los veraces y mentirosos forman en conjunto la clase de los normales (que se contrapone a la de los paradójicos). Si alguien dice "soy normal" entonces necesariamente es veraz (recordemos que un paradójico no puede hacer una afirmación que sean posibles para los veraces o los mentirosos). Estos son los grupos del planeta de los tripartitos:
Normales:
* Veraces: hacen afirmaciones verdaderas no paradójicas (es decir, válidas en planetas en los que no existen paradójicos).
* Mentirosos: hacen afirmaciones falsas no paradójicas (misma aclaración).
Paradójicos: Agrupan a todos los nativos que no son normales y se dividen en:
* Paradójicos veraces: hacer afirmaciones verdaderas que los veraces no pueden hacer, como por ejemplo "soy mentiroso o paradójico".
* Paradójicos mentirosos: hacer afirmaciones falsas que los mentirosos no pueden hacer, como por ejemplo "soy mentiroso".
* Paradójicos paradójicos: hacen afirmaciones que ninguno de los grupos anteriores puede hacer.
Paradójicos paradójicos: Son un subgrupo de los paradójicos y se dividen en:
* Paradójicos paradójicos veraces: hacer afirmaciones verdaderas que ni los veraces ni los paradójicos veraces pueden hacer, como por ejemplo "soy mentiroso o paradójico mentiroso o paradójico paradójico".
* Paradójicos paradójicos mentirosos: hacer afirmaciones falsas que ni los mentirosos ni los paradójicos mentirosos pueden hacer, como por ejemplo "soy mentiroso o paradójico mentiroso". * Paradójicos paradójicos paradójicos: hacen afirmaciones que ninguno de los grupos anteriores puede hacer.
Paradójicos paradójicos paradójicos: Son un subgrupo de los paradójicos paradójicos y se dividen en:
* Paradójicos paradójicos paradójicos veraces:...
Etc.
Otros grupos del planeta de los tripartitos:
* Caballeros: Agrupa a los veraces, paradójicos veraces, paradójicos paradójicos veraces, paradójicos paradójicos paradójicos veraces, etc.
* Bribones: Agrupa a los mentirosos, paradójicos mentirosos, paradójicos paradójicos mentirosos, etc.
Transparadójicos: Hacen afirmaciones que ni los normales, ni los paradójicos, ni los paradójicos paradójicos, ni los paradójicos paradójicos paradójicos, etc. pueden hacer. Se dividen en:
* Transparadójicos veraces.
* Transparadójicos mentirosos.
* Transparadójicos paradójicos.
* Transcaballeros: agrupa a los caballeros, a los transparadójicos veraces, a los transparadójicos paradójicos veraces, etc.
* Transbribones: agrupa a los bribones, a los transparadójicos mentirosos, alos transparadójicos paradójicos mentirosos, etc.
26.12.05
Spock y los tripartitos (II)
Recordemos que en el planeta de los tripartitos hay tres grupos de nativos, por un lado están los veraces, que sólo hacen afirmaciones verdaderas; por otro lado están los mentirosos, que sólo hacen afirmaciones falsas. El tercer grupo está formado por los paradójicos, que sólo hacen afirmaciones que ni un veraz ni un mentiroso podría hacer.
Por ejemplo, si un nativo dice "soy mentiroso" entonces es un paradójico, y pertenece en especial al subgrupo de los paradójicos mentirosos. Si un nativo dice "soy paradójico" entonces pertenece al grupo de los mentirosos. No puede ser un paradójico pues está haciendo una afirmación que un mentiroso puede hacer.
Los distintos grupos del planeta de los tripartitos no existen desde el comienzo de la historia de ese mundo, sino que han ido apareciendo merced a un largo proceso evolutivo. En los albores de la historia del planeta existía un único grupo, el de los veraces. Pero cierto día un nativo dijo "no soy veraz" y dio así comienzo al grupo de los mentirosos.
Durante algún tiempo sólo hubo veraces y mentirosos, hasta que cierto día un nativo dijo "soy mentiroso", y dio así comienzo al grupo de los paradójicos mentirosos. Y aún más tarde alguien dijo "soy mentiroso o paradójico" y dio comienzo al grupo de los paradójicos veraces.
a) En el texto anterior hay un error, ¿cuál es y cómo se puede corregir, conservando el estilo?
b) ¿Qué afirmación pudo dar origen a un nuevo grupo?
Por ejemplo, si un nativo dice "soy mentiroso" entonces es un paradójico, y pertenece en especial al subgrupo de los paradójicos mentirosos. Si un nativo dice "soy paradójico" entonces pertenece al grupo de los mentirosos. No puede ser un paradójico pues está haciendo una afirmación que un mentiroso puede hacer.
Los distintos grupos del planeta de los tripartitos no existen desde el comienzo de la historia de ese mundo, sino que han ido apareciendo merced a un largo proceso evolutivo. En los albores de la historia del planeta existía un único grupo, el de los veraces. Pero cierto día un nativo dijo "no soy veraz" y dio así comienzo al grupo de los mentirosos.
Durante algún tiempo sólo hubo veraces y mentirosos, hasta que cierto día un nativo dijo "soy mentiroso", y dio así comienzo al grupo de los paradójicos mentirosos. Y aún más tarde alguien dijo "soy mentiroso o paradójico" y dio comienzo al grupo de los paradójicos veraces.
a) En el texto anterior hay un error, ¿cuál es y cómo se puede corregir, conservando el estilo?
b) ¿Qué afirmación pudo dar origen a un nuevo grupo?
15.12.05
14.12.05
Calesita
Éste es un problema inspirado en una situación absolutamente real.
La calesita (carrusel o tiovivo) del Parque Rivadavia, en el barrio de Caballito, Buenos Aires, ha aumentado recientemente sus precios. Hasta antes del aumento cada vuelta en la calesita costaba 50 centavos y por cada 4 boletos (1 boleto = 1 vuelta) que uno comprara todos juntos le regalaban un quinto.
Después del aumento, la vuelta pasó a costar 75 centavos y además ahora te regalan un boleto extra por cada 7 comprados todos juntos.
La pregunta es: ¿en qué porcentaje aumentó el costo de una vuelta en la calesita del Parque Rivadavia?
La calesita (carrusel o tiovivo) del Parque Rivadavia, en el barrio de Caballito, Buenos Aires, ha aumentado recientemente sus precios. Hasta antes del aumento cada vuelta en la calesita costaba 50 centavos y por cada 4 boletos (1 boleto = 1 vuelta) que uno comprara todos juntos le regalaban un quinto.
Después del aumento, la vuelta pasó a costar 75 centavos y además ahora te regalan un boleto extra por cada 7 comprados todos juntos.
La pregunta es: ¿en qué porcentaje aumentó el costo de una vuelta en la calesita del Parque Rivadavia?
13.12.05
Spock y los tripartitos (I)
Cierta vez Spock, el viajero espacial estudioso de la lógica, llegó al planeta de los tripartitos. En este planeta hay tres grupos de nativos, por un lado están los veraces, que sólo hacen afirmaciones verdaderas; por otro lado están los mentirosos, que sólo hacen afirmaciones falsas. El tercer grupo está formado por los paradójicos, que sólo hacen afirmaciones que ni un veraz ni un mentiroso podría hacer.
Por ejemplo, si un nativo dice "soy mentiroso" entonces es un paradójico, y pertenece en especial al subgrupo de los paradójicos mentirosos. Si un nativo dice "soy paradójico" entonces pertenece al grupo de los mentirosos. No puede ser un paradójico pues está haciendo una afirmación que un mentiroso puede hacer.
En su primer día en este planeta Spock se encontró con un nativo que le dijo: "Soy mentiroso o paradójico".
¿A qué grupo pertenecía el nativo?
Por ejemplo, si un nativo dice "soy mentiroso" entonces es un paradójico, y pertenece en especial al subgrupo de los paradójicos mentirosos. Si un nativo dice "soy paradójico" entonces pertenece al grupo de los mentirosos. No puede ser un paradójico pues está haciendo una afirmación que un mentiroso puede hacer.
En su primer día en este planeta Spock se encontró con un nativo que le dijo: "Soy mentiroso o paradójico".
¿A qué grupo pertenecía el nativo?
10.12.05
Laberinto (II)
Acabo de ver que el buen amigo Juan de Mairena ha estado escribiendo en estos días sobre laberintos. Juro que la entrada anterior fue escrita antes saberlo. Un caso curioso de telepatía, que seguramente interesaría a nuestros amigos de El Ojo Crédulo.
9.12.05
Laberinto
Un laberinto es un camino rectílineo trazado en un espacio topológicamente hostil. (Graffiti leído por ahí.)
8.12.05
Números salvajes
The Wild Numbers (o Los números salvajes) es una simpática novela escrita por Philibert Schogt que narra el intento que hace Isaac Swift, un matemático de ficción, por resolver el problema de los números salvajes, un problema asimismo de ficción creado ad hoc por el autor de la novela.
El planteo del problema, según Schogt, sería el siguiente. Tenemos definidas ciertas operaciones aritméticas “decepcionantemente simples”. Si aplicamos estas operaciones a un número entero obtenemos una fracción. Apliquemos estas operaciones a esa fracción y obtendremos otra. Finalmente, al cabo de cierto número de pasos, obtendremos nuevamente un número entero. En palabras del autor: “dentro de todo número se esconde un número salvaje, que emergerá si se lo provoca suficientemente”.
Si comenzamos con 0, dice Schogt, el número salvaje que emerge es 11; comenzando con el 1 emerge el 67; comenzando con 2 obtenemos 2; el 3 nos da el número salvaje 4769 y el 4 nos da nuevamente 67. Los números 2, 11, 67 y 4769 son salvajes y, según Schogt, es difícil hallar un quinto ejemplo. El problema abierto que Isaac Swift intenta resolver en la novela es: ¿existen infinitos números salvajes?
Una pregunta interesante que muchos lectores de la novela seguramente se plantearán es: cuando Schogt escribió que el 0 da el 11, que el 1 da el 67 y así sucesivamente ¿tenía en mente algunas operaciones “decepcionantemente simples” en concreto o se limitó a escribir números al azar? En este último caso ¿es posible definir operaciones “decepcionantemente simples” que se ajusten a las especificaciones de Schogt? Después fallar en varias tentativas de hallar estas operaciones he llegado a la convicción personal de que Schogt simplemente eligió números al azar y que, si acaso existen operaciones que se ajusten a la descripción de la novela, difícilmente serán “decepcionantemente simples”.
En uno de estos fallidos intentos por encontrar las operaciones de Schogt tropecé con un problemita que paso a comentarles a continuación. Comencemos por definir una función F del siguiente modo: si n es un entero entonces F(n) es el producto de todos los números primos impares que son divisores de n, si n no es divisible por ningún primo impar (esto ocurre si n es 1 o si es potencia de 2) entonces F(n) = 1. Tenemos entonces, por ejemplo, que F(1) = 1, F(2) = 1, F(3) = 3, F(4) = 1, F(5) = 5, F(6) = 3, F(7) = 7, etc.
Si a/b es una fracción (en la que suponemos que a y b no tienen divisores en común mayores que 1, recordemos además que si n es un entero entonces n = n/1), definimos w(a/b) = (F(a) + F(b))/máx(a, b). Como en la novela de Schogt comenzamos con un número entero y aplicamos la función w una y otra vez.
Conjetura 1: Si comenzamos con un entero positivo n y aplicamos la función w una y otra vez tarde o temprano caeremos en un ciclo (es decir, una secuencia de números enteros o fraccionarios que se repetirán cíclicamente una y otra vez, eventualmente puede ser un único número que permanece fijo).
Por ejemplo, si comenzamos con 1 obtenemos 2, luego 1, luego 2 y así sucesivamente. A partir de 1 obtenemos entonces el ciclo salvaje (1, 2). Comenzando con 2, 3, 4, 5, 6, 7 u 8 obtenemos el mismo ciclo. Para 9 obtenemos el ciclo salvaje unitario (4/9), es decir w(4/9) = 4/9. Comenzando con 25 obtenemos el ciclo (6/25, 8/25). Comenzando con 95 obtenemos (10/49, 12/49); con 99, obtenemos (56/99, 40/99, 38/99, 52/99, 46/99).
Conjetura 2: El único ciclo salvaje formado por números enteros es (1, 2).
Conjetura 3: En todo ciclo salvaje, las fracciones que lo forman
tienen el mismo denominador. (Recordemos que escribimos las fracciones de tal modo que numerador y denominador no tengan divisores en común mayores que 1. )
¿Podrá alguien demostrar o refutar estas conjeturas? ¿Podrá alguien encontrar las operaciones de Philibert Schogt?
El planteo del problema, según Schogt, sería el siguiente. Tenemos definidas ciertas operaciones aritméticas “decepcionantemente simples”. Si aplicamos estas operaciones a un número entero obtenemos una fracción. Apliquemos estas operaciones a esa fracción y obtendremos otra. Finalmente, al cabo de cierto número de pasos, obtendremos nuevamente un número entero. En palabras del autor: “dentro de todo número se esconde un número salvaje, que emergerá si se lo provoca suficientemente”.
Si comenzamos con 0, dice Schogt, el número salvaje que emerge es 11; comenzando con el 1 emerge el 67; comenzando con 2 obtenemos 2; el 3 nos da el número salvaje 4769 y el 4 nos da nuevamente 67. Los números 2, 11, 67 y 4769 son salvajes y, según Schogt, es difícil hallar un quinto ejemplo. El problema abierto que Isaac Swift intenta resolver en la novela es: ¿existen infinitos números salvajes?
Una pregunta interesante que muchos lectores de la novela seguramente se plantearán es: cuando Schogt escribió que el 0 da el 11, que el 1 da el 67 y así sucesivamente ¿tenía en mente algunas operaciones “decepcionantemente simples” en concreto o se limitó a escribir números al azar? En este último caso ¿es posible definir operaciones “decepcionantemente simples” que se ajusten a las especificaciones de Schogt? Después fallar en varias tentativas de hallar estas operaciones he llegado a la convicción personal de que Schogt simplemente eligió números al azar y que, si acaso existen operaciones que se ajusten a la descripción de la novela, difícilmente serán “decepcionantemente simples”.
En uno de estos fallidos intentos por encontrar las operaciones de Schogt tropecé con un problemita que paso a comentarles a continuación. Comencemos por definir una función F del siguiente modo: si n es un entero entonces F(n) es el producto de todos los números primos impares que son divisores de n, si n no es divisible por ningún primo impar (esto ocurre si n es 1 o si es potencia de 2) entonces F(n) = 1. Tenemos entonces, por ejemplo, que F(1) = 1, F(2) = 1, F(3) = 3, F(4) = 1, F(5) = 5, F(6) = 3, F(7) = 7, etc.
Si a/b es una fracción (en la que suponemos que a y b no tienen divisores en común mayores que 1, recordemos además que si n es un entero entonces n = n/1), definimos w(a/b) = (F(a) + F(b))/máx(a, b). Como en la novela de Schogt comenzamos con un número entero y aplicamos la función w una y otra vez.
Conjetura 1: Si comenzamos con un entero positivo n y aplicamos la función w una y otra vez tarde o temprano caeremos en un ciclo (es decir, una secuencia de números enteros o fraccionarios que se repetirán cíclicamente una y otra vez, eventualmente puede ser un único número que permanece fijo).
Por ejemplo, si comenzamos con 1 obtenemos 2, luego 1, luego 2 y así sucesivamente. A partir de 1 obtenemos entonces el ciclo salvaje (1, 2). Comenzando con 2, 3, 4, 5, 6, 7 u 8 obtenemos el mismo ciclo. Para 9 obtenemos el ciclo salvaje unitario (4/9), es decir w(4/9) = 4/9. Comenzando con 25 obtenemos el ciclo (6/25, 8/25). Comenzando con 95 obtenemos (10/49, 12/49); con 99, obtenemos (56/99, 40/99, 38/99, 52/99, 46/99).
Conjetura 2: El único ciclo salvaje formado por números enteros es (1, 2).
Conjetura 3: En todo ciclo salvaje, las fracciones que lo forman
tienen el mismo denominador. (Recordemos que escribimos las fracciones de tal modo que numerador y denominador no tengan divisores en común mayores que 1. )
¿Podrá alguien demostrar o refutar estas conjeturas? ¿Podrá alguien encontrar las operaciones de Philibert Schogt?
Spock y los Dos Bocas
En el planeta de los Dos Bocas todos los nativos hacen las afirmaciones de a pares. Existen tres tipos de nativos, por un lado están los veraces (en cada par de afirmaciones, ambas son verdaderas), luego están los mentirosos (en cada par de afirmaciones, ambas son falsas) y finalmente están los Dos Bocas mixtos (en cada par de afirmaciones, una es verdadera y la otra es falsa, la verdadera puede ser la primera o la segunda afirmación).
Cierta vez Spock, el viajero espacial estudioso de la lógica, se encontró con dos Dos Bocas nativos, llamados A y B, que se conocen perfectamente entre sí y que le dijeron:
A dijo: B es mixto o mentiroso / B es mixto.
B dijo: A es veraz / yo soy mixto.
(La barra separa las afirmaciones en cada par.)
¿A qué clase pertenece cada uno?
Cierta vez Spock, el viajero espacial estudioso de la lógica, se encontró con dos Dos Bocas nativos, llamados A y B, que se conocen perfectamente entre sí y que le dijeron:
A dijo: B es mixto o mentiroso / B es mixto.
B dijo: A es veraz / yo soy mixto.
(La barra separa las afirmaciones en cada par.)
¿A qué clase pertenece cada uno?
2.12.05
Sombreros rojos, sombreros verdes (II)
Tenemos nuevamente una habitación en la que hay 50 personajes, algunos de los cuales tienen sombreros rojos y los demás sombreros verdes. Algunos son "normales" (ven rojos los sombreros rojos y verdes los sombreros verdes), los otros son inversos" (ven los colores invertidos). Nadie ve su propio sombrero. En la habitación hay al menos un normal y al menos un inverso.
Cada uno dice con sinceridad qué cantidad de sombreros rojos ve y qué cantidad de sombreros verdes ve. Todos declaran lo mismo, aunque no se sabe qué.
a) ¿Cuántos normales hay?
b) ¿Cuántos personajes tienen sombreros rojos?
c) Demuestre que la solución es única.
Cada uno dice con sinceridad qué cantidad de sombreros rojos ve y qué cantidad de sombreros verdes ve. Todos declaran lo mismo, aunque no se sabe qué.
a) ¿Cuántos normales hay?
b) ¿Cuántos personajes tienen sombreros rojos?
c) Demuestre que la solución es única.
Suscribirse a:
Comentarios (Atom)