Hay una solución.
A pesar de mis dudas durante gran parte de este tiempo, esperando que la respuesta fuera que no se podía encontrar una solución sin pasar de 150, resulta que hay es una solución válida.
La solución que he encontrado es:
$$ 1,4,6,7,33,50,60,69,94,107,119,127,131,135,142,149 $$
He confirmado que las 120 sumas de dos valores son únicas. Tenga en cuenta que una segunda solución es la misma que esta, excepto con cada valor sustituido por 150 menos el valor.
El valor fue encontrado por mi código, después de tal vez 2 días de tiempo de ejecución. El código sigue funcionando, por lo que puede encontrar más soluciones.
Observaciones previas...
Para ayudar a buscar una respuesta a esto, he investigado las preguntas equivalentes para números más pequeños. En concreto, ¿cuál es el número más pequeño de $n$ enteros" que necesita para poder elegir $k$ enteros que satisfacen la condición. Para cada uno de los números presentados aquí, he utilizado código para confirmar que no se puede hacer con un rango de valores más pequeño.
En la tabla siguiente, el conjunto de soluciones son "hasta la inversión" - esto es porque, si se sustituyen todos los valores, $s$ en la solución con $n+1-s$ se obtiene otra solución, y así todas las soluciones vienen en pares equivalentes. Por ejemplo, $[1,2,3,5,8]$ y $[1,4,6,7,8]$ son idénticos, hasta la inversión.
$$\begin{array}{c|c|c} \hline\text{choose $k$ integers} & \text{from first $n$ integers} & \text{Solutions (up to reversal)} \\ \hline 5 & 8 & [1,2,3,5,8] \\ \hline 6 & 13 & \begin{array}{c}[1,2,3,5,8,13]\\ [1,2,3,7,10,13]\end{array} \\ \hline 7 & 19 & \begin{array}{c}[1,2,3,5,9,14,19]\\ [1,2,3,8,11,15,19]\end{array} \\ \hline 8 & 25 & [1,2,3,5,9,15,20,25] \\ \hline 9 & 35 & \begin{array}{c}[1,2,3,5,9,16,25,30,35]\\ [1,2,3,8,14,17,27,31,35]\\ [1,2,3,15,20,25,28,31,35]\end{array} \\ \hline 10 & 46 & [1,2,8,11,14,22,27,42,44,46] \\ \hline 11 & 58 & \begin{array}{c}[1,2,6,10,18,32,35,38,45,56,58]\\ [1,2,6,10,18,32,34,45,52,55,58]\end{array} \\ \hline 12 & 72 & \begin{array}{c}[1,2,3,8,13,23,38,41,55,64,68,72]\\ [1,2,12,19,22,37,42,56,64,68,70,72]\end{array} \\ \hline 13 & 87 & [1,2,12,18,22,35,43,58,61,73,80,85,87] \\ \hline 14 & 106 & \left[\begin{array}{c}1,2,7,15,28,45,55,67,\\70,86,95,102,104,106\end{array}\right] \\ \hline 15 & 127 & \left[\begin{array}{c}1,2,3,23,27,37,44,51,81,\\96,108,111,114,119,127\end{array}\right]\\ \hline \end{array}$$
Algunas ideas:
-
El aumento de $n$ necesario para aumentar $k$ por 1 parece crecer cada vez (con la única excepción de 13->19->25 - las diferencias entre $n$ los valores son 5,6,6,10,11,12,14,15,19 - esto no es demasiado sorprendente, pero vale la pena señalarlo.
-
La densidad de sumas dentro del rango posible puede calcularse con relativa facilidad. Hay $\frac{k(k-1)}2$ pares dentro del conjunto, y por lo tanto que muchas sumas si no hay dos iguales. Hay $2n-3$ posibles sumas creables a partir de un par de números entre $1$ y $n$ (ya que la suma no puede ser $1$ , $2$ o $2n$ ). Por lo tanto, la densidad viene dada por $\frac{k(k-1)}{2(2n-3)}$ - las densidades resultantes son (aproximadamente) 76,9%, 65,2%, 60,0%, 59,6%, 53,7%, 50,6%, 48,7%, 46,8%, 45,6% y 43,5%.
-
Todas las soluciones óptimas encontradas hasta ahora (teniendo en cuenta la inversión) pueden escribirse con $[1,2...$ al principio.
-
Curiosamente, aunque una solución para $k=15$ se puede encontrar con $n=127$ no se puede encontrar tal solución para $n=128$ si necesita tanto 1 como 128 en el conjunto.
Enfoques que he utilizado para tratar de encontrar soluciones:
-
Un código que busca la solución en un enfoque "aditivo" - encontrar qué valores se pueden añadir al conjunto existente que tienes, y seguir ampliando hasta que te quedes sin valores, entonces retroceder y probar un nuevo valor. Con una codificación cuidadosa para asegurar que se minimiza el espacio de búsqueda razonablemente bien, esto puede encontrar todas las soluciones óptimas para hasta $k=14$ en un tiempo razonable, si se introduce la información correcta $n$ en (y puede utilizarse de forma similar para confirmar que no hay ningún $n$ funcionará). Sin embargo, para las grandes $n$ se vuelve mucho más difícil de manejar.
-
Un código codicioso que busca la solución con un enfoque "sustractivo": empieza con todos los valores posibles en el mismo conjunto (es decir, del 1 al 150 para la pregunta real), luego elimina números basándose en los que reducen más el número de "colisiones" (sumas que aparecen varias veces), con cierta aleatoriedad cuando varios números pueden lograr la misma reducción... y luego vuelve a añadir números si no aumentan sustancialmente el número de colisiones. Esto puede encontrar muchas soluciones con bastante rapidez para los casos "fáciles", pero debido al aspecto aleatorio, también es bastante lento para encontrar los valores óptimos para los casos más grandes $n$ . Un enfoque no aleatorio es probable que sea muy, muy lento, ya que se empieza con un montón de números y hay un montón de opciones de eliminación.
-
Tome una solución más pequeña, como para $k=12$ ( $n=72$ ), luego se reescalan los números y se intentan rellenar los huecos. Por ejemplo, multiplicando el primer $k=12$ solución por 2 da $[2,4,6,16,26,46,76,82,110,128,136,144]$ . A partir de aquí, podemos encontrar que $[31,89,147]$ se puede añadir, para un total de $k=15$ ... pero a pesar de varios intentos, no he conseguido llegar a $k=16$ utilizando este enfoque.
