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?

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?

Diccionario trucado

Todos hemos jugado alguna vez a la búsqueda en el diccionario. Consiste en decirle una palabra al otro jugador, y que éste encuentre la página donde está la palabra mirando la menor cantidad posible de páginas.

La estrategia común consiste en una búsqueda binaria, ligeramente modificada para tener en cuenta las cantidades relativas de palabras que comienzan con cada letra.

Ahora bien, supongamos que podemos trucar un diccionario, duplicando a nuestro antojo cualquier página del diccionario cuantas veces querramos, pero siempre poniendo las copias donde deben ir.

¿Qué distribución de cantidades de página será la que haga más difícil para el oponente encontrar la palabra "ingenuo", por ejemplo?