viernes, 22 de julio de 2016

Histogaritmos

Primero, la definición de histogaritmo (medio rebuscada pero luego de un rato se hace natural).

Supongamos que tenemos una lista no vacía de números. Por ejemplo:

L = [1, 1, 1, 2, 2, 3, 3, 3, 4] (ordenar la lista no es necesario, pero es práctico)

Calculamos su histograma H(L), que consiste en las cantidades de cada grupo de números iguales:

H(L) = [1, 2, 3, 3] (porque en L hay 1 cuatro, 2 dos, 3 unos y 3 treses)

y luego hacemos el histograma del resultado:

H^2(L) = [1, 1, 2]

y así siguiendo hasta que llegamos a un resultado con un solo elemento (en este caso, tras tres pasos más):

H^3(L) = [1, 2]

H^4(L) = [1, 1]

H^5(L) = [2]

Como iteramos 5 pasos para llegar a una lista unitaria, decimos que 5 es el histogaritmo de L.

Ahora, el problema:

Dado un natural N, ¿Cómo construir una lista de N elementos que tenga el mayor histogaritmo posible?


domingo, 22 de mayo de 2016

Dadivosidad

Este es un juego ralo con azar, con el que soñé anoche. Juegan dos jugadores, usando un dado común.
Uno de los jugadores toma el dado, lo arroja, y decide cuál de estas dos cosas hacer:
  • Anotarse los puntos que indica el dado y ceder el turno al otro jugador.
  • Anotarle al otro jugador los puntos que indica el dado, pero retener el turno.
Esto se repite una y otra vez (cambiando o no de turno, según las decisiones de los jugadores), hasta que uno de los jugadores llega a 50 puntos, y es declarado ganador.

¿Habrá una estrategia que maximice la probabilidad de ganar para el primero o segundo jugador?

El segmento monocromático

Demostrar o refutar lo siguiente:

De cualquier forma que pintemos el plano con dos colores, siempre habrá un segmento unitario cuyos puntos sean todos de un mismo color.

sábado, 10 de marzo de 2012

¿La versión original del Tonga?


He aquí una variante del Tonga que jugué hoy y encontré bastante buena. Es similar a las otras dos variantes que he mencionado pero más libre aún.
  • 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 su turno, cada jugador coloca dos fichas: una blanca y una negra, en dos casillas desocupadas del tablero.
  • 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 mi memoria no falla, fue esta la primera versión que sugirió Iván y que probamos con el Grupo de los Lunes, pero no puedo recordar si la descartamos por algún fallo serio (más allá de cierto problema de simetría que se puede arreglar fácilmente).


Si algún GrupoLunero lee esto agradeceré si me corrige o confirma.

sábado, 19 de noviembre de 2011

Dominando el tablero de ajedrez

Queremos dominar un tablero de ajedrez, esto es, cubrirlo con 32 fichas de dominó (como en tantos acertijos clásicos, cada ficha cubre exactamente dos casillas, en posición horizontal o vertical).
Hay muchísimas maneras de hacerlo; sin embargo, cada ficha que colocamos reduce la cantidad de maneras de colocar las siguientes.
La pregunta es: ¿Cuál es la cantidad mínima de fichas que hay que colocar en el tablero para que haya una única manera de colocar el resto de las fichas?
Aclaremos que consideramos a todas las fichas como si fueran indistinguibles; sólo nos interesa su posición relativa en el tablero.