Sottoinsieme di somme uniche 100€ prize
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
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
Risposte
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.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo