Newsgroup: it.hobby.enigmi
Titolo: RCP Addittivi

Vorrei trovare sets di  n interi positivi,  in modo che le somme di un
qualunque subset da 2 fino ad n elementi, siano tutte differenti. Mi
spiego meglio, prendiamo n=4, allora per i 4 numeri (a,b,c,d) avremo 11
possibili somme:
 a+b, a+c, a+d, b+c, b+d, c+d, a+b+c, a+b+d, a+c+d, b+c+d, a+b+c+d .
Tutti i subset, sarebbero 16, ma per il nostro scopo l'insieme vuoto e
quelli con un solo elemento li ignoriamo. E' facile convincersi che con
n elementi si hanno n^2 subset,  basta pensare che ciascun elemento puo'
essere o non essere presente. Nel nostro caso avremo n^2-(n+1) somme da
verificare.
Perche' tutte le somme siano differenti, direte voi a questo punto, e'
sufficiente prendere le potenze di 2, come tutti sanno, sommando nei
vari modi 1,2,4,8 si ottengono tutti i naturali da 1 a 16. Quello che
chiedo e' che il numero piu' grande appartenente al set, sia il piu'
piccolo possibile. Per n=4  (3,5,6,7) e' gia' una sol. migliore dato che
7<8
e le varie somme:
3+5         =8
3+6         =9
3+7         =10
5+6         =11
5+7         =12
6+7         =13
3+5+6     =14
3+5+7     =15
3+6+7     =16
5+6+7     =18
3+5+6+7 =21
sono tutte differenti.
Cosa possiamo dire per n= 5,6,7,8.......?
:) dario

 Cosa possiamo dire per n= 5,6,7,8.......?
spoiler
.
.
.
.
.
.
.
.
.
Per ora ho una soluzione generale, sicuramente non quella ottimale, che
migliora, di poco, quella con le potenze di due
per un generico n
consideriamo le n-1 potenze di 2, con esponenti da 0 ad n-2
per esempio per n=5
1, 2, 4, 8
come hai già detto, considerando anche i subset di una cifra otteniamo tutti
i numeri da 1 a 2^(n-1)-1
nel nostro caso da 1 a 15
se, come ennesimo valore prendiamo 2^(n-1)-1 (nel nostro caso 15), e lo
sommiamo a qualunque subset precedente (compresi quelle di una sola cifra),
otteniamo sempre numeri diversi tra loro e maggiori del più grande del
precedente.
quindi
1 2 3
1 2 4 7
1 2 4 8 15
1 2 4 8 16 31
ecc.
in pratica scriviamo, per ogni n, potenze di due, e diminuiamo l'ultimo
valore di una unità
ciao
paolo

 Cosa possiamo dire per n= 5,6,7,8.......?
Per ora solo muscoli e poco cervello. Ecco la due migliori possibilità per
n=5
(1)  (a,b,c,d,e) = (3,6,11,12,13)
(2)  (a,b,c,d,e) = (6,9,11,12,13)
ed ecco le somme nei due casi
abcde  (1) (2)
---**  25  25
--*-*  24  24
--**-  23  23
--***  36  36
-*--*  19  22
-*-*-  18  21
-*-**  31  34
-**--  17  20
-**-*  30  33
-***-  29  32
-****  42  45
*---*  16  19
*--*-  15  18
*--**  28  31
*-*--  14  17
*-*-*  27  30
*-**-  26  29
*-***  39  42
**---   9  15
**--*  22  28
**-*-  21  27
**-**  34  40
***--  20  26
***-*  33  39
****-  32  38
*****  45  51
Ciao, Silv:o)

 (2)  (a,b,c,d,e) = (6,9,11,12,13)
Per n=6 la sestina è unica
(11,17,20,22,23,24)
Ancora nessun appiglio.
Silv:o)

 Cosa possiamo dire per n= 5,6,7,8.......?
Parto ancora dalle potenze di 2
1 2 4 8 16 32...
noto che
A) due diversi subset hanno sempre somme differenti
B) l'ultimo termine è maggiore della somma di tutti i precedenti
moltiplico tutti i termini per 3
3 6 12 24 48 96...
noto che valgono ancora le proprietà A) B), ed inoltre
C) tutti i termini sono multipli di 3, e quindi lo è anche qualsiasi somma
parziale
aggiungo altri due termini, incrementando l'ultimo rispettivamente di una o
due unità
3 6 12 24 48 96 97 98
D) i due termini aggiunti valgono rispettivamente 1 e 2 (mod 3)
confronto ora due qualsiasi subset
_ se nessuno dei due contiene i termini 97, 98, le due somme sono differenti
per la proprietà A)
_ se in uno solo dei subset è presente uno dei termini 97, 98, le due somme
hanno diverso resto (mod 3) per la proprietà D)
_ se i termini 97 e 98 sono presenti in subset diversi, le due somme hanno
ancora diverso resto (mod 3) per la proprietà D)
_ se i termini 97 e 98 sono presenti nello steso subset, questo è
sicuramente maggiore dell'altro; infatti dalla proprietà B) deriva il fatto
che 97+98 è maggiore della somma di tutti gli altri termini
quindi trovo i diversi set
3 4 5
3 6 7 8
3 6 12 13 14
3 6 12 24 25 26
3 6 12 24 48 49 50
3 6 12 24 48 96 97 98
ecc.
Per n=2 o n=3 le soluzioni non sono sicuramente quelle ottime
Per n=5 Silvio ha già trovato una soluzione migliore
Per n>5 non sono sicuro che il metodo descritto generi sempre i set
migliori, ma ho l'impressione che sia così, almeno da un certo n in avanti.
ciao
paolo

 D) i due termini aggiunti valgono rispettivamente 1 e 2 (mod 3)
mi pare che la cosa funzioni anche se i termini aggiuntivi si ottengono
dall'ultimo, rispettivamente aggiungendo e sottraendo una unità
3 6 12 24 48 96   97 95
nel caso n=6 verrebbe
3 6 12 23 24 25
però vedo anche questa è già stata superata da Silvio
forse il metodo va perfezionato
ciao
paolo

Ciao, Paolo,
La prima tua impressione č che
"Per n>5 non sono sicuro che il metodo descritto generi sempre i set
migliori, ma ho l'impressione che sia cosě, almeno da un certo n in avanti."
vediamo. I tuoi subset hanno come termine piů grande 3*2^(n-3)+1.
n  Paolo  min.(brute force)
4    7     7
5   13    13
6   25    24
7   49    44  (20,31,37,40,42,43,44)
e dell'ultima non sono sicuro sia la migliore, anche la brute force arranca
al crescere di n.
Quindi mi pare che si prospetti una divergenza. Comunque partendo dal
termine maggiore anziché dal piů piccolo posso trovare facilmente ottimi
locali. Non c'č la certezza che siano globali, ma possono servire per
verificare la discrepanza dal tuo metodo e per capire se l'andazzo č
esponenziale come il tuo oppure piů tranquillo. Stasera vedo di fare qualche
prova.
Ciao, Silv:o)

Nel nostro caso avremo n^2-(n+1) somme da verificare.
E' con profonda riverenza e timore che provo a correggere Dario Uri,
ma credo che il numero dei subset non sia n^2, ma 2^n. :-))
Credo inoltre che escludere i subset di un solo elemento sia inutile:
tutti gli insiemi trovati rispettano anche questo vincolo, quindi
tanto vale mantenerlo.
Confermo i valori trovati da Silvio e ci aggiungo alcuni altri:
 4 --> 3,5,6,7
 5 --> 6,9,11,12,13
 6 --> 11,17,20,22,23,24
 7 --> 20,31,37,40,42,43,44
 8 --> 40,60,71,77,80,82,83,84
 9 --> 77,117,137,148,154,157,159,160,161
10 --> 148,225,265,285,296,302,305,307,308,309
11 --> 285,433,510,550,570,581,587,590,592,593,594
12 --> 570,855,1003,1080,1120,1140,1151,1157,1160,1162,1163,1164
13 -->1120,1690,1975,2123,2200,2240,2260,2271,2277,2280,2282,2283,2284
14 -->2200,3320,3890,4175,4323,4400,4440,4460,4471,4477,4480,4482,
       4483,4484
Sono garantiti essere i minori di ogni gruppo fino ad N = 7, per i
successivi non sono sicuro che siano i minori (ma sono convinto che lo
siano) perche' li ho ottenuti rapidamnente con un trucco:
Fissato il caso N, si puo' notare che il caso N+1 si ottiene prendendo
come primo elemento uno degli elementi del caso N (inizialmente il
terzo, poi diventa il quarto poi il quinto), quindi gli altri elementi
si ottengono come somma di questo primo elemento e di quelli del caso
N in ordine.
Esempio:
il primo elemento del caso 5 e' uguale a 6 (terzo elemento del caso 4)
quindi gli elemti del caso 5 sono:
1 -> 6
2 -> 6+3 = 9
3 -> 6+5 =11
4 -> 6+6 =12
5 -> 6+7 =13
Qualcuno e' in grado di dare una dimostrazione? Per ora io non ho il
tempo di pensarci, me ne vado a dormire.
Ciao, Damiano  

 5 -> 6+7 =13
Ottimo!  mi sembra una grande osservazione. Utilizzando la tua procedura
in senso inverso,  posso scrivere tutto in forma compatta. Prendiamo la
sequenza:
1,2,3,5,8,14,25,45,.... Allora i numeri trovati da te e Silvio si ricavano
direttamente sottraendo i primi n termini dal termine   n+1.
Es. per n=5 sottraggo i primi 5 termini della serie (1,2,3,5,8),  dal
sesto (14) ottenendo proprio (6,9,11,12,13)
Non resta che trovare la regola che genera questa sequenza.  A questo
punto mi viene un dubbio..... Vado a consultare Sloane... aspetta li'.
5 minuti dopo.    No, non c'e'.
Ad una prima osservazione sembra che un termine puo' essere aggiunto solo
se NON genera la stessa somma con lo stesso numero di elementi. Mi spiego
meglio.
Una volta scritti i primi tre termini1,2,3 non posso aggiungere il num. 4
perche' 4+1=3+2. Il 5 invece va bene, e' vero che 1+2+3 = 1+5, ma le due
somme hanno un diverso numero di addendi.
Procedendo,  il 6 va eliminato difatti 6+1=5+2
                     il 7 va eliminato           7+1=5+3
                      l'8 va bene, e lo scrivo come quinto termine.
Mi sembra che ogni termine deve essere uguale o maggiore della somma dei
due precedenti, allora vediamo di trovare il nono termine che deve essere
=>70.
 70+1+2   = 45+25+3
 71+3+1   = 45+25+5
 72+1+2   = 45+25+5
 73+2+3   = 45+25+8
 74+1+3   = 45+25+8
 75+1+2   = 45+25+8
 76+3+5   = 45+25+14
 77+2+5   = 45+25+14
 78+1+5   = 45+25+14
 79+2+3   = 45+25+14
 80+1+3   = 45+25+14
 81+1+2   = 45+25+14
 82+2+3+5  = 45+25+14+8
 83+1+3+5  = 45+25+14+8
 84+1+2+5  = 45+25+14+8
Con 85 non si possono formare addizioni con la stessa somma e lo stesso
numero di addendi, percio' diventera'  il nono termine della nostra
sequenza.
Ora sottraendo 1,2,3,5,8,14,25,45 da 85 si ottiene la sol. per n=8:
 8---> 40,60,71,77,80,82,83,84.
Tenendo presente queste osservazioni, c'e' un modo piu' rapido per far
crescere la nostra sequenza ??
:) dario
.

 crescere la nostra sequenza ??
Combinando il tuo lavoro con quello di Damiano, si trova facilmente una
regola, anche se è difficile formalizzarla. In pratica ogni termine si
ottiene raddoppiando il precedente e togliendo uno dei termini precedenti,
sempre più *lontani* al crescere di n. La prima volta va tolto il termine
che sta una casella prima, poi per due volte quello che sta due caselle
prima, per tre volte quello che precede di tre posti e così via.
a_1=1
a_2=2
a_(n+1) = 2*a_n - a_(n-k_n)
dove k_n è una successione i cui termini sono
1,2,2,3,3,3,4,volte4,5volte5,...
a_1 =                 = 1
a_2 =                 = 2
a_3 = 2*a_2 - a_(2-1) = 2*a_2 - a_1 = 3
a_4 = 2*a_3 - a_(3-2) = 2*a_3 - a_1 = 5
a_5 = 2*a_4 - a_(4-2) = 2*a_4 - a_2 = 8
a_6 = 2*a_5 - a_(5-3) = 2*a_5 - a_2 = 14
a_7 = 2*a_6 - a_(6-3) = 2*a_6 - a_3 = 25
a_8 = 2*a_7 - a_(7-3) = 2*a_7 - a_4 = 45
a_9 = 2*a_8 - a_(8-4) = 2*a_8 - a_4 = 85
a10 = 2*a_9 - a_(9-4) = 2*a_9 - a_5 = 162
spero si capisca.
Ciao, Silv:o)

crescere la nostra sequenza ??
Regola sperimentale:
un nuovo numero si ottiene raddoppiando l'ultimo e sottraendo uno dei
numeri della sequenza. 
Esempio:
La sequenza e' 1,2,3,5,8,14,25,45,85,....
i vari numeri si ottengono:
2*2-1 = 3
2*3-1 = 5
2*5-2 = 8
2*8-2 = 14
2*14-3 = 25
2*25-5 = 45
2*45-5 = 85
i successivi sono:
2*85-8 = 162
2*162-14 = 310
2*310-25 = 595
2*595-25 = 1165
2*1165-45 = 2285
2*2285-85 = 4485
I numeri da sottrarre sono progressivi (ma con quale regola?), per cui
si riduce molto la ricerca: o e' quello usato nella formula precedente
oppure il successivo. Il prossimo numero della sequenza dovrebbere
essere:
2*4485-85 = 8885
oppure
2*4485-162 = 8808
da scegliere con la forza bruta. Si puo' fare di meglio?
-- 
Ciao, Damiano


vedo adesso il post di Silvio; mi sembra che la situazone si chiarisca
ulteriormente, ma credo sia difficile dare una formula 'esteticamente'
soddisfacente.
-- 
Ciao, Damiano

 a_(n+1) = 2*a_n - a_(n-k_n)
n   k
3   1
4   2
5   2
6   3
7   3
8   3
9   4
10  4
11  4
12  4
13  5
...
allora forse si puň rendere il tutto in forma piů compatta (o piů
incasinata?), ricorrendo ai numeri triangolari
j  T
1  1
2  1+2=3
3  1+2+3=6
4  1+2+3+4=10
...
dalla prima tabella (n,k) vediamo che k incrementa il suo valore quando n-3
č un numero triangolare, e precisamente se n-3 č il j_esimo triangolare,
allora k assume il valore j+1
per esempio
per n=6, n-3=3 č il secondo numero triangolare, k assume il valore 3
per n=13, n-3=10 č il quarto triangolare, k assume il valore 5
forse si potrebbe arrivare perfino ad una formula unica, ricorrendo alle
funzioni INT (parte intera), MOD, o qualcos'altro.
Qualcuno vuole provarci?
ciao
paolo

 ...
mi pare di aver fatto un po' di confusione: nella prima colonna ho riportato
i valori n+1 anzichč n.
Allora la colonna dovrebbe slittare verso il basso di una posizione, e il
discorso sui numeri triangolari dovrebbe essere riferito ad n-2 anziché ad
n-3
Uso il condizionale, perché non sono dicuro di non essere ancora confuso :-(
provate a verificare
ciao
paolo

Qualcuno vuole provarci?
Hai ragione non avevo notato che sono numeri triangolari. Si puo'
ottenere una formula unica ricorrendo alla funzione inversa dei numeri
triangolari:
OT(n) = int((isqrt(8*n+1)-1)/2) 
dove isqrt() e' la radice intera (radice quadrata+troncamento dei
decimali). Se n e' un numero triangolare, OT(n) e' il suo numero
d'ordine, se n non e' un numero triangolare OT(n) e' il numero
d'ordine del triangolare immediatamente inferiore a n. 
Esempio: per n = 6 -> OT(n) = 3, infatti 6 e' il terzo numero
triangolare, n = 12 -> OT = 4 che e' il numero d'ordine del
triangolare immediatamente inferiore a 12 (10).
La successione si genera quindi:
 a_1 = 1
 a_2 = 2
 a_3 = 3
 a_(n+1) = 2*a_n - a_(n-1-OT(n-2))
La formula non e' molto semplice, ma e' facilissima da implementare
con un linguaggio di programmazione (o con excel). La successione
risultante e'
1,2,3,5,8,14,25,45,85,162,310,595,.....
Spero di non vederla in qualche messaggio futuro accompagnata dalla
domanda: quale e' il prossimo termine della successione .... :-))))
Chissa' se e' possibile trovare una formula diretta, che non costringa
a riferirsi ad elementi precedenti della successione? Credo che sia
veramente dura.
-- 
Ciao, Damiano