Negritas II

Hace unos dí­as, en un intercambio de ideas con Marcos a raí­z del acertijo "Negritas2 surgió la siguiente pregunta:

¿Cuál será la menor cantidad de negritas que se necesitan poner en un tablero de nxn para lograr que todas las palabras sean de diferente longitud?

Lamentablemente, al analizarlo un poco, resultó que no era un problema tan desafiante. La menor cantidad de negritas se obtiene tratando de que todas las palabras (o la mayorí­a de ellas) estén disjuntas (no se crucen). Con un par de ensayos se encuentra el patrón de colocación de las mismas en tableros mayores.

Por otra parte, si pedimos que todas las palabras se crucen y que el tablero no quede separado en dos o más partes, existe una solución trivial para todo tablero.

Tal vez quieran ensayar todo esto antes de seguir leyendo.

Mas interesante resultó lo siguiente:

Colocar negritas para que tanto las palabras horizontales como las verticales sean de distinta longitud.

Existen soluciones triviales (lo cual garantiza que el problema siempre tiene solución)

Esta disposición en "escalera" no nos da la solución óptima al problema. Puede lograrse con bastantes negritas menos.

Lo dicho entonces: Colocar la menor cantidad de negritas para lograr que las palabras horizontales y las verticales sean todas de distinta longitud.

Update: Releyendo los viejos números de la revista El Acertijo, descubro que este problema ya había sido publicado allí y su autor fue Jaime Poniachik. Ahora nunca podré saber si se me ocurrió a mi o si solo me había quedado en el subconsciente :-)
Cuando se publique la hoja con este acertijo, pondré el link correspondiente.