29.11.05

Verdalia (III)

Recordemos que en el planeta Verdalia todos los nativos pertenecen a uno y sólo uno de los tres siguientes grupos: por un lado están los Veraces, que siempre hacen afirmaciones rigurosamente verdaderas; en segundo lugar están los Mentirosos, que siempre hacen afirmaciones falsas. El tercer grupo está formado por los Cambiantes (también llamados Normales), que alternan aleatoriamente afirmaciones verdaderas con afirmaciones falsas.

En su tercer día de visita a Verdalia, Spock visitó a Fred y Ged, dos nativos de quienes no tenía ninguna información adicional.

Después de los saludos, Fred dijo: “Yo soy cambiante”.
Ged dijo: “Yo soy mentiroso”.

Después de un rato Fred agregó: “Al menos uno de nosotros es cambiante”.
Pero Ged retrucó: “Al menos uno de nosotros es cambiante”.

¿A qué grupo pertenecía cada uno?

25.11.05

Verdalia (II)

Recordemos que en el planeta Verdalia todos los nativos pertenecen a uno y sólo uno de los tres siguientes grupos: por un lado están los Veraces, que siempre hacen afirmaciones rigurosamente verdaderas; en segundo lugar están los Mentirosos, que siempre hacen afirmaciones falsas. El tercer grupo está formado por los Cambiantes (también llamados Normales), que alternan aleatoriamente afirmaciones verdaderas con afirmaciones falsas.

En su segundo día en Verdalia, Spock fue a visitar a Alfio, Beto y Gamo, tres nativos de quienes Spock sabía a ciencia cierta que pertenecían cada uno a un grupo diferente, aunque no sabía exactamente a qué grupo pertenecía cada uno.

Al llegar Spock, Alfio lo saludó.
Beto le dijo: Yo soy cambiante.
Gamo le dijo: Yo soy mentiroso.

¿A qué grupo pertenecía cada uno?

23.11.05

Verdalia (I)

En el planeta Verdalia todos los nativos pertenecen a uno y sólo uno de los tres siguientes grupos: por un lado están los Veraces, que siempre hacen afirmaciones rigurosamente verdaderas; en segundo lugar están los Mentirosos, que siempre hacen afirmaciones falsas. El tercer grupo está formado por los Cambiantes (también llamados Normales), que alternan aleatoriamente afirmaciones rigurosamente verdaderas con afirmaciones rigurosamente falsas.

Cuando Spock, el viajero espacial estudioso de la lógica, llegó a Verdalia, el primer nativo con el que se encontró le dijo: “Yo no soy veraz”.

¿A qué grupo pertenecía este nativo de Verdalia?

19.11.05

Sistemas de frases (una teoría)

Éste es un intento de formalización de los sistemas de frases (aunque en realidad no todos los sistemas de los problemas anteriores son contemplados en ella).

Parte 1: Frases.

Por una frase atómica entenderemos una expresión que puede tomar cualquiera de las tres formas siguientes:

Tipo 1) Las frases cuyos números están en el conjunto A son V.
Tipo 2) Las frases cuyos números están en el conjunto A son F.
Tipo 3) Las frases cuyos números están en el conjunto A son equivalentes.

Donde V y F son símbolos primitivos y A es un conjunto finito no vacío de enteros positivos. Cuando la frase sea del Tipo 1 o Tipo 2 y A esté formado solamente por el número n habitualmente las frases adoptarán la forma:

1') La frase n es V.
2') La frase n es F.

Una frase se define como:

a) Las frases atómicas son frases.
b) Si P es una frase, la negación de P (que escribiremos "No es cierto que P") es también una frase.
c) Si P es una frase y Q es una frase entonces "P y Q", "P o Q" y "Si P entonces Q" son frases.
d) Toda frase se obtiene aplicando sucesivamente las reglas anteriores una cantidad finita de veces.

Parte 2: Sistemas.

Un sistema de frases es una sucesión finita de frases: P1, P2,....,Pm. Un sistema será válido si y sólo si en todos los casos los conjuntos mencionados en las frases están contenidos en el conjunto {1,...m}. En otras palabras, si las frases sólo se refieren a frases del sistema. En lo sucesivo siempre supondremos que los sistemas son válidos.

Parte 3: Valuaciones.

Una valuación para un sistema de frases es una función que a cada frase le asigna el símbolo V o el símbolo F. Dada una valuación, serán equivalentes las expresiones "A la frase Pn le corresponde el símbolo V", "Pn es V" y "La frase n es V" (análogamente con F).

Dada una valuación para un sistema diremos que una frase del Tipo 1 es verdadera si y sólo si a todas las frases cuyos índices están en A les corresponde V. Una frase del tipo 2 es verdadera si y sólo si a todas las frases cuyos subíndices están en A les corresponde F. Una frase del tipo 3 es verdadera si y sólo si a todas las frases cuyos subíndices están en A les corresponde el mismo símbolo. (Cuando no son verdaderas, son falsas).

Para las frases compuestas se procede del modo habitual: "P y Q" es verdadera si y sólo si tanto P como Q lo son, "P o Q" es verdadera si y sólo si al menos una de ambas es verdadera, etc.

Nota: "es verdadera" (resp. falsa) será equivalente a "hace una afirmación verdadera" (resp. falsa).

Definición: Un sistema es compatible si y sólo si admite una valuación tal que todas las frases que, por esa valuación, son V hacen afirmaciones verdaderas y todas las frases que, por esa valuación son F, hacen afirmaciones falsas. Si esta valuación, además, es única entonces el sistema se dirá compatible determinado.

Si no es compatible, se dirá incompatible.

Parte 4: Notas.

1) Las palabras "compatible", "determinado" e "incompatible" están inspiradas en los términos análogos usados al referirse a los sistemas de ecuaciones lineales.

2) Se aceptarán abreviaturas "naturales". Por ejemplo, si Pn es "La frase n es F" entonces podrá también decirse que Pn afirma "Esta frase es F". O por ejemplo, si P1 es "Las frases cuyos números están en el conjunto A son V" y A es el conjunto de todos los subíndices
de las frases del sistema entonces podremos rescribir P1 como "Todas las frases son V".

3) En esta formalización no se admiten "sistemas autorreferentes", la frase "El sistema es incompatible" no es admisible. Tampoco se admiten sistemas infinitos. La formalización puede ampliarse fácilmente para incluir otras frases atómicas, además de las de Tipo 1, 2 o 3. El único requisito es que esté claramente definido el criterio para determinar cuándo es verdadera y cuándo falsa. Una posible cuarta frase atómica es:

Tipo 4) "El sistema es compatible", que es verdadera si el sistema que la contiene es compatible y falsa en caso contrario.

Parte 5: Tres teoremas.

Teorema 1 (o Teorema del Mentiroso): El sistema formado por la única frase

1) "La frase 1 es F"

es incompatible.

Teorema 2: Si el sistema es compatible y la frase Pn dice "Esta frase es equivalente a Pm" (más formalmente Pn es "Las frases cuyos números están en el conjunto {n, m} son equivalentes") entonces a Pm le corresponde V.

Teorema 3 (o Teorema de la no paradoja): Un sistema cuyas frases estén construidas a partir de frases atómicas de los tipos 1, 2 o 3 es o bien compatible o bien incompatible.

En otras palabras, si el sistema no se refiere globalmente a sí mismo no hay riesgo de paradoja. Podemos llamar no paradójicos a estos sistemas, a los cuales se les puede atribuir consistentemente la condición de compatible o la de incompatible. Por el contrario, un ejemplo de sistema paradójico sería:

1) Las dos frases son equivalentes.
2) El sistema es incompatible.

que sólo puede ser compatible si la frase 2 es verdadera, pero en ese caso debe ser incompatible.

17.11.05

Sistema de frases (V)

¿Es compatible el siguiente sistema de frases?

1) Todas las frases son falsas.
2) Exactamente una frase es falsa.
3) Exactamente dos frases son falsas.
4) Exactamente tres frases son falsas.
5) Exactamente cuatro frases son falsas.

Y así sucesivamente ad infinitum.

(Para una definción de compatible, ver aquí.)

16.11.05

Sistema de frases (IV)

¿Es compatible el siguiente sistema de frases?

1) Exactamente una frase es falsa.
2) Exactamente dos frases son falsas.
3) Exactamente tres frases son falsas.
4) Exactamente cuatro frases son falsas.


Y así sucesivamente ad infinitum.

(Para una definción de compatible, ver aquí.)

15.11.05

Sistema de frases (III)

¿Es compatible el siguiente sistema de frases?

1) Exactamente una frase es falsa.
2) Exactamente dos frases son falsas.
3) Exactamente tres frases son falsas.
4) Todas las frases son falsas.


(Para un definición de compatible, ver aquí.)

14.11.05

Tríos (II)

La idea aquí es la opuesta a la del problema anterior. Buscamos ahora escribir una secuencia circular con los números de 1 a n (una vez cada uno, sin repetir) de modo tal que cualquier trío de números consecutivos esté en secuencia aritmética.

Si la secuencia no fuera circular, habría siempre una solución trivial: 1-2-3-...-n, pero la circularidad de la secuencia invalida esta solución (excepto para el caso n = 3).

Para n = 3 tenemos entonces la solución 1-2-3 (y también la solución 1-3-2). Ésta es una solución para el caso n = 9: 3-1-5 -9-7-8-6-4-2.

Como antes, el objetivo es investigar para qué valores de n existe solución, cuántas soluciones hay en cada caso y dar, si es posible, un método sistemático para hallarlas.

Tríos (I)

En este problema y en el siguiente, cuando hablemos de una secuencia de números imaginaremos que la misma es circular. Por ejemplo, al escribir 1-5-7 estaremos diciendo que al 1 le sigue el 5, al 5 le sigue el 7 que y al 7 le sigue el 1. Por supuesto, 1-5-7 será exactamente lo mismo que 5-7-1 o que 7-1-5, pero será diferente a 1-7-5. La secuencia 1-4-5-6 será la misma que 5-6-1-4.

Diremos que tres números están en secuencia aritmética cuando ocurra que uno de los tres es exactamente el promedio de los otros dos. Por ejemplo, 1-5-9 están en secuencia aritmética y también lo están 1-9-5 (en ambos casos, el 5 es el promedio de 1 y 9).

La idea básica del problema consiste en escribir una secuencia circular que contenga a los números de 1 a n (una vez cada uno, sin repetir), de modo tal que no haya nunca tres números consecutivos en secuencia aritmética.

Por ejemplo, para n = 5, la secuencia 4-1-5-3-2 falla porque 3-2-4 están en secuencia aritmética.

Es obvio que para n = 3 no existe solución. Tal vez no es tan obvio, pero tampoco existe solución para n = 4 o para n = 5.

El problema consiste ubicar los números del 1 al 6 en una secuencia circular de modo tal que no haya tres números consecutivos en secuencia aritmética. ¿Cuántas soluciones hay?

Addenda: Investigar para qué valores de n > 6 existe solución, cuántas soluciones hay en cada caso y dar, si es posible, un método sistemático para hallarlas.

13.11.05

Conjetura de Poniachik

Una potencia es el resultado de elevar un entero a algún exponente mayor que 1. Las primeras potencias son entonces 1, 4, 8, 9, 16, 25, 27.

La conjetura de Poniachik afirma que existe una constante C tal que si n es un entero mayor que C entonces entre el cuadrado de n y el cuadrado de n + 1 existe al menos una potencia.

12.11.05

Otra serie

1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 6, 7, 8, 11, 14, 17, 20, 23, 26, 29, 12, 13, 14, 15, 19, 23, 27, 31, 35, 39, 20, 21, 22, 23, 24, 29, 34, 39, 44, 49, 30, 31, 32, 33, 34, 35, 41, 47, 53, 59, 42, 43, ...

¿Cuál sigue?

11.11.05

Pitágoras pandigital

Use la mayor cantidad de cifras diferentes para formar una terna pitagórica. Por ejemplo 63, 84 y 105 usa 7 dígitos.

10.11.05

Sabueso en un cubo

Un sabueso recorre un cubo de 3x3x3. Inicia su recorrido en un cubito cualquiera y a partir de allí va pasando de un cubito a cualquier otro que tenga una cara en común con él. En el primer cubito marca un 1, en el siguiente un 2, luego un 3 y así sucesivamente hasta visitar, exactamente una vez cada uno, los 27 cubitos que forman el cubo grande.

El objetivo es lograr un recorrido tal que en cada capa horizontal quede la misma cantidad de números primos y que, a la vez, estos primos formen en cada capa un dibujo simétrico.

Vemos aquí un ejemplo fallido, en cada capa la cantidad de primos es la misma. Además en la capa central y en la superior el dibujo es simétrico, pero el dibujo no es simétrico en la capa inferior:

9.11.05

Fibonacci, Rayos y Centellas

Vamos a definir esta vez una familia de sucesiones numéricas, todas las cuales son variantes de la sucesión de Fibonacci. En cualquiera de estas sucesiones los primeros n números son elegidos arbitrariamente; a partir de allí se usa la siguiente regla: cada número es la suma del inmediato anterior más otro que se encuentre aún más atrás.

Por ejemplo, podemos definir la sucesión b(n) que comienza con 1, 2, 3, es decir, b(1) = 1, b(2) = 2, b(3) = 3 y que a partir de allí siga la regla:

b(n) = b(n-1) + b(n-2) si n = 2k
b(n) = b(n-1) + b(n-4) si n = 2k + 1

La sucesión comienza entonces con 1, 2, 3, 5, 6, 11, 14, 25, 31, 56, 70, ...

Diremos que esta sucesión b(n) es de tipo 1, 3, 1, 3, 1, 3,.... Esto significa que cada término es la suma del inmediato precedente más otro que se halla más atrás y que se obtiene así: la primera vez salteo un término hacia atrás, la segunda vez salteo tres términos hacia atrás, luego uno, luego tres, etc.

En su libro Circo Matemático, Martín Gardner habla de la sucesión de Fibonacci y, entre otros datos muy interesantes, menciona allí distintas situaciones (físicas, biológicas, etc.) en las que esta sucesión se nos aparece. Por ejemplo, imaginemos hay tres cristales planos horizontales y un rayo de luz que incide sobre ellos oblicuamente desde arriba. El rayo, al llegar, atraviesa el primer plano, pero después de eso el rayo puede atravesar los planos o bien puede rebotar en ellos.

Si el rayo nunca rebota entonces tiene sólo una trayectoria posible: atraviesa los tres planos y listo.

Si el rayo rebota una sola vez entonces tiene dos trayectorias posibles: rebota en el segundo plano o rebota en el tercero.

Si rebota dos veces, hay tres trayectorias: rebota en el segundo y luego en el primero, o bien rebota en el tercero y luego en el segundo, o bien rebota en el tercero y luego en el primero.

Las cantidades de trayectorias son 1, 2, 3, y después sigue 5, 8, 13,... Es decir, obtenemos la sucesión de Fibonacci.

¿Qué sucesiones se obtendrían para cuatro planos, cinco, seis, etc?

Solución para tres planos: Construimos la sucesión que comienza con 1, 2 y que luego es del tipo 1, 1, 1, 1,.... De ella tomamos todos los términos. Obtenemos la sucesión de Fibonacci.

Solución para cuatro planos: Construimos la sucesión que comienza con 1, 2, 3 y que luego es del tipo 1, 3, 1, 3, 1, 3,... De ella tomamos el primer término y luego vamos saltando uno. De 1, 2, 3, 5, 6, 11, 14, 25, 31, 56, 70, ... nos quedamos con 1, 3, 6,14, 51, 70,.... Esta sucesión nos da la cantidad de trayectorias para 0, 1, 2, 3,... rebotes si hay cuatro planos.

Solución para cinco planos: Construimos la sucesión que comienza con 1, 2, 3, 4 y que luego es del tipo 1, 3, 5, 1, 3, 5, 1, 3, 5,... De ella tomamos el primer término y luego vamos saltando dos.

Solución para n planos: Construimos la sucesión que comienza con 1, 2, 3,..., n-1 y que luego es del tipo 1, 3, 5, 7, ..., 2n-5, 1, 3, 5, 7,..., 2n-5, De ella tomamos el primer término y luego vamos saltando n–3. Ésta es la solución para n planos.

Problemas:

a) Es sabido que los cocientes de términos consecutivos de la sucesión de Fibonacci se acerca cada vez más a la razón áurea o número de oro. Esto es cierto aunque en lugar de 1, 1,... se elija otro comienzo cualquiera. ¿Puede decirse algo sobre los cocientes de los términos consecutivos de estas sucesiones generalizadas? ¿Qué ocurre con los cocientes de una sucesión de tipo 2, 2, 2, 2, 2,... o 3, 3, 3, 3,... o, en general, k, k, k, k,...? ¿Depende de los términos iniciales? ¿Depende de k?

b) Observemos que la sucesión natural 1, 2, 3, 4, 5,... cae también dentro de este tipo general. Se definiría como aquella que comienza con 1, 2 y luego es del tipo 1, 2, 3, 4, 5, 6, 7,... ¿Hay otras sucesiones conocidas que sean de este tipo general?

T(n,m) - Problema 6

Otra vez tenemos dos personajes; cada uno de tipo T(n.m) con n > 0 y m > 0, no necesariamente el mismo tipo para cada uno.

C dice: D es T(1,1).
D dice: C es T(1,2).
C dice: D es T(1,2).
D dice: C es T(1,1).

Ahí paran.

¿A qué tipo pertenece cada uno?

T(n,m) - Problema 5

Otro problemita sobre los T(n,m):

Tenemos dos personajes; cada uno de tipo T(n.m) con n > 0 y m > 0, no necesariamente el mismo tipo para cada uno.

A dice: B es T(1,1).
B dice: A es T(1,2).
A dice: B es T(1,2).
B dice: A es T(1,1).


Y así siguen indefinidamente.

¿A qué tipo pertenece cada uno?

7.11.05

Función discontinua

Un nuevo problema topológico. En realidad ya había publicado este problema en la lista snark, y allí fue correctamente respondido. De todos modos, no me parece inoportuno repetirlo aquí:

El problema consiste en hallar una función F(x) de variable real (es decir, una función F de R en R, considerado R con la topología usual), que sea discontinua, pero que tenga igualmente la siguiente propiedad: si A es cualquier subconjunto conexo de R entonces F(A) es conexo.

(Toda función continua cumple la propiedad, la idea es hallar una función que la cumpla a pesar de ser discontinua.)

Operación

¿Qué operación es *?

1 * 1 = 3
1 * 2 = 6
2 * 1 = 5
2 * 2 = 10
1 * 3 = 7
3 * 1 = 7
2 * 3 = 11
3 * 2 = 14
3 * 3 = 15

1*4 = 12
4*1 = 9
2*4 = 20
4*2 = 18
3*4 = 28
4*3 = 19
4*4 = 36

3.11.05

T(n,m) - Problema 4

Otro problemita sobre los T(n,m):

Tenemos tres personajes, uno de ellos es T(1,1), otro es T(1,0) y el tercero es T(0,1). Uno de ellos usa sombrero blanco, otro usa sombrero negro y otro sombrero gris, aunque no necesariamente en ese orden.

B dice: C es T(1,0).
C dice: A lleva sombrero negro.
A dice: B es T(1,1).
B dice: C lleva sombrero blanco.

¿A qué clase pertenecen A, B y C? ¿Quién usa cada sombrero?

2.11.05

Planaridad

Un juego on line con fuertes connotaciones topológicas. (He tomado prestada la referencia de Juegos de Ingenio.)

1.11.05

Sombreros rojos, sombreros verdes

En una habitación hay cierto número de personajes, cada uno de los cuales tiene puesto un sombrero. Algunos llevan sombreros rojos, los demás llevan sombreros verdes y mientras que cada uno puede ver los sombreros que llevan todos los demás, no puede ver el propio.

Algunos de las personajes son "normales" y ven rojos a los sombreros rojos y verdes a los sombreros verdes. Otros son "inversos", a los sombreros rojos los ven de color verde y a los sombreros verdes los ven de color rojo.

Cada uno va declarando por turno los colores que ve. En su declaración cada personaje dice sinceramente lo que cree ver. Por ejemplo, si un personaje tuviera frente a sí 8 sombreros rojos y 6 verdes, entonces un "normal" diría eso: que ve 8 sombreros rojos y 6 verdes. Un "inverso", en cambio, diría que ve 8 verdes y 6 rojos.

Ahora el problema:

En la habitación hay 50 personajes, 49 de ellos declaran que ven 25 sombreros rojos y 24 verdes. El personaje restante declara que ve 24 sombreros rojos y 25 verdes. Se sabe que hay más normales que inversos.

¿Cuántos normales hay? ¿Cuántos de ellos usan sombreros rojos y cuántos usan sombreros verdes?

Retorno a la serie

En una entrada anterior preguntaba acerca de la regla de construcción de la siguiente serie:

no hay, 0, 0, 1, 0, 1, 0, 3, 2, 3, 0, 1, 0, 3, 2, 3, 0, 1, 0, 3, 2, 9, 0, 5, 6, 3, 4, 9, 0, 1, 0, 9, 4, 3, 6, 5, 0, 9, 2, 3, 0, 1, 0, 3, 2, 15, 0, 5, 12, 3,...

Al momento de escribir estas líneas, nadie había respondido la pregunta. O al menos nadie había escrito la respuesta en forma de comentario. Como ayuda, digo que la serie se relaciona de lguna manera con la conjetura de Goldbach.

Lo que sigue puede servir (o no) de pista para quienes aún no lograron responder la cuestión original y como problema adicional para quienes sí lograron hallar la respuesta.

Una aclaración previa: se llaman primos gemelos a los pares de primos cuya diferencia es exactamente igual a 2 (por ejemplo 3 y 5, 5 y 7, 11 y 13, etc). Se cree que existe una cantidad infinita de tales pares, aunque esto nunca ha sido demostrado. Excepto en el caso 3 y 5, el número central entre cada par de primos gemelos es siempre un múltiplo de 3.

El nuevo problema consiste en demostrar que la serie no hay, 0, 0, 1, 0, 1, 0, 3, 2, 3, 0, 1, 0, 3, 2, 3, 0, 1, 0, 3, 2, 9, 0, 5, 6, 3, 4, 9, 0, 1, 0, 9, 4, 3, 6, 5, 0, 9, 2, 3, 0, 1, 0, 3, 2, 15, 0, 5, 12, 3,... tiene las siguientes propiedades:

a) Si es cierto que existen infinitos pares de primos gemelos, entonces en la serie existen infinitas ternas de números consecutivos que son de la forma n, n–1, n. Ejemplos de ternas así son 1, 0, 1 y 3, 2, 3.

b) Excepto en la primera terna de la forma n, n–1, n (que es 1, 0, 1) en todas las demás el número central cae en un lugar que es múltiplo de 3.

c) Excepto las ternas 0, 1, 0, no existen otras ternas que sean de la forma n, n+1, n.

d) La secuencia simétrica 0, 1, 0, 3, 2, 3, 0, 1, 0, 3, 2, 3, 0, 1, 0 aparece una sola vez en toda la serie.