jueves, 30 de octubre de 2008

Zigurates


(nota: Jaime Poniachik planteó la idea de los zigurates lineales, yo sólo modifiqué la dimensión)

Un zigurate es una estructura escalonada similar a una pirámide, pero posiblemente truncada, como la de la figura. Cada piso es cuadrado, y tiene dos ladrillos más de cada lado que el piso superior.

Hay zigurates que son distintos entre sí, pero que usan la misma cantidad de ladrillos. Por ejemplo, el de una sola capa de lado 10 y el de dos capas de lados 8 y 6 usan ambos 100 ladrillos, y son los únicos que usan esta cantidad.

En general, indicaremos con la función Z(n) la cantidad de zigurates distintos que se pueden construir con n ladrillos. Ejemplos: Z(1) = 1, Z(2) = 0, Z(100) = 2.

La mayoría de los valores de Z son 0. Es trivial ver que hay infinitos Z(n) ≥ 1 (por ejemplo, los números cuadrados). Quizá es menos trivial ver que hay infinitos Z(n) = 2.

Conocemos algunos valores de Z iguales a 3 y 4. Es un buen ejercicio tratar de encontrarlos sin computadora. ¿Habrá infinitos?

Aún no encontramos valores mayores. ¿Existirán?

miércoles, 17 de septiembre de 2008

Buscando la libertad

Este es un juego que se me presentó hoy en sueños.

Dos damas de ajedrez están apresadas en el centro de un tablero lleno de peones que las vigilan.
Cada jugador comanda una de ellas. Se turnan para moverlas normalmente (comiendo peones o moviendo a casillas libres).
Gana el primero que logre que su dama logre la libertad. Esto puede entenderse de varias formas, dando lugar a distintas variantes del juego. Por ejemplo:
  • Para partidas cortas, la variante espacio personal: gana el jugador que logre mover su dama al centro de una zona de 3x3 casillas vacías.
  • Para partidas más largas, la variante libertad de movimientos: gana el jugador que logre colocar su dama en una posición tal que no esté vigilada por ningún peón, es decir, que no tenga ningún movimiento de captura.
¿Habrá estrategias simples para ambas variantes?

martes, 8 de julio de 2008

Árboles cuadriculados

El otro día me puse a dibujar árboles siguiendo las líneas de una hoja cuadriculada, como en la figura. (Básicamente, un árbol es un grafo conexo sin ciclos).

¿Cuántos árboles de N nodos se podrán dibujar? (Todas las intersecciones del cuadriculado usadas cuentan como nodos).

sábado, 5 de julio de 2008

Valor predictivo

El valor predictivo de un número natural es K si y sólo si sus primeros K dígitos no nulos "predicen" los demás. La predicción se hace multiplicándolos entre sí.

Por ejemplo:
  • El valor predictivo de 326, que denotaremos P(326), es 2, porque 3x2 = 6.
  • P(4320024) = 3, ya que 4x3x2 = 24.
Si no se puede hacer la predicción, el valor predictivo es nulo; por ejemplo, P(31) = 0.

La pregunta concreta es ¿cuántos números de valor predictivo nulo hay entre uno y un millón?

La pregunta más abstracta es ¿tendrá la serie P(n) alguna propiedad interesante?

martes, 17 de junio de 2008

Boggle cervantino

Hoy, una idea intrigante de Pablo Coll: ¿Cuál será el menor boggle donde entre el Quijote completo?

Precisemos: un boggle es un tablero cuadrado donde cada casilla contiene una letra. Buscamos el menor en el que se puedan ir leyendo todas las letras del Quijote, saltando de una letra a otra que esté vecina ortogonal o diagonalmente. A los efectos del problema ignoraremos acentos, signos de puntuación y mayúsculas (aunque bien podrían incluirse).

Desde ahí, Pablo generaliza algo temerariamente: imagina un Boggle de Babel, donde pueda leerse cualquier texto finito. ¿Existirá? ¿Qué tamaño tendría que tener?

lunes, 26 de mayo de 2008

Recorridos proporcionados

Tenemos un tablero de ajedrez infinito. Colocamos una dama, un rey, una torre, dos alfiles (uno en una casilla blanca y otro en una casilla negra) y un caballo, en seis casillas separadas de nuestra elección.

La misión es ir visitando todas las (infinitas) casillas restantes del tablero, de manera que todas las piezas visiten, en el límite, la misma proporción de casillas.

¿Podrá hacerse?

sábado, 3 de mayo de 2008

Otra variante del Tonga

Otra variante del Tonga, que no he probado contra otros jugadores aún pero pinta bien por algunas simulaciones que he hecho:

Juegan dos jugadores, sobre un tablero de ajedrez. Hay, a disposición de ambos, 32 fichas blancas y 32 fichas negras.

Los jugadores se turnan para colocar las fichas sobre casillas vacías. Cada jugador puede poner cualquier ficha, sea blanca o negra (siempre que queden fichas de ese color disponibles, claro).

Uno de los jugadores apunta a construir islas de fichas blancas; el otro, a construir islas de fichas negras. Las islas son grupos de fichas del mismo color, conectadas por los lados (como las cadenas del Go).

Cuando el tablero se llena, el que haya formado la isla más grande de su color gana la partida. Si hay empate, se desempata sucesivamente con islas más pequeñas.

Si alguien lo prueba, no deje de avisar.

martes, 15 de abril de 2008

Distribución de letras

Esta máquina de escribir antigua usaba, en lugar de teclado, un dial semicircular. Moviendo una aguja se señalaba la letra a escribir, y apretando un botón se imprimía dicha letra. Otro botón hacía mover el carro para poner los espacios.

No queda claro en el dibujo cuál era la distribución de las letras en el dial; por lo tanto podemos imaginar el siguiente problema:

Suponiendo que la aguja empieza en un extremo del dial, ¿Cómo deberíamos disponer las letras de manera que, al tipear el Quijote, la aguja recorra la menor distancia posible?

miércoles, 9 de abril de 2008

La taza inclinada

Este es un problema sacado del mundo real.

Mi amigo Javier tiene una cafetera, y tazas con forma de cono truncado. En la figura se ve la taza de perfil. Tanto la base como el fondo son círculos.

Cuando mi amigo quiere meter o sacar la taza de la cafetera, debe inclinarla un cierto ángulo. ¿Cuánto café puede servir, como máximo, para que al retirar la taza no se vuelque café? La parte sombreada de la figura representa el café cuando la taza está inclinada.

lunes, 7 de abril de 2008

Una variante del Tonga

El Tonga es un interesante juego de tablero creado por el Grupo de los lunes. Pruébenlo; es muy interesante.

He aquí una variante del juego, que probamos algunos de los miembros del grupo el otro día. Aún no tiene nombre, aunque se podría llamar Tonga Libre o algo por el estilo.

Juegan dos jugadores, sobre un tablero cuadriculado. Puede servir uno de ajedrez.

Uno de los jugadores apunta a construir islas de fichas blancas; el otro, a construir islas de fichas negras.

Las islas son grupos de fichas del mismo color, conectadas por los lados (como las cadenas del Go).

En cada turno, un jugador señala dos casillas, y el otro coloca en una de ellas una ficha blanca, y en la otra una ficha negra. En turnos sucesivos van intercambiando roles.
Otra manera de pensarlo es la siguiente: el jugador de turno coloca las dos fichas donde le plazca, y su oponente puede, si lo desea, intercambiarlas de lugar.

Cuando el tablero se llena, el que haya formado la isla más grande de su color correspondiente gana la partida. Si hay empate, se desempata sucesivamente con islas más pequeñas.

No hicimos muchas partidas, pero parece un juego interesante. Si alguien lo prueba y descubre alguna particularidad del juego, no deje de avisar.

martes, 26 de febrero de 2008

El puntaje, parte 2

Otro juego de preguntas y respuestas asigna puntaje al jugador de acuerdo a este sistema:

  • El puntaje inicial es de un punto.
  • Con cada respuesta correcta, el participante duplica su puntaje.
  • Con cada respuesta equivocada, el participante pierde un punto.
Tras una ronda de 20 preguntas, ¿Cuántos puntajes distintos puede obtener un jugador?

Y generalizando: ¿Cómo es la serie de cantidades de puntajes posibles en funcion de la cantidad de preguntas?

jueves, 31 de enero de 2008

El puntaje

Un juego de preguntas y respuestas asigna puntaje al jugador de acuerdo a este sistema:

  • El puntaje inicial es de cero puntos.
  • Con cada respuesta correcta, el participante suma un punto.
  • Con cada respuesta equivocada, su puntaje se divide por dos (se considera el puntaje como numero real, no necesariamente entero).
Tras una ronda de 20 preguntas, ¿Cuántos puntajes distintos puede obtener un jugador?

Y generalizando: ¿Cómo es la serie de cantidades de puntajes posibles en funcion de la cantidad de preguntas?