Organice $\{1,2,\cdots,n\}$ en un círculo. ¿Cuáles son los arreglos que minimizan la suma máxima de todos los adyacentes $k$ ¿enteros? Algunos ejemplos no triviales de $(n,k)$ son bienvenidos. Un algoritmo aleatorio que dé un límite probabilístico sería genial.
Respuesta
¿Demasiados anuncios?
user384189
Puntos
1
No queremos que los dos números más grandes del conjunto: que son n y n-1 sean adyacentes entre sí: Se puede averiguar rápidamente el patrón de que el límite inferior de la suma máxima adyacente es n+2:
La pauta general es empezar con n -el número mayor- en la posición más alta y asegurarse de que n-1 no está al lado de n, y luego, si puedes, n-2 no está al lado ni de n ni de n-1 y n-3 no está al lado de ninguno de ellos y así sucesivamente. Los coloqué exactamente a 2 puntos de distancia en el sentido de las agujas del reloj (aunque podrías usar la convención de las agujas del reloj en su lugar).
