Newsgroup: it.hobby.enigmi
Titolo: Somma da 1 a 100

Cerco un gruppo di interi tali che sommando esattamente 2 termini del
gruppo, non necessariamente differenti, posso ottenere tutti gli interi
da 1 a 100 almeno in un modo.
Ad es: {0,1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90}
1=0+1
2=0+2
3=1+2
4=2+2
....
97=7+90
98=8+90
99=9+90
100=10+90
E' possibile farlo con meno di 19 termini?
:) dario

 
...scusa Dario: solo positivi oppure anche negativi ?
CiaO,
Massimo

  solo positivi oppure anche negativi ?
L'idea era solo positivi, ma possiamo trattarli entrambi.
ciao :)dario

 E' possibile farlo con meno di 19 termini?
...cakkio !!!!
;-)
Sto problema me portero' in vacanza per tutto il mese e 
prometto di non rientrare senza la soluzione....
A prima vista mi viene di dire che non e' possibile, ma
conoscendo Dario sono sicuro che almeno una soluzione
con 18 esiste.
Una considerazione banale e quella di invertire il problema
chiedendosi quante somme diverse sono possibili con N numeri.
Tale valore mi risulta essere N*(N+1)/2 per cui il minimo
valore del gruppo cercato non sara' inferiore a 14.
CiaO,
Massimo

 Ad es: {0,1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90}
Se ti accontenti dei numeri da 1 a 99 e rimuovi il vincolo che il gruppo sia
composto da interi, si può trovare un gruppo di 18 termini così composto:
{.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 19.5, 29.5, 39.5, 49.5,
59.5, 69.5, 79.5, 89.5}
Beh, è meglio di niente... :)
Ciao
Giorgio

 composto da interi, si può trovare un gruppo di 18 termini
se proprio ci dobbiamo accontentare, facciamo 99 numeri, da 2 a 100,
utilizzando 18 interi
1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90
:-)
ciao
paolo

 
....ma allora c'e' il "trucco" ???
Ditemi come stanno le cose altrimenti sono costretto a portarmi
al mare anche il PC.....
;-))
CiaO,
Massimo

 al mare anche il PC.....
Ed io, se Dario non interviene in tempo, dovro' acquistare un portatile da
montagna.
:-)
ciao
paolo

 
Ecco a cosa sono arrivato al momento:
Da 1 a 20 con  7 numeri = 0 , 1 , 2 , 5 , 8 , 9 , 10 
Da 1 a 26 con  8 numeri = 0 , 1 , 2 , 5 , 8 , 11 , 12 , 13 
Da 1 a 32 con  9 numeri = 0 , 1 , 2 , 5 , 8 , 11 , 14 , 15  16 
Da 1 a 38 con 10 numeri = 0 , 1 , 2 , 3 , 7 , 11 , 15 , 17 , 18 , 20 
Questi sono i limiti inferiori varificati in modo "bruto".
Speriamo in un intervento di Dario.....
;-)
CiaO,
Massimo

 Speriamo in un intervento di Dario.....
Ci sono parecchie soluzioni con 18 termini, e 5 con solo 17, con una di
queste si arriva fino a 104.
In tutte le sol. in 17 non compare il 2.
E' una variante dell'RCP (vi ricordate) non credo ci siano metodi al di
fuori della forza bruta.
Eventualmente fra qualche giorno metto le sol.
:) dario

 In tutte le sol. in 17 non compare il 2.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Togliendo il 2 trovo facilmente una delle soluzioni in 18:
0,1,3,4,5,6,7,8,9,12,22,32,42,52,62,72,82,92
non dispero di trovare una delle soluzioni in 17 a breve, e stavolta senza
programmi! (vabbč, con un lieve fogliettino elettronico, ma solo per
controllare i numeri che non copro con il tentativo in corso ;)
Ciao, Silv:o)
Ciao, Silv:o)

 fuori della forza bruta.
RCP ? Cosa era ? Magari possiamo parlarne a settembre.....
;-)
CiaO e buone vacanze a tutti.
Massimo

Ciao a tutti!
dopo aver a lungo lurkato il newsgroup, invio la mia prima soluzione
ad un problema, approfittando delle vacanze di molti solutori,
generalmente velocissimi..
S
.
.
P
.
.
O
.
.
I
.
.
L
.
.
E
.
.
R
.
.
ecco quello che ho trovato dopo ore e ore..
0 1 3 4 9 11 16 20 25 30 34 39 41 46 47 49 50
sapendo che non viene usato il 2, obbligatoriamente i primi tre numeri
sono 0 1 3, poi osservo che un numero entro i primi 50 ha una utilita'
maggiore perche' raddoppiandosi rientra a formare un numero utile,
percio' sono partito da 50 ed ho proceduto a ritroso aggiungendo il 49
e il 47 e cosi' via procedendo cercando di ottenere le somme dal lato
vicino allo zero e vicino al 100. Insomma un sacco di tentativi!!
Alla fine la soluzione trovata presenta una bella simmetria centrata
sul 25.
Qualcuno ha scritto un programmino per una ricerca esaustiva?
Riciao a tutti!
Mario Orlandini
 

 generalmente velocissimi..
Gran debutto!
... gli assenti hanno sempre ragione, ma questo era un problemillo tosto,
altro che ferie ;)
Mi stavo accingendo a provare un approccio esaustivo, ora m'hai tolto un po'
d'entusismo.
Se non m'impiccio troppo nelle prime fasi e trovo un algoritmo che poti di
brutto, il tentativo lo fo lo stesso.
Ciao, e di nuovo complimenti e benvenuto, Silv:o)


Il programmino l'ho scritto e, nonostante contenga un criterio per il taglio
di rami non utili alla ricerca delle soluzioni, non fa ben sperare in un
tempo di risposta breve riguardo ai 17 termini.
Comunque vi elenco quello che ho trovato (spero di non avere fatto troppi
errori di trascrizione) (i tempi di elaborazione sono riferiti ad un Pentium
II-333):
confermo quanto detto da Massimo per i termini fino a 9.
con 4 termini si arriva fino a 8 in 1 modo:
0 1 3 4
con 5 termini si arriva fino a 12 in 1 modo:
0 1 3 5 6
con 6 termini si arriva fino a 16 in 1 modo:
0 1 3 5 7 8
con 7 termini si arriva fino a 20 in 5 modi:
0 1 2 5 8 9 10
0 1 3 4 8 9 11
0 1 3 4 9 11 16
0 1 3 5 6 13 14
0 1 3 5 7 9 10
con 8 termini si arriva fino a 26 in 3 modi:
0 1 2 5 8 11 12 13
0 1 3 4 9 10 12 13
0 1 3 5 7 8 17 18
con 9 termini si arriva fino a 32 in 2 modi:
0 1 2 5 8 11 14 15 16
0 1 3 5 7 9 10 21 22
con 10 termini si arriva fino a 40 in 1 modo (tempo di elaborazione 1"):
0 1 3 4 9 11 16 17 19 20
con 11 termini si arriva fino a 46 in 2 modi (tempo di elaborazione 7"):
0 1 2 3 7 11 15 19 21 22 34
0 1 2 5 7 11 15 19 21 22 24
con 12 termini si arriva fino a 54 in 4 modi (tempo di elaborazione 66"):
0 1 2 3 7 11 15 19 23 25 26 28
0 1 2 5 7 11 15 19 23 25 26 28
0 1 3 4 9 11 16 18 23 24 26 27
0 1 3 5 6 13 14 21 22 24 26 27
con 13 termini si arriva fino a 64 in 1 modo (tempo di elaborazione 11'):
0 1 3 4 9 11 16 21 23 28 29 31 32
Sto provando con 14 termini e mi aspetto un tempo di elaborazione di poco
meno di 2 ore e se è vero che i tempi si moltiplicano per 10 per ogni
termine aggiunto, la ricerca esaustiva con 17 termini impiegherebbe circa 75
giorni!
E' vero che l'indizio dato da Dario sull'assenza del numero 2 limita la
ricerca (su 16 possibili inizi con 5 termini, solo 6 cominciano con 0, 1,
3...) però siamo sempre su un tempo di un mesetto circa!
Ho verificato che la soluzione di Mario (complimenti!) è l'unica che inizia
con 0 1 3 4 9 11 16...
Ciao
Giorgio

Prima rettifica:
Le configurazioni possibili dei primi 5 termini sono 17 (non 16) e, di
queste, 7 non contengono il 2.
Seconda rettifica:
La prima soluzione con 11 termini č:
0 1 2 3 7 11 15 19 21 22 24 (non 34)
In 103' il mio programma ha determinato che con 14 termini si ottengono i
numeri fino a 72 in un solo modo:
0 1 3 4 9 11 16 20 25 27 32 33 35 36
A questo punto la stima del tempo per i 17 termini č "scesa" a circa 60
giorni! :)
Ciao
Giorgio

Giorgio Vecchi ha scritto....
Mario Orlandini ha scritto...
Sergio Silvio ha scritto...
Che gusto riuscire ad attivare tutti sti' cervelli !!
Mario, a quanto mi risulta sei l'unica persona al mondo ad aver trovato
una sol. in 17 termini a mano.
Visto che ci frequentiamo da un po' di anni, e so chi sei, non mi
meraviglio piu' di tanto, ma l'impresa e' notevole.
ciao :) dario

 3...) però siamo sempre su un tempo di un mesetto circa!
Utilizzando anche l'altro suggerimento di Dario (maxSum = 104) ho limitato
gli addendi a 52.
In dieci minuti ha trovato la soluzione di Mario, in mezz'ora ancora non è
uscito dalla sequenza 0 1 3 4 9 11 16...
che come ha già detto Giorgio porta soltanto alla soluzione di Mario.
Appena sento il beep delle altre soluzioni vi faccio sapere.
Ciao, Silv:o)