El problema del huerto

Con respecto a los indigestos n¨²meros McNugget de la semana pasada, he aqu¨ª lo que dice nuestro comentarista habitual Salva Fuster:

¡°Los n¨²meros McNugget de 6, 9 y 20 son: 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 y 43, es decir, un total de veintid¨®s n¨²meros, siendo el 43 el mayor de ellos que no se puede conseguir.

Los n¨²meros McNugget de 4, 6 y 9 son los seis siguientes: 1, 2, 3, 5, 7 y 11. En este caso el n¨²mero de Frobenius-McNugget ser¨ªa el 11.

Una forma sencilla de ver los n¨²meros que no se pueden obtener como combinaci¨®n de 4, 6 y 9 es la siguiente:

Con 4 y 6 podemos obtener cualquier n¨²mero par mayor que 4.

Por otra parte, sumando 9 a cualquier par mayor o igual que 4, obtendremos cualquier impar mayor o igual que 13.

No podremos hacer los impares menores que 13, salvo el propio 9, ni tampoco podremos hacer el 2, de modo que la lista de los no conseguibles es: 1, 2, 3, 5, 7, 11¡å.

Otro comentarista habitual, Manuel Amor¨®s, plantea el acertijo siguiente:

En una urna hay 100 c¨¢psulas id¨¦nticas, una de las cuales contiene un premio.

a) Un amigo y t¨² vais sacando alternativamente las c¨¢psulas, una a una, y las abr¨ªs hasta dar con la premiada. Para maximizar tus probabilidades de obtener el premio, ?te conviene sacar en primer o en segundo lugar?

b) Misma cuesti¨®n, pero ahora las c¨¢psulas vac¨ªas no se descartan, sino que se vuelven a meter en la urna y se mezclan con las dem¨¢s.

Un sutil acertijo de aspecto inofensivo que suscit¨® interesantes comentarios y que me da pie a plantear una metapregunta algo capciosa: sin conocer ni buscar las respuestas a y b, ?podemos asegurar que ser¨¢n diferentes?

Y un tercer comentarista asiduo (esta semana la secci¨®n la han hecho los lectores, benditos sean), Juan Jos¨¦ Rodr¨ªguez, relacion¨® sagazmente a Frobenius con el matem¨¢tico brit¨¢nico James Joseph Sylvester, que introdujo t¨¦rminos tan b¨¢sicos como ¡°matriz¡± o ¡°discriminante¡±, y que es conocido sobre todo por sus aportaciones a la geometr¨ªa discreta.

El problema de la plantaci¨®n de ¨¢rboles

Uno de los problemas de geometr¨ªa discreta abordados por Sylvester es el denominado ¡°problema del huerto¡± o ¡°problema de la plantaci¨®n¡±, que debe su nombre a que, en la pr¨¢ctica, se plantea este tipo de problemas cuando se desea plantar ¨¢rboles de forma que se alineen de una determinada manera. En concreto, se trata de hallar el m¨¢ximo n¨²mero de alineaciones rectil¨ªneas de 3 puntos que se pueden formar situando n puntos en el plano.

Es evidente que con 3 puntos solo se puede formar una fila de 3, y con 4 puntos tambi¨¦n, pues no hay manera de colocar el cuarto punto para formar una nueva fila de 3. ?Y con 5, 6, 7¡­ puntos? ?Hay alguna relaci¨®n sencilla entre el n¨²mero de puntos y el m¨¢ximo n¨²mero de filas de 3 puntos que se pueden formar con ellos?

En la figura vemos una elegante configuraci¨®n de 9 puntos con 10 alineaciones de 3 puntos. ?Se puede mejorar?

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.