He pensado en utilizar el principio de la colombofilia, pero aparte de eso no estoy seguro de cómo resolverlo.
Respuestas
¿Demasiados anuncios?
DiGi
Puntos
1925
rajb245
Puntos
290
Más simplemente quizás:
Supongamos que no hay dos casas con números consecutivos. Si $L$ es el número de casa más bajo, entonces el segundo número de casa más bajo es al menos $L + 2$ el tercero más bajo es al menos $L + 4$ y así sucesivamente hasta el número de casa más alto de al menos
$$L + 30 \cdot 2 = L + 60$$
¡Ahora deriva una contradicción!
Jaseem Abbas
Puntos
130
No estoy seguro de que esta sea la respuesta que buscabas, pero es una de esas "tan dolorosamente sencillas que probablemente nunca te hayas planteado":
La calle Norte termina en un callejón sin salida.
Pero más allá de eso...
Si las casas están numeradas del 1 al 57 y NONE de ellos están numerados consecutivamente, todos deben tener números impar. Todos los números impar del 1 al 57 (inclusive) suman 29 números.
El problema cita 31 casas en un polígono en el que sólo caben 29 casas sin ninguna adyacente. 31-29 = 2, por lo que al menos dos de las casas deben ser adyacentes a otras para que se ajusten a los parámetros.
Aunque la pregunta citara 30 casas, al menos dos tendrían números adyacentes. Por ejemplo, si la casa número 30 tuviera el número 2, las casas 1, 2 y 3 tendrían números adyacentes.
ASCII Advocate
Puntos
1959
Hay un único subconjunto con el máximo número de casas no adyacentes: {1,3,5,...,57}. El número de casas (29) de este conjunto es inferior a 30.
Esta observación resuelve el problema, pero también indica que con 30 casas hay al menos 2 adyacencias. Con sólo 1 adyacencia $(i-1,i)$ podría añadir $+1$ a todos los números de la casa $\geq i$ y obtener un conjunto de números de casa entre 1 y 58 sin adyacencias, pero ahí también el tamaño máximo del conjunto es 29, no 30. Para tener 30 números no adyacentes tenemos que elegirlos de un intervalo de tamaño al menos 59.
Continuando con el argumento para el caso general, para tener $H$ casas con números distintos entre $1$ y $n$ y con $\leq k$ adyacencias, se necesita $(n+k) \leq 2H - 1.$ Esto es óptimo; la igualdad puede mantenerse, y de forma única.
