Mostrando entradas con la etiqueta Problema de lógica. Mostrar todas las entradas
Mostrando entradas con la etiqueta Problema de lógica. Mostrar todas las entradas

Problemita de lógica (4)

En los comentarios al problema anterior Marcos Donnantuoni se pregunta si la solución de aquél problema es única. Esa pregunta, a su vez, me inspira este nuevo problema.

Para cada afirmación indicar si es verdadera o falsa:
1) La siguiente afirmación es falsa.
2) El problema tiene solución única.


Problemita de lógica (3)


1) En esta lista hay más afirmaciones verdaderas que falsas.
2) En esta lista hay más afirmaciones verdaderas que falsas.
3) En esta lista hay tantas afirmaciones verdaderas como falsas.
4) En esta lista hay más afirmaciones falsas que verdaderas.

¿Cuáles de estas afirmaciones son verdaderas y cuáles son falsas?

Problemita de lógica (2)

Cada casilla debe quedar pintada de blanco o de negro. Las casillas blancas contienen siempre afirmaciones verdaderas, las casillas negras contienen siempre afirmaciones falsas. Ninguna fila ni ninguna columna está formada por casillas que sean todas del mismo color. 

Actualización: ¡Cuidado! Había un error en el enunciado (en la casilla que ahora está de otro color). Por las dudas una aclaración, en la tercera casilla de la primera fila, la frase "la casilla aquí abajo" se refiere a la casilla inmediatamente inferior y no a la última de la columna.


Otra actualización: Pablo Rowies (quien me había advertido del error que había antes) y Laura Spivak lo han resuelto correctamente.

Problemita de Lógica (1)



1) En esta lista hay más afirmaciones verdaderas que falsas.
2) En esta lista hay tantas afirmaciones verdaderas como falsas.
3) En esta lista hay más afirmaciones falsas que verdaderas.

¿Cuáles de estas afirmaciones son verdaderas y cuáles son falsas?

El ABC de la creación (3): imposibilidades

Pares y nones
Las reglas del juego y los primeros desafíos pueden verse en este enlace, otros desafíos pueden verse en este otro enlace.

De los dos últimos desafíos planteados en la entrada original, uno de ellos pedía pasar de la cinta vacía a una que contuviera solamente la letra A, y el otro desafío, pasar de la letra A a la letra B. En los comentarios a esa misma entrada Marcos Donnantuoni conjeturó que estos objetivos son imposibles de alcanzar; mi intención aquí es demostrar que, en efecto, son imposibles.

La demostración de ambas imposibilidades pasa por un argumento de paridad. Recordemos que la primera regla dice que donde haya dos casillas vacías es posible "crear" dos letras iguales; la segunda regla enuncia la operación inversa, dos letras iguales y consecutivas pueden ser borradas. La tercera regla dice que dos letras diferentes consecutivas (AB, por ejemplo) pueden ser cambiadas por la letra restante (en el ejemplo, una C).

Pensemos ahora en las cantidades de letras que haya en la configuración inicial, y específicamente fijémonos en sus paridades. Las dos primeras reglas no alteran la paridad de esas cantidades, ya le suman o le restan un 2 a una de ellas. La tercera regla, en cambio, cambia las tres paridades a la vez, ya que le suma un 1 a una cantidad y le resta 1 a las otras dos. Es decir, al aplicar cualquiera de las reglas, o bien las tres paridades no cambian, o bien cambian todas a la vez.

Esto significa que, si al comenzar, las cantidades de dos de las letras tenían la misma paridad (ambas cantidades eran pares o ambas eran impares) entonces a lo largo de todo el proceso esas cantidades seguirán teniendo la misma paridad (porque, en caso de cambiar, ambas paridades cambiarán al mismo tiempo); y si esas dos cantidades, al comenzar, tenían diferente paridad entonces la paridad seguirá siendo siempre diferente (por la misma razón). Podemos decir, en resumen, que las paridades relativas de las cantidades de letras no cambiarán nunca.

Ahora bien, si quisiéramos pasar de la cinta vacía a la letra A entonces al comenzar las cantidades de A y de B tendrían la misma paridad (ambas cantidades serían pares, ya que valen cero), mientras que al terminar habría una cantidad impar de A (una letra) y una cantidad par de B (cero). La paridad relativa de A y B habría cambiado, lo cual es imposible. Luego, no puede pasarse de la cinta vacía a una sola A. Lo mismo sucede si queremos pasar de A a B, porque al comenzar A y C tendrían diferente paridad (uno y cero son las cantidades iniciales de esas letras), pero al terminar tendrían la misma (cero y cero, ambas pares).

Una pregunta que queda pendiente es si vale la afirmación recíproca; es decir, si tenemos dos configuraciones de letras en las cuales las paridades relativas de A, B y C son las mismas (es decir, dos paridades que sean iguales/diferentes en una configuración son también iguales/diferentes en la otra configuración) entonces ¿es siempre posible pasar de una configuración a la otra? Creo que la respuesta es que sí, aunque no he podido encontrar una demostración elegante de ese hecho.

El ABC de la creación (2): soluciones y nuevos desafíos.

Espacio versus tiempo
Las reglas del juego y los primeros desafíos pueden verse en este enlace

Marcos Donnantuoni propone una variante para todos los desfíos que consiste en buscar la solución que ocupe el menos espacio posible, en lugar del menor tiempo. Es decir, ahora buscamos la solución que pueda ser desarrollada en la cinta de menor longitud (a igualdad en espacio, será mejor la solución en menor tiempo).

Éstas son, hasta ahora, las mejores soluciones para los tres primeros desafíos en esta variante.

(a) Pasar de la cinta vacía a ABC y (b) pasar de ABC a BCA: Las soluciones óptimas en tiempo (ambas de Marcos, con 5 pasos) son también hasta ahora las mejores en espacio, con 4 espacios cada una (no parece que se pueda mejorar). Las copio aquí:
0 ----
1 --AA
2 AAAA
3 A--A
4 ABBA
5 ABC-

0 ABC-
1 AA--
2 AAAA
3 A--A
4 ABBA
5 -CBA

(c) A partir de ABC recorrer las otras cinco permutaciones de esas letras: MFR tiene una solución en 25 pasos (óptima en tiempo) que sólo usa 5 espacios (la de Marcos, también de 25 pasos, pblicada en el entrada anterior, si no conté mal -y pude haber contado mal- usa 10 espacios):
00   ABC--
01   C-C--
02   C-CAA
03   C--BA
04   CCCBA
05   --CBA
06   --C-C
07   BBC-C
08   BA--C
09   BACCC
10   BAC--
11   B-B--
12   B-BAA
13   B--CA
14   BBBCA
15   --BCA
16   --B-B
17   AAB-B
18   AC--B
19   ACBBB
20   ACB--
21   -BB--
22   -BBBB
23   -B--B
24   -BAAB
25   --CAB

Dos nuevos desafíos:

El caminante (propuesto por Leonardo): pide hacer "caminar" una letra A n pasos hacia la derecha o hacia la izquierda. MFR pudo hacer "caminar" una A una cantidad par n de casillas, a la izquierda o a la derecha, en exactamente n pasos; por ejemplo para = 4:

00   A----
01   AAA--
02   --A--
03   --AAA
04   ----A

"Para moverla sólo un lugar", dice MFR, "cuesta un poquito más de trabajo, a mí me salió en 5 pasos (y utilizando dos 'espacios' adicionales en sentido opuesto al que queremos 'avanzar')":
00   --A-
01   BBA-
02   BC--
03   BCAA
04   BB-A
05   ---A

Leonardo, por su parte, tiene una solución para mover A un paso a la derecha en 3 tiempos (y 4 espacios):
00 -A--
01 -ABB
02 --CB
03 --A-

Actualización del 15.11.13: Escribe Leonardo en los comentarios.
Conclusiones sobre traslados de A:
Para cualquier número n de pasos, con n par, la cantidad mínima es n. 
Para cualquier número n de pasos, con n impar, la cantidad mínima es n+2.
Por otra lado, y como consecuencia de esto, dado un número n cualquiera, si se lo escribe de la forma q+w, siendo q y w enteros positivos, entonces la cantidad de pasos necesarios para moverlo n lugares será igual a la de q sumada a la de w.
En otras palabras, si definimos una función P(n) que es la mínima cantidad de pasos necesarios para trasladar una A n lugares, entonces P(n)=P(q+w)=P(q)+P(w) siempre que q+w=n.

Desafío escatológico (propuesto por Marcos): pide pasar de BABA a CACA...
...(1) en la menor cantidad de tiempo
...(2) usando el menor espacio.

Claudio Meller tiene una solución en 7 pasos y 6 espacios, y otra en 8 pasos y 5 espacios.
7 PASOS  SEIS ESPACIOS
0. --BABA
1. CCBABA
2. CA-ABA
3. CA--CA
4. CACCCA
5. CAC--A
6. CACAAA
7. CACA

8 PASOS CINCO ESPACIOS
0. -BABA
1. --CBA
2. CCCBA
3. C--BA
4. CAABA
5. CA-CA
6. CA--B
7. CACCB
8. CACA-

La solución ¿óptima? de Marcos tiene 6 pasos y 5 espacios:
0 BABA-
1 BAC--
2 BACAA
3 B - BAA
4 B--CA
5 BAACA
6 -CACA

El ABC de la creación

Tres simples reglas para un pequeño Big Bang
(Ésta es la transcripción de mi charla en el 4º Encuentro para Celebrar el Ingenio de Martin Gardner y Jaime Poniachik.)

El universo en el que transcurre este pequeño Big Bang es una cinta dividida en casillas todas iguales; es necesario aclarar que la cinta es infinita, en el sentido de que puede ser prolongada indefinidamente por cualquiera de sus dos extremos:

Este universo contiene solamente tres tipos de partículas, a las que llamaremos A, B y C. Una "ley natural" dice que cada casilla puede contener como máximo una partícula.

Hay tres reglas que rigen el modo en el que las partículas son creadas o destruidas. Estas reglas están resumidas en la siguiente imagen:



Regla 1: En dos casillas vacías consecutivas pueden colocarse dos letras iguales (en la imagen se ejemplifica con AA, pero también puede ser BB o CC).

Regla 2: Es la inversa de la anterior; dos letras iguales consecutivas pueden ser borradas (como antes, en la imagen se ejemplifica con AA, pero también puede ser BB o CC):

Reglas 3: Dos letras diferentes consecutivas pueden ser reemplazadas por la tercera letra, es decir, las dos letras se borran y el lugar que ocupaba una de ellas pasa a ser ocupado por la otra letra. En la imagen se ejemplifica el reemplazo de AB por C, pero también vale para reemplazar BA por C, CA por B, AC por B, etc.

Veamos un ejemplo de aplicación de las reglas:

En el ejemplo hemos partido del universo vacío y hemos llegado a la configuración A-espacio-B-espacio-C. Esto se ha conseguido en seis pasos; un "paso" consiste siempre en la aplicación de una de las tres reglas.

En los desafíos se parte de una cierta configuración y se debe llegar a otra, siempre en la menor cantidad posible de pasos. Los desafíos están resumidos en esta imagen:

Desafío (a): Partir del espacio vacío y llegar a ABC (sin espacios intermedios). Se entiende que al terminar la cinta sólo muestra ABC, el resto del universo está vacío. Yo lo logré en 10 pasos, pero la solución no es necesariamente la óptima. De hecho, la noche misma del encuentro Pablo Coll me aseguró que había encontrado una solución en solamente 6 pasos y que después me la enviaría.

Desafío (b): Partir de ABC y llegar a BCA; las tres letras finales no tienen por qué ocupar las mismas casillas que las iniciales. Yo lo logré en 10 pasos, pero la solución no es necesariamente la óptima.

Desafío (c): Partir de ABC y lograr que se vayan formando sucesivamente las otras cinco permutaciones posibles de esas tres letras (ACB, BCA, BAC, CAB y CBA, no necesariamente en ese orden). En su momento, cada permutación debe aparecer sola en la cinta; la cuenta de los pasos termina en el momento en que aparece la sexta permutación (sea cual fuere). Yo lo logré en 23 pasos, la solución tampoco es necesariamente la mejor.

En los dos últimos desafíos, para hacerlos más interesantes, no doy cantidades de pasos:

Desafío (d): Partir de la cinta vacía y llegar a A.

Desafío (e): Partir de A y llegar a B (la B no debe ocupar necesariamente la misma casilla que la A).

Las soluciones que lleguen (por mail o dejadas en los comentarios) serán publicadas aquí mismo, más abajo.

Gracias... ¡y que se diviertan!

Soluciones:
(a) Pablo Rowies dio en los comentarios una solución para el desafío (a) en 8 pasos que Claudio Meller, también en los comentarios, mejora a 6 pasos y Marcos Donnantuoni, a 5:
0 - - - -
1 - - AA
2 AAAA
3 A - - A
4 ABBA
5 ABC

(b) Pablo Rowies da una solución en 8 pasos para el desafío 2 que Claudio Meller mejora a 6 pasos y Marcos Donnantuoni, a 5:
0 ABC -
1 AA - -
2 AAAA
3 A - - A
4 ABBA
5 - CBA

(c) Marcos Donnantuoni y Claudio Meller encuentran soluciones con 25 pasos, tras un estudio informático Marcos aclara que la solución es óptima.
0__________ABC__
1__________ABCBB
2__________ABA_B
3__________AC__B
4__________ACBBB
5__________ACB__ *
6___________BB__
7_________BBBB__
8_________B__B__
9_________BAAB__
10________BAC___ *
11________BB____
12________BBBB__
13________B__B__
14________BCCB__
15________BCA___ *
16______CCBCA___
17______CCB_B___
18______CA__B___
19______CABBB___
20______CAB_____ *
21______CC______
22____CCCC______
23____C__C______
24____CBBC______
25____CBA_______ *

Sólo quedan abiertos los desafíos (d) y (e).

Soluciones óptimas:
Desafío (a): 5 pasos (Marcos Donnantuoni), no puede mejorarse.
Desafío (b): 5 pasos (Marcos Donnantuoni), no puede mejorarse.
Desafío (c): 25 pasos (Claudio Meller y Marcos Donnantuoni), no puede mejorarse.

Gracias por los comentarios en los que se plantean otros desafíos, en breve los incorporaré a una nueva entrada sobre el tema. Por supuesto, también agradezco los comentarios con soluciones, las que corresponde a los nuevos desafíos también aparecerán próximamente en otra entrada sobre este tema.

Éste es el video de la charla.



Problemita lógico de verano

1. Exactamente una de estas afirmaciones es falsa.
2. Exactamente dos de estas afirmaciones son falsas.
3. Exactamente tres de estas afirmaciones son falsas.
...
999. Exactamente novecientas noventa y nueve de estas afirmaciones son falsas.
1000. Todas estas afirmaciones son falsas.

¿Cuáles de estas afirmaciones son verdaderas y cuáles falsas?

Edificios

Edificios es un problema lógico clásico cuyo planteo es el siguiente: en un tablero cuadrado de n hay que colocar números de 1 a n; en cada casilla va exactamente un número y no puede haber dos números iguales en una misma fila o columna. Alrededor del tablero hay pistas que indican cómo deben ser colocados esos números, para entenderlas hay que imaginar que cada uno de los números a colocar representa la altura de un edificio; las pistas nos dicen cuántos edificios ve una persona que esté parada en esa posición si se coloca mirando hacia el tablero, bajo la suposición de que cada edificio oculta a todos los que estén detrás de él y que sean a la vez más bajos que él, pero que no oculta a los que sean más altos. Un ejemplo con su solución:

Una de las condiciones que todo buen problema de lógica debe cumplir es que su solución sea única, es decir, no puede haber dos formas diferentes de completar el tablero respetando a la vez todas las pistas. A veces sucede que este objetivo se logra con una cantidad menor de pistas. Por ejemplo, en el problema anterior hay, en efecto, pistas redundantes. Éste problema, con menos pistas, también tiene solución única:

En su charla en el Tercer Encuentro por Martin Gardner y Jaime Poniachik, Ivan Skvarca (autor del excelente blog aquí enlazado) planteó estas dos preguntas:

1) ¿Siempre es posible, no importa cuál sea el valor de n, plantear un problema de Edificios en un tablero de n x n que tenga solución única? ¿O para valores "grandes" de n esto es imposible?

2) ¿Cuál es la mínima cantidad de pistas que pueden ponerse de modo que la solución sea única?

Mi intención en esta entrada es responder a la primera pregunta y hacer un aporte para la segunda.

1) En una primera aproximación podríamos creer que la respuesta es que para valores suficientemente grandes de n se llega a un punto en que es imposible garantizar que la solución sea única. Después de todo, la cantidad de pistas de las que disponemos crece linealmente con n, mientras que la cantidad de números a colocar crece cuadráticamente (por así decir, hay muchas más incógnitas que datos). Pero este razonamiento es falaz porque no toma en cuenta que hay una pista "global": en cada fila y columna no puede haber dos números iguales.

La respuesta en realidad es que para cualquier valor de n siempre es posible plantear al menos un problema de Edificios de n x n con solución única. El siguiente dibujo da idea de cómo hacerlo si n es mayor o igual que 6:
2) El mismo dibujo nos da una cota para la cantidad mínima de pistas que pueden colocarse en un problema de Edificios de modo que la solución sea única. Vemos que, para n mayor o igual que 6, esto puede lograrse con 2n - 6 pistas; la pregunta que queda ahora planteada es si puede lograrse con una cantidad menor. 

Sudokito con pistas

En cada casilla debe colocarse un número del 1 al 4; en cada fila y en cada columna no puede haber dos números iguales.


Las desventajas de la perfección.

(El texto de esta entrada es una reescritura del artículo originalmente publicado aquí, a partir de una idea de Matías Graña.)

En los problemas de veraces y mentirosos a veces aparecen ciertos personajes a los que se llama lógicos perfectos. Un lógico perfecto es un ser que es capaz de obtener de manera infalible y casi instantánea todas las conclusiones que sea posible extraer de una serie de premisas.

Puede objetarse que es muy difícil encontrar a un ser con estas características; más aún, tal vez hasta se pueda demostrar lógicamente que un ser así no puede existir ni siquiera en teoría. Pero en los problemas de veraces y mentirosos (que, después de todo, son problemas recreativos y no teoremas matemáticos) nadie pretende que los lógicos perfectos existan realmente, sino que la expresión "lógico perfecto" es simplemente un recurso lingüístico cómodo que evita tener que dar un sinfín de explicaciones.

Por ejemplo, pensemos en este problema que, estrictamente hablando, no es de veraces y mentirosos pero cae dentro de la misma familia (tomado de aquí):

Tres personas entran en un bar y el mozo les pregunta si todos van a tomar café.
El primero responde: No sé.
El segundo responde: No sé.
El tercero responde: .

La pregunta es ¿cómo se explican esas respuestas?

Así formulada, la pregunta tiene miles de respuestas posibles, como por ejemplo que los dos primeros son indecisos y el tercero es el líder del grupo, y tantas otras que es fácil imaginar. Ahora bien, si aclaramos que las tres personas responden verazmente en base a la información que poseen (o no poseen) y en base a las conclusiones que de esa información se puede extraer y que no fallan al obtener esas conclusiones, en dos palabras, si decimos que los tres son lógicos perfectos, entonces la respuesta es sólo una... que les dejo a ustedes para encontrar.

Ahora bien, dejemos volar la imaginación y supongamos que que sí existen los lógicos perfectos, y que por algún procedimiento semimágico fuera posible convertirse en uno. Supongamos además que estamos a punto de enfrentar una situación en la que va a ser indispensable extraer rápidamente conclusiones lógicas a partir de ciertas premisas; más aún, supongamos que nuestra libertad va a depender de que seamos capaces de razonar rápida y correctamente. Bajo estas circunstancias ¿no aceptaríamos convertirnos en lógicos perfectos? ¿No lo sentiríamos como una garantía de triunfo? Pues bien, les voy a contar una historia en la que ser un lógico perfecto sería, quizás, una desventaja.

En esta historia, en los calabozos del palacio de un un rey, hay tres prisioneros a los que llamaremos A, B y C. Como es su cumpleaños, el rey ha decidido que uno de ellos tenga la posibilidad de ser liberado. Para eso organiza este juego:

En una caja hay 7 estampillas, cuatro rojas y tres verdes. A los prisioneros se les vendarán los ojos, cada uno se le pegarán en la frente dos estampillas tomadas al azar de la caja y luego se les quitarán las vendas. De este modo, cada uno podrá ver las estampillas que tienen los demás, pero no verán las propias ni tampoco sabrán cuál es la estampilla que quedó en la caja, aunque sí sabrán cuántas estampillas de cada color hay en total.

En orden (el orden fue sorteado de antemano y quedó así: A, B, C) cada prisionero intentará deducir cuáles son las estampillas que tiene en la frente. Si arriesga y acierta, es liberado y el juego termina (los otros dos vuelven a prisión). Si arriesga y pierde, ya no tiene chance de arriesgar otra vez y habrá perdido (vuelve a la prisión). Si no dice nada y pasa, sigue en juego y puede volver arriesgar después si es que la ronda vuelve a él y nadie gana antes.

Supongamos que a A le pegan una estampilla verde y una roja, a B dos verdes y a C dos rojas; y supongamos además que los tres son lógicos perfectos. ¿Qué sucede entonces?

A puede ver dos estampillas verdes y dos rojas; sabe que faltan dos rojas y una verde, pero no tiene forma de deducir si en su frente tiene dos rojas o una roja y una verde. Por lo tanto pasa sin arriesgar.

B puede ver tres rojas y una verde; sabe que faltan dos verdes y una roja, pero no tiene forma de deducir si tiene dos verdes o una verde y una roja. Por lo tanto pasa sin arriesgar.

C tiene a la vista las tres estampillas verdes, de modo que deduce que todas las que quedan son rojas. Dice en voz alta que tiene dos rojas, gana y es liberado.

Al prisionero A no le convino ser lógico perfecto. "Bueno", pensarán ustedes, "¿qué otra cosa podría haber hecho, después de todo?". Pero si en lugar de ser un lógico perfecto, A hubiera sido simplemente racional entonces podría haber pensado así:

"O tengo dos estampillas rojas, o tengo una roja y una verde. Si tuviera dos rojas, B tendría a la vista las cuatro estampillas rojas, deduciría entonces que él tiene dos verdes y ganaría. Si yo tuviera una roja y una verde entonces C tendría a la vista las tres verdes, deduciría que él tiene dos rojas y ganaría. En cualquier caso, si no arriesgo estoy perdido. Ahora bien, hay tres estampillas de las que no sé dónde están, dos son rojas y una es verde; por lo tanto hay una probabilidad de 2/3 de que la estampilla de la caja sea roja y 1/3 de que sea verde. Por lo tanto, la probabilidad de yo tenga una verde y una roja es de 2/3 y solamente 1/3 de que tenga dos rojas." En base a este cálculo, A arriesgaría que tiene una verde y una roja... y ganaría.

El riesgo calculado le ha ganado al razonamiento perfecto.

Razonamiento

Teorema: Dado cualquier número irracional existe una sucesión de números racionales que converge a él.


Demostración: Tomemos, por ejemplo, el número Pi = 3,141592... Consideremos la sucesión: 3; 3,1; 3,14; 3,141; 3,1415;... Es claro que se trata de una sucesión de números racionales que converge a Pi. Por otra parte, es obvio también que el mismo procedimiento puede repetirse para cualquier otro número irracional. Por lo tanto el teorema queda probado.


La pregunta es: ¿Es válida esta demostración?

Solución de "Un curioso problema de sombreros"

(Viene de este problema.)

La solución es la siguiente: El coordinador se coloca en un extremo de la habitación e indica que 50 personas se coloquen a su derecha y las otras 50 a su izquierda. Luego ordena que se emparejen, cada persona de la derecha con una persona de la izquierda.

La siguiente indicación del coordinador es que cada uno mire el sombrero de su pareja y que al sonar el gong hagan lo siguiente:

a) El miembro de la pareja que estaba inicialmente a la derecha debe decir en voz alta el color que esté viendo (por ejemplo, si su pareja tiene un sombrero blanco entonces dirá "blanco").
b) El miembro de la pareja que estaba inicialmente a la izquierda debe decir en voz alta el color opuesto al que esté viendo (por ejemplo, si su pareja tiene un sombrero blanco entonces dirá "negro").

Comprobemos que este mecanismo asegura que 50 personas dirán su propio color de sombrero. Hay cuatro casos a considerar: que los dos tengan sombreros blancos, que los dos tengan sombreros negros, que el de la derecha tenga blanco y el otro negro, y el opuesto de este último caso.

Si los dos tienen sombreros blancos, al sonar el gong el miembro de la derecha dirá "blanco", su propio color de sombrero. (El otro miembro de la pareja dirá "negro" y fallará.)

Si los dos tienen sombreros negros, al sonar el gong el miembro de la derecha dirá su color de sombrero y el otro miembro fallará.

Es fácil ver que si los colores de sombrero son diferentes entonces el miembro de la izquierda dirá su propio color y el de la derecha se equivocará.

En resumen: al sonar el gong, exactamente un miembro de cada pareja dirá su propio color de sombrero, por lo tanto un total de exactamente 50 personas acertará. Todo esto sin que el coordinador necesite ver un solo sombrero.

Hasta aquí el problema planteado por Adrián Paenza. Demos ahora una vuelta de tuerca.

Supongamos que haya un segundo gong. Una sola indicación adicional puede lograr que al sonar este segundo gong las 100 personas digan correctamente su propio color de sombrero. La indicación sería:

c) Observe qué dijo su compañero al sonar el primer gong. Si su compañero acertó al decir su propio color de sombrero entonces, al sonar el segundo gong, usted cambie lo que dijo la primera vez (por ejemplo, si la primera vez usted dijo "blanco", al sonar el segundo gong dirá "negro"). Si su compañero falló al decir su propio color, entonces, al sonar el segundo gong usted repetirá lo que dijo la primera vez.

De esta forma, con tres simples indicaciones, se logra que, al sonar el segundo gong, las 100 personas digan correctamente su propio color de sombrero.

Un curioso problema de sombreros

Unos días atrás vi, en uno de sus programas de televisión, a Adrián Paenza mientras contaba la solución de un problema de lógica. No llegué a ver el enunciado, pero creo que pude deducirlo con bastante exactitud a partir de la solución. El enunciado del problema (al que me parece que le estoy agregando algún dato adicional) diría más o menos así:

En una habitación (una habitación grande) hay 100 personas. Algunos tienen sombreros blancos y otros tienen sombreros negros. Nadie puede ver su propio color de sombrero, aunque sí puede ver el color de todos los demás. Las personas no saben qué cantidad de sombreros de cada color hay en total (incluso podrían ser todos del mismo color), por lo que inicialmente nadie tiene información suficiente como para deducir su propio color de sombrero. En un momento dado sonará un gong. En ese instante todas las personas dirán a la vez un color (blanco o negro).

Supongamos que, además, hay un coordinador (un individuo adicional, que no tiene sombrero). El coordinador no le puede dar a nadie información acerca del color de sombrero que tiene (más aún, el coordinador podría ser ciego o tener los ojos vendados). De hecho, el coordinador no puede dar ninguna información del tipo que sea. Las personas con sombreros tampoco pueden darse información entre sí. El coordinador tiene permitido dar órdenes o instrucciones a las personas con sombreros, siempre que no impliquen transmisión de información. Las personas con sombreros sólo dirán una palabra en el momento que suene el gong, y nada más. (Por supuesto no hay trampas, como la existencia de espejos, o que se hagan señas, etc.)

El objetivo del coordinador es lograr que, cuando suene el gong, al menos la mitad de las personas presentes diga su propio color de sombrero.

Por supuesto, si todos dicen un color al azar, hay una alta probabilidad de que al menos la mitad acierte con su propio color, pero no queremos eso, queremos la certreza absoluta de que al menos la mitad acertará. La pregunta es: ¿qué instrucciones debe dar el coordinador para asegurase de que al menos la mitad acertará?

Para quienes no hayan visto el programa, les dejaré unos días para que piensen la respuesta. Mi intención no es tanto plantear el problema en sí, como comentar (en la próxima entrada) una curiosa consecuencia de la solución.

La solución puede verse aquí.

Pruebas de elección múltiple

1. Marque con X las respuestas correctas (podría no haber ninguna):

a) Ninguna respuesta es correcta. ( )
b) Esta respuesta es correcta. ( )
c) Todas las respuestas son correctas. ( )

2. Marque con X las respuestas correctas (podría no haber ninguna):

a) Esta respuesta es correcta. ( )

El Sombrerero Loco

Descripción

Llamo a este esquema El Sombrerero Loco: En una habitación hay cierto número de personajes; cada uno tiene un sombrero, que puede ser de color blanco o de color negro. Todos los personajes ven el sombrero que tienen los demás, pero nadie conoce ni puede ver el propio.

Se supone que los que tienen sombreros blancos deben hacer siempre afirmaciones verdaderas y que los que tienen sombreros negros deben hacer siempre afirmaciones falsas. Ahora bien, como al principio nadie sabe cuál es realmente su color de sombrero, cada personaje adopta al comenzar una postura cualquiera. Es decir, cada uno decide (independientemente de cuál sea su sombrero) hacer siempre afirmaciones falsas o hacer siempre afirmaciones verdaderas.

Cuando un personaje hace una afirmación, otro personaje puede advertirle que no se está comportando correctamente. Es decir, le puede decir que está haciendo una afirmación falsa cuando su sombrero en realidad es blanco, o que está haciendo una afirmación verdadera mientras que su sombrero es negro. La advertencia es así: No deberías decir eso. La advertencia opuesta es: Bien dicho. Claro está que quien hace esta advertencia podría, a su vez, estar mintiendo.

Cuando, a partir de lo que ve y de lo que oye, un personaje logra deducir cuál es su propio color de sombrero, entonces (sin ninguna advertencia) comienza a comportarse tal como este color indique. Si deduce que su color es negro, a partir de ese momento hará afirmaciones falsas; si deduce que es blanco, hará afirmaciones verdaderas (esto puede significar, o no, un cambio en el comportamiento que venía teniendo).

Observemos finalmente que todos oyen lo que dicen los demás y que todos son lógicos perfectos, es decir, conocen inmediatamente todas las consecuencias lógicas de lo que se dice.

El problema

Tenemos cuatro personajes, a los que llamaremos Abel, Benito, Carlos y Darío.

Abel le dice a Benito: Tu sombrero es negro.
Carlos le dice a Abel: No deberías decir eso.
Darío le dice a Carlos: Bien dicho.
Benito le dice a Abel: Tu sombrero es blanco.
Darío le dice a Benito: No deberías decir eso.
Darío le dice a Abel: Tu sombrero es blanco.
Benito le dice a Darío: No deberías decir eso.
Abel le dice a Darío: Nuestros sombreros son del mismo color.

¿De qué color es el sombrero de cada uno? ¿Qué postura adoptó cada uno inicialmente?

Viaje al planeta Biplantar

Cierta vez Spock, el viajero espacial estudioso de la Lógica, llegó al planeta Biplantar. En este planeta, como en tantos otros visitados por Spock, la población entera está dividida en dos grupos: el de los veraces y el de los mentirosos. Los veraces sólo hace afirmaciones rigurosamente verdaderas mientras que los mentirosos sólo hacen afirmaciones falsas.

En este planeta, además, todas las casas tienen dos plantas, a las que, en un alarde de imaginación, llamaremos inferior y superior. En una de las plantas (puede ser la inferior o puede ser la superior, eso depende de cada casa) viven solamente veraces, en la otra planta, obviamente, viven solamente mentirosos. Esto no quiere decir que cada uno de ellos esté confinado a una planta específica, cual si de prisioneros se tratara. Por el contrario, quienes viven en una planta pueden visitar libremente la otra, pero "viven" (moran, pernoctan, residen) sólo en una las dos.

En los pueblos o en las ciudades pequeñas las casas son de estructura sencilla y cualquier visitante sabe en todo momento en qué planta de la casa se encuentra. En las grandes ciudades, en cambio, las casas pueden tener una estructura muy compleja, laberíntica diríamos, con escaleras falsas que parecen conducir a plantas inexistentes, ventanas con falsos paisajes (creados por jardines elevados artificialmente o por juegos de espejos), puertas falsas y otras trampas para la percepción de tal modo que, después de un tiempo de transitar por sus habitaciones, el visitante puede perder la noción de si se encuentra en la planta inferior o en la superior (aunque el residente nunca se extravía y siempre sabe perfectamente dónde se encuentra).

En su primer día en el planeta Biplantar, Spock se encontraba en una casa en un pueblo pequeño. Había llegado hacía una o dos horas, pero todavía no tenía idea de quiénes vivían en cada planta. En ese momento vio a un residente (que vivía en esa casa, aunque no necesariamente en la planta donde ambos se encontraban) y después de saludarlo, Spock le preguntó a qué grupo pertenecía (es decir, si era veraz o mentiroso). El nativo respondió:

Si yo dijera: "Si hay una planta sobre nosotros entonces yo vivo en ella", entonces usted podría deducir a qué grupo pertenezco.

De esta información Spock dedujo enseguida en qué planta vivían los veraces y en qué planta, los mentirosos. Tal vez dedujo otras cosas, tal vez no. (Pero nótese que el hecho de que Spock tenga la información suficiente como para hacer una determinada deducción no significa necesariamente que la tengamos también nosotros.)

Las preguntas son: ¿El nativo que habló con Spock era veraz o mentiroso? ¿En qué planta de la casa estaban los dos, la inferior o la superior? ¿En cuál de las dos plantas vivían los veraces?

Para cada pregunta el desafío es, o bien responderla, o bien demostrar que la información que se tiene es insuficiente para dar una respuesta certera.

Que se diviertan...

Acertijo en 6 por 6

El protagonista de este problema es un tablero de 6x6...

...y el objetivo es completarlo de acuerdo con las siguientes reglas:

1. Cada una de las casillas con un círculo debe contener un número, que sólo puede ser, en cada caso, un 1 o un 4. En las demás casillas no habrá números.
2. Al terminar, debe haber al menos un 1 y al menos un 4.
3. Algunas de las casillas restantes contendrán minas (a modo de ayuda, una ya está colocada), otras, eventualmente, pueden quedar vacías.
4. Las casillas con círculos no contienen minas, ni pueden quedar vacías.
5. Como en el Buscaminas de Windows, cada número debe indicar cuántas minas hay en las casillas que están alrededor de él.

Que se diviertan....

Y aún otro problemita de lógica

Como ya dijimos, los nativos de Verdalia pertenecen, o bien al grupo de los veraces (que sólo hacen afirmaciones verdaderas), o bien al de los mentirosos (que sólo hacen afirmaciones falsas). Abel, Bruno y Carlos son todos nativos de Verdalia y cada uno sabe a qué grupo pertenecen los otros.

Abel dice: Carlos es... (la historia no registra cómo termina la frase, aunque sí se sabe que el final era veraz o mentiroso).
Bruno dice: Abel dijo que Carlos es veraz.
Carlos dice: Exactamente dos de nosotros son mentirosos.

¿A qué grupo pertenece cada uno?

Otro problemita de lógica

Los nativos de Verdalia pertenecen, o bien al grupo de los veraces (que sólo hacen afirmaciones verdaderas), o bien al de los mentirosos (que sólo hacen afirmaciones falsas). Abel, Bruno, Carlos y Darío son todos nativos de Verdalia y cada uno sabe a qué grupo pertenecen los otros.

Abel dice: Exactamente dos de nosotros son veraces.
Bruno dice: Exactamente dos de nosotros son veraces.
Carlos dice: Darío es mentiroso.
Darío dice: Abel es mentiroso.

¿A qué grupo pertenece cada uno?