Sottoinsieme di somme uniche 100€ prize

[mathsolution]

Ciao a tutti!

per la soluzione di questo problema in modo smart (non soluzioni esponenziali in tempo o spazio) offro un premio di 100€!

Il problema è il seguente:

Selezionare un insieme di N numeri, per cui scelto un valore K a piacere (nessun vincolo su K), è possibile prendere K numeri dall'insieme creato (nota: se K>N posso selezionare più volte lo stesso numero) ottenendo per ogni selezione S', S'', S''', ... somme uniche se ovviamente S' != S'' != S''' ...

in pratica se fisso K=3

creo il mio set A = [1,2,3,4]

posso creare una selezione S' = [1 2 3] = sum(S') = 6
posso creare anche S'' = [1 1 4] = sum (S'') = 6

cioè per numeri diversi la somma non è unica!

Possibile risolvere questo problema, per cui dato N e K, restiture N numeri per cui selezionari K alla volta con ripetizioni le loro somme siano sempre uniche se i numeri contenuti sono diversi di almeno 1 elemento?

Grazie!!

CIAOO

[Pappappero]

Ovviamente se $N = 1,2$ qualunque soluzione funziona.

Dal momento che hai due parametri dovresti anche specificare quale e' il parametro per cui non ammetti "soluzioni esponenziali in tempo/spazio".

Inoltre dovresti specificare che tipo di numeri vuoi nel tuo insieme: solo numeri naturali? solo interi? sono ammessi irrazionali? sono ammessi complessi, quaternioni, ottonioni?

Infine, e cosa piu' importante, per il caso generale, non e' chiaro cosa scegli prima;

Nella prima parte sembra che per ogni $N$ vuoi un insieme $A_N$ di $N$ elementi per cui, dato un $K$ qualsiasi, i $K$-multiinsiemi di $A_N$ hanno tutte somme diverse.

Nella seconda parte fissi prima $K$, non citi $N$ e scegli $A_N$ con $4$ elementi (e scegli quell'$A_N$ come esempio che NON funziona?).

Nell'ultima parte sembra che l'insieme possa dipendere da $K$: fissi $N,K$ e scegli l'insieme in funzione di questi due parametri; $K$ diversi possono corrispondere a insiemi diversi? (sempre di cardinalita' $N$). Quest'ultimo caso e' piu' facile del primo; la soluzione in questo consiste semplicemente nello scegliere gli elementi di $A_N$ in modo che siano "troppo lontani" (in funzione di $K$) perche' ripetendone uno se ne possa ottenere un'alto dell'insieme.

Piu' precisamente, fissiamo $N,K$ e scegliamo il nostro insieme come i primi $N$ elementi della successione $a_1 = 0$, $a_n = K a_{n-1} +1$. E' possibile "migliorare" questa soluzione, ma prima di ragionarci vorrei un po' di risposte alle questioni sollevate sopra.