Newsgroup: it.hobby.enigmi
Titolo: minimo metro progressivo

Chiamiamo Metro Progressivo di ordine n un metro da muratore le cui
stecche - completamente prive di gradazione interne - siano lunghe 1,2,..,n
Ovviamente per misurare una distanza n, l'MP_n con la sua ultima stecca fa
al caso nostro. Ma si puo` quasi sempre fare meglio, ad esempio 12 si misura
con l'MP_5 (3+4+5). Per quali n non e` possibile usare qualcosa di piu`
comodo dell'MP_n?
Ciao, Silv:o)

 wrote:
: Chiamiamo Metro Progressivo di ordine n un metro da muratore le cui

SPOILER:
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 
Prendendo le successioni di lunghezza 2,3,4,5... otteniamo che i numeri
"buoni" sono rispettivamente quelli della forma
2k+1, k>=1
3k,   k>=2
4k+2, k>=2
5k,   k>=3
6k+3, k>=3
....
e qualche rapido conto mi fa immaginare che solo le potenze di 2 non siano
esprimibili in questo modo.
RISPOILER
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 
E` facile vedere che se n=2^k non e` possibile esprimere n come la somma di
h interi consecutivi, con h>1. Infatti, se h fosse pari la somma dei valori
sarebbe un numero dispari, e se h fosse dispari la somma dei valori sarebbe
uguale ad h volte il valore centrale, e quindi non potrebbe essere una
potenza di 2.
Abbiamo appena visto sopra che se n e` dispari e cioe` 2k+1 lo possiamo
esprimere come k+(k+1). 
Ora, se abbiamo un n esprimibile come 
   (a-(k-1))+(a-(k-2)+...+(a-1)+a+(a+1)+...+(a+k)
cioe` con un numero di termini pari, allora 2n sara` esprimibile come 
   (a-(2k-1))+(a-(2k-2)+...+(a-1)+a+(a+1)+...+(a+2k)
(esempio: 30 = 6+7+8+9, quindi a=7 e k=2; 60 = 4+5+6+7+8+9+10+11).
Questo andrebbe quasi bene per terminare l'induzione, se non fosse che k
potrebbe diventare cosi` grande da darci numeri negativi nella somma
finale.
Per terminare la dimostrazione, mi serve quindi far vedere che possiamo
sempre trovare una soluzione con un numero di addendi abbastanza piccolo.
Al momento non mi viene in mente nulla, pero`.
ciao, .mau.

 6k+3, k>=3
Se ho ben capito il quesito e la tua risposta, deve esserci qualcosa che non
va :-))
Ho fatto la verifica con una lunghezza pari a 5 che, secondo i tuoi calcoli,
dovrebbe richiedere un MP_5.
In realta' un MP_3 va benissimo
Ciao
Arturo

 wrote:
: > Prendendo le successioni di lunghezza 2,3,4,5... otteniamo che i numeri
: > "buoni" sono rispettivamente quelli della forma
: >
: > 2k+1, k>=1
: > 3k,   k>=2
: > 4k+2, k>=2
: > 5k,   k>=3
: > 6k+3, k>=3
: 
: Se ho ben capito il quesito e la tua risposta, deve esserci qualcosa che non
: va :-))
: Ho fatto la verifica con una lunghezza pari a 5 che, secondo i tuoi calcoli,
: dovrebbe richiedere un MP_5.
: In realta' un MP_3 va benissimo
Infatti 5 = 2*k+1 con k=2, e quindi e` nella mia lista.
ciao, .mau.


Perdonami, ma continuo a non capire bene, in quanto ho difficolta' a
decifrare il significato di *numeri buoni*.
Visto che le distanze esprimibili con un numero presente nella lista possono
essere misurate con un MP "piccolo",
provo a confutare la soluzione con un numero non presente nella lista.
La distanza 8 puo' essere misurata con un MP_6 con le stecche 5 e 2
ripiegate.
Ma forse c'e' ancora qualcosa che non ho compreso :-?)
ciao
Arturo

 wrote:
: Perdonami, ma continuo a non capire bene, in quanto ho difficolta' a
: decifrare il significato di *numeri buoni*.
: Visto che le distanze esprimibili con un numero presente nella lista possono
: essere misurate con un MP "piccolo",
: provo a confutare la soluzione con un numero non presente nella lista.
: 
: La distanza 8 puo' essere misurata con un MP_6 con le stecche 5 e 2
: ripiegate.
: 
: Ma forse c'e' ancora qualcosa che non ho compreso :-?)
Qua posso non avere compreso io.
Il mio modello dice che le stecche sono di lunghezza 1,2,3,4,5,6,...,n
e io posso piegare solo le stecche iniziali e finali, trovando una stringa
della forma a,(a+1),...b .
Secondo il tuo modello, se ripieghi la 2 e la 5 ottieni 1-2+3+4-5+6 che
pero` fa 7... a meno che non butti via la parte a sinistra dell'inizio.
Qua bisogna chiedere lumi a chi il quesito l'ha proposto.
ciao, .mau.

 pero` fa 7... a meno che non butti via la parte a sinistra dell'inizio.
Prova ad aiutarmi con un disegno:
            1xxxxT
            xxxx2
             xxxx
          3xx
          xx
            I
- I e T sono rispettivamente l'ģinizio e la fine del metro
- ogni riga rappresenta una stecca
- i numeri indicano il punto in cui la stecca piu' piccola fa perno
6-5+4+3
Mi sembra che i conti tornino :-)
ciao
Arturo

 wrote:
: * Chiamiamo Metro Progressivo di ordine n un metro da muratore le cui
:   stecche - completamente prive di gradazione interne - siano lunghe
: 1,2,..,n *
: > Secondo il tuo modello, se ripieghi la 2 e la 5 ottieni 1-2+3+4-5+6 che
: > pero` fa 7... a meno che non butti via la parte a sinistra dell'inizio.
: 
: Prova ad aiutarmi con un disegno:
: 
:             1xxxxT
:             xxxx2
:              xxxx
:           3xx
:           xx
:             I
quindi hai piegato la 3, la 5 e la 6, non la 2 e la 5. Per quello che non
mi tornavano i conti.
A questo punto mi chiedo se una soluzione 
     I
     22
       33T
che dall'inizio di I alla fine di T conta quattro unita`, sia valida :-)
cioa, .mau.
: - I e T sono rispettivamente l'ģinizio e la fine del metro

: 
: 

 La definizione mi sembrava chiara
Io direi "chiaramente ambigua"
Avevo pensato solo a stringhe del tipo x,x+1,..,x+k, ma questa tua
interpretazione mi pare interessante. Ci pensero`
Silv:o)

"Silvio Sergio" ha scritto

spoiler
v
v
v
v
v
v
v
Si tratta di vedere quali numeri possano essere espressi comme somma di una
progressione aritmetica
A mano trovo facilmente:
3 = 1+2
5 = 2+3
6 = 1+2+3
7 = 3+4
9 = 4+5
10 = 1+2+3+4
11 = 5+6
12 = 3+4+5
13 = 6+7
14 = 2+3+4+5
15 = 1+2+3+4+5
17 = 8+9
eccetera
Mancano all'appello i numeri 1, 2, 4, 8, 16,... quindi penso naturalmente
alle potenze di 2.
A questo punto cerco una spiegazione.
Per i numeri dispari n (diversi da 1), si vede immediatamente che possono
essere espressi come
(n/2-1/2)+(n/2-1/2)
esempio
7 = (3.5-0.5) + (3.5+0.5) = 3+4
I numeri pari n che non siano potenze di 2 hanno almeno un fattore dispari,
quindi possono essere espressi almeno in un modo nella forma
n = p*d
con p pari e d dispari
distinguo i due casi (p>d/2), (p<d/2)
se p>d/2, scompongo n come somma di termini p ripetuti d volte;
esempio
28 = 7*4 = 4+4+4+4+4+4+4
quindi, partendo dal termine centrale, che lascio invariato, andando verso
sinistra decremento i termini di 1,2,3,..., e verso destra li incremento
delle stesse quantità
(4-3), (4-2), (4-1), (4), (4+1), (4+2), (4+3)
ottenendo la progressione aritmentica
1,2,3,4,5,6,7
se p<d/2, scompongo n comme somma di termini d/2 ripetuti 2*p volte
eempio
44 = 4*11 = 5.5 + 5.5 + 5.5 + 5.5 + 5.5 + 5.5 + 5.5 + 5.5
poi incremento meta' dei termini di 0.5, 1.5,.. e decremento l'altra meta'
delle stesse quantita'
5.5+3.5, 5.5+2.5, 5.5+1.5, 5.5+0.5, 5.5-0.5, 5.5-1.5, 5.5-2.5, 5.5-3.5
ottenendo la progressione
9,8,7,6,5,4,3,2
ciao
paolo

 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Per le potenze di 2.
Prima di tutto bisogna dire che a parte le potenze di 2 ogni altro numero è
ottenibile con un opportuno numero di stecche consecutive.
Con un numero dispari D > 1 di stecche consecutive o ottengo un numero
dispari (2,3,4 = 9) o un numero pari multiplo di D (3,4,5 = 12) e quindi non
potenza di 2.
Con un numero pari di stecche consecutive ottengo un multiplo di un numero
dispari (2,3,4,5 = 14).
Adesso si tratta di dimostrare che ogni n non potenza di 2 è ottenibile con
le opportune stecche di MP_n.
Ogni n dispari è ottenibile con due stecche di metro consecutive "a cavallo"
di n/2.Es. 9 si ottiene con 4 e 5.
Ogni n pari non potenza di 2 è dato dal prodotto di un numero pari P per un
numero dispari D > 1, quindi si può ottenere o prendendo 2P stecche di metro
a cavallo di n/(2P) oppure D stecche di metro centrate in P. Dico "si può"
perché in alcuni casi non c'è abbastanza metro per poterlo fare. Mi spiego.
Nel caso n = 14, P è 2 e D è 7. Si possono usare 4 (2P) stecche a cavallo
del 3.5 (n/(2P)) e cioè 2,3,4,5 ma non si possono usare 7 stecche centrate
sul 2 (-1,0,1,2,3,4,5) - che peraltro fornisce il valore giusto -, perché se
già è difficile reperire il Metro Progressivo da un normale ferramenta,
penso che quello con le stecche di lunghezza negativa sia proprio
introvabile! :) Tra l'altro, per inciso, con quest'ultimo metro si
otterrebbero anche le potenze di 2.
Si può dimostrare che, per ogni coppia (P, D), almeno in uno dei due casi
non si esce dal metro. Nel primo caso D/2 deve essere > P, nel secondo caso
P deve essere > D/2, quindi o è vera l'una o è vera l'altra.
Adesso rilancio io. Troviamo un criterio per determinare il Metro più corto
per ottenere n.
Ciao
Giorgio

 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



"Silvio Sergio" ha scritto

spoiler


...

Spoiler
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
Per tutte e sole le potenze di 2.
In pratica vogliamo esprimere n come somma di numeri consecutivi, allora un
numero che non sia potenza di due ha senz'altro un divisore dispari k,
perciò si può scrivere come somma dei k numeri la cui mediana è n/k.
Una potenza di 2 non si può scrivere come somma di consecutivi perché la
generica somma da a a b varrebbe
(a+b)(b-a+1)/2 dato che una delle due parentesi è sempre dispari è
necessario che n abbia un fattore dispari.
Ciao
Andrea

"Silvio Sergio" ha scritto

spoiler


 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



 wrote in message
8pilg4$d2s1e$1...@ID-49224.news.cis.dfn.de...



"Silvio Sergio" ha scritto

spoiler


 per ottenere n.
Non sapendo come cominciare, come spesso faccio in questi casi mi
costruisco una tabellina dei risultati ottenibili.
1) 01    02    03    04    05    06    07    08    09    10    11...
2)    03    05    07    09    11    13    15    17    19    21...
3)       06    09    12    15    18    21    24    27    30...
4)          10    14    18    22    26    30    34    38...
5)             15    20    25    30    35    40    45...
6)                21    27    33    39    45    51...
7)                   28    35    42    49    56...
ecc.
1) = valori ottenibili utilizzando 1 stecca.
2) =   "        "            "     2   "
3) =   "        "            "     3   " ecc.
Possiamo ore fare alcune osservazioni.
La prima e' che tutti i num.primi appaiono nella riga 2) sono percio'
esprimibili solo con n+(n+1).
Es. il 21 appare 3 volte:
Come somma di 2 numeri 10+11
Come somma di 3 numeri 6+7+8
Come somma di 6 numeri 1+2+3+4+5+6
Evidentemente per avere il metro piu' corto per un dato n, dobbiamo
trovare l'n piu' in basso possibile nella nostra tabella.
L'ennesima riga comincia con l'ennesimo triangolare Tn, e tutti i numeri
alla sua destra si incrementano di una quantita' n, sono percio' del
tipo Tn+kn (k un intero qualunque).
Con queste semplici osservazioni ho gia' un criterio per trovare il
metro piu' corto.
Prendo ad es n=33
Per cercare il 33 piu' basso possibile, procedo dal fondo.
Dato che l'ottavo triangolare 8*9/2 e'> 33, 33 puo' stare al massimo
nella riga 7, dove troveremo 
T7 = 7*8/2 = 28 e tutti i 28+k7, ma 33-28=5 che non e' divisibile per 7.
Passo alla riga 6. T6=6*7/2 = 21. 33-21=12 che e'= 6*2 cosi' il nostro
33 lo troveremo come secondo numero dopo il 21, come dire che e' uguale
alla somma della terza sestina di numeri cioe':
3+4+5+6+7+8 = 33.
A questo punto abbiamo capito il metodo.
Qual e' il metro piu' corto per misurare 1000?
Trovo il maggior triangolare <1000, T44 = 44*45/2 = 990
 
Cerco nella riga 44) 1000-990 = 10 (non e' divisibile per 44
Cerco nella riga 43) 1000-946 = 54    "  43
.......
 
Cerco nella riga 25) 1000-325 = 675   675/25 = 27
Allora 1000 e' ottenibile come somma di 25 numeri consecutivi cominciano
dal 28
28+29+30+.....+51+52 = 1000
:) dario


Bello il tuo sistema "tabellare"!
Questo è il mio metodo: sfruttando l'analisi dei divisori pari e dispari del
mio messaggio precedente (o meglio di uno dei 9 (!) miei messaggi precedenti
(mannaggia al news server TIN!)), si possono trovare tutte le coppie di
divisori (uno pari e uno dispari > 1) di n. Nel caso 1000 sono:
1) 5, 200
2) 8, 125
3) 25, 40
Di queste o posso utilizzare D stecche centrate su P o 2P stecche a cavallo
di D/2, a seconda che sia D/2 < P o D/2 > P.
In tutti i casi il valore dell'ultima stecca è: (D-1)/2+P, che è proprio il
valore da minimizzare.
1) 5/2 < 200, 5 stecche centrate su 200
2) 125/2 > 8, 16 stecche a cavallo di 62.5
3) 25/2 < 40, 25 stecche centrate su 40
1) (D-1)/2+P = 202
2) (D-1)/2+P = 70
3) (D-1)/2+P = 52
Con 3) ottengo il metro più corto, che naturalmente coincide col tuo.
Nel caso dei numeri primi > 2, il metro più corto è lungo (n+1)/2.
Ciao
Giorgio
P.S. Nel mio precedente messaggio mi è "scappato" detto che con un metro
negativo si ottengono le potenze di 2. Non è vero, a patto che non usiamo un
metro (-1, 0, 1, 2) per ottenere 2, cosa che però otteniamo con un normale
metro MP_2 e che comunque non risolve il problema dato! Mi è proprio
scappato, ma forse nessuno se ne era accorto e potevo fare finta di niente!
:-)


Secondo la mia originaria interpretazione, era possibile utilizzare un MP
ripiegando anche le stecche interne.
Poi mi sono accorto che in molti casi e' vantaggioso piegare ad U il metro.
Con queste regole e' possibile utilizzare quasi sempre un MP "piccolo" per
misurare una distanza D.
Se i miei conti sono esatti, l'unica eccezione (oltre al caso particolare 1)
e' la distanza 4, per la quale deve essere utilizzato necessariamente un
MP_4 o superiore.
Ciao
Arturo


E poi ci sono i numeri dispari non primi. In questi casi si trovano tutte le
coppie (A,B) di divisori (naturalmente dispari), e tra queste si sceglie
quella che minimizza la formula A+(B-1)/2, che è il valore dell'ultima
stecca.
Perché non si debordi nei metri negativi, deve valere la condizione 2A > B.
A volte la condizione rimane vera scambiando i valori di A e B e a volte no.
Ad
esempio con n=15 e i due divisori 3 e 5, la condizione è verificata sia con
A = 3 che con A = 5, nel caso di n = 21 si può solo avere A = 7 e B = 3.
Ciao
Giorgio