sábado, 9 de noviembre de 2013

Segmentos sin cortar

Enunciado

Este problema es muy interesante.

Usa de forma bastante repetitiva una fórmula que nos dice cuántos segmentos se pueden trazar entre N puntos. Son, exactamente N*(N-1)/2, ya que cada uno de ellos lo podemos unir con todos los restantes, y así contaremos cada segmento dos veces, ya que tiene dos extremos cada segmento.

En realidad, si corta segmentos de los que se forman entre todos los puntos que hemos seleccionado, eso significa que esos 60 segmentos tienen un extremo a cada lado de la recta, y es suficiente decidir cuántos puntos hay en cada uno de los dos lados para contar cuántos segmentos no son cortados por la recta.

El caso más sencillo es que sólo haya un punto a un lado de la recta, por lo que habrá 60 exactamente al otro, pues la recta corta exactamente a 60 segmentos. Por lo tanto, no habrá más segmentos en el lado "solitario", pero habrá 60*59/2 = 1770 segmentos en el otro lado, así que habrá estos 1770 segmentos que no cortará la recta.

Otro caso diferente es que haya 2 puntos en el lado menos poblado, y entonces habrá 30 en el otro, evidentemente, ya que son 60 los segmentos que pasan entre ellos por la recta. Eso hará que haya un segmento en el lado de los 2 puntos, y 30*29/2 = 435 en el otro lado. En total, 436 segmentos que no cortan la recta.

En el tercer caso, habrá 3 y 20 puntos, y el número de segmentos que no cortan será 3 + 20*19/2 = 193.

En el cuarto, habrá 4 y 15 puntos, lo que lleva a 4*3/2 + 15*14/2 = 6 + 105 = 111 segmentos.

En el quinto caso, habrá 5 y 12 puntos respectivamente, lo que nos lleva a 5*4/2 + 12*11/2 = 10 + 66 = 76 segmentos que no cortan.

En el sexto caso, habrá 6 y 10 puntos respectivamente, de forma que hay 6*5/2 + 10*9/2 = 15 + 45 = 60 segmentos que no se cortan (casualmente, los mismos que sí que cortan).

Y ya no hay más casos, porque 7, 8 y 9 son números que no dividen a 60, por lo que no puede ser que esté esa cantidad de puntos a un lado, pues no conseguiremos 60 segmentos que pasen sobre la recta.

Por tanto, las respuestas posibles serían, como dice nuestro anónimo visitante, 60, 76, 111, 193, 436 y 1770.

No hay comentarios: