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?

Empaquetando círculos

Tenemos N círculos, cuyos radios van de 1 a N.
¿Cómo empaquetarlos de manera que quepan (sin solaparse) en el círculo más chico posible?

Update: Al parecer este problema se usó en este concurso hace tiempo.

Concurso de empaquetamiento de puntos

¿Cuán pequeño puede ser el mínimo círculo que circunde a N puntos, si los puntos tienen que tener coordenadas enteras y no repetir distancias entre ellos?

Tal es el tema del concurso de Al Zimmermann de esta temporada. En este sitio se puede leer las reglas, anotarse y comenzar a enviar soluciones.

Blanqueando el tablero

Tenemos un tablero de ajedrez, y lo vamos transformando con la siguiente mecánica.

En cada movida, elegiremos dos casillas cualesquiera del tablero; estas casillas definirán un cuadrilátero de casillas, a todas las cuales cambiaremos de color: de blanco a negro y de negro a blanco.

¿Cuántas movidas serán necesarias, como mínimo, para dejar todas las casillas blancas?

Boggle numérico

Queremos armar un Boggle donde se puedan leer los números del uno al millón (en notación decimal).

¿De qué tamaño deberá ser el tablero, como mínimo?

Rotando sumas

Tomemos un cuadrado de 3x3 lleno de dígitos y sumemos las filas como si fueran tres números de tres cifras:

 324
 553
 807
----
1684

Ahora giremos el cuadrado para obtener tres nuevas sumas:

 324    437    708    853
 553    250    355    052
 807    358    423    734
----   ----   ----   ----
1684   1045   1486   1639

El problema que propongo hoy es lograr cuatro sumas diferentes, pero lo más cercanas entre sí que podamos. Es decir, minimizar la diferencia entre la mayor y la menor de las sumas.

Ajedrez pacifista

En el ajedrez pacifista, las piezas no deben comer ni amenazar jamás una pieza ajena. El jugador que se ve forzado a amenazar una pieza ajena, pierde.

¿Cuál es la partida más breve posible de ajedrez pacifista?

(Aclaración: la última movida debe ser forzada.)

Maximizar las diferencias

El objetivo de este primer problema es ubicar los números del 1 al 15, sin repetirlos, en los círculos del diagrama, de manera que la suma de todas las diferencias absolutas entre números vecinos sea la máxima posible.

Una linda generalización sería encontrar el patrón para ubicar los números de 1 a N para cualquier diagrama basado en un número triangular N.