Classico monete e resto

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Classico monete e resto

Messaggio da Claudio. »

Sia $m_1,m_2, \cdots, m_{n-1}, 1$ un'n-upla di interi decrescenti. Sia $c\in\mathbb N$ e $t_1,\cdots, t_n$ interi naturali tali che $t_1m_1+t_2m_2+\cdots+t_n=c$.
Dimostrare che il minimo di $t_1+\cdots+t_n$ si ottiene per $\displaystyle t_1=\left\lfloor\frac c{m_1}\right\rfloor, t_2=\left\lfloor\frac {c-t_1m_1}{m_2}\right\rfloor,t_3=\left\lfloor\frac {c-t_2m_2-t_1m_1}{m_3}\right\rfloor...$
Ultima modifica di Claudio. il 27 lug 2013, 12:13, modificato 1 volta in totale.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Nel caso che tutti gli m e i t siano positivi la dimostrazione è semplice. Ho usato un procedimento grossolano, ma è il primo che mi è venuto in mente

La n-pla iniziale indicata nel testo comporta che sia : t1 = c/m1 ; t2=t3=….=tn=0 e quindi t1 + t2 + …. + tn = c/m1 , somma che indicheremo con S1
Per considerare altre n-ple occorre che sia t1 < c/m1 ; indichiamo t1 = c/m1 – b1 (con b1>0)

Supponiamo che t2 supplisca a tutta la parte mancante b1 di t1 per arrivare al totale c
Allora sarà m1 . t1 + m2 . t2 = c cioè: (c – b1 . m1) + m2 . t2 = c da cui : t2 = b1 . m1/m2 > b1
in questo caso la somma dei vari t , che indicheremo con S2 sarà : S2 = t1+t2+ 0+….+0 = c/m1 – b1 + b1 . m1/m2 . Cioè S2 > S1

Analogamente se il contributo di t2 non bastasse a compensare b1 , indichiamo t2 = b1 . m1/m2 – b2 ( con b2 >0)
Ipotizzando che basti allora il contributo di t3 per arrivare al totale c allora sarà :
m1 . t1 + m2 . t2 + m3 . t3 = c cioè (c – b1 . m1) + (b1 . m1/m2 - b2) m2 + m3 . t3 = c da cui : t3 = b2 . m2/m3 > b2
la somma S3 sarà allora S3 = t1 + t2 + t3 + 0 + …. + 0 = c/m1 – b1 + b1 . m1/m2 – b2 + b2 . m2/m3 Cioè S3 > S2

E così via . Ne consegue che la n-pla iniziale è quella a somma minima ( S1 = c/m1 )

Nel caso di qualche t <0 la demo dovrebbe rimanere simile : se per esempio nel caso precedente fosse imposto un t3 < 0 , allora il t4 moltiplicato per il suo m4, potrebbe compensare sia il valore negativo (m3 . t3) precedente che il residuo da compensare b2 . m2 ; e risulterebbe al solito una S4 > S3

Et cetera et cetera
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Classico monete e resto

Messaggio da EvaristeG »

Gli interi $m_j$ sono tutti maggiori di $1$, quindi anche di $0$. Dei $t_j$ viene detto che sono interi positivi, quindi anch'essi maggiori di zero. Per cui il caso $t_j<0$ non è da trattare.
maurizio43 ha scritto: La n-pla iniziale indicata nel testo comporta che sia : t1 = c/m1 ; t2=t3=….=tn=0 e quindi t1 + t2 + …. + tn = c/m1 , somma che indicheremo con S1
Perché? $c/m_1$ potrebbe non essere un intero (anzi, in genere non lo è).
Ad esempio, prendiamo $n=3$, $m_1=4, m_2=3, m_3=1$, $c=25$. La $n$-upla minimizzante suggerita dal testo è allora $t_1=6$, $t_2=0$, $t_3=1$.
Poi, tu cambi in ordine i valori di $t_2$, $t_3$ etc, ma nessuno dice che si debba procedere così. Io potrei (se il problema è giusto,ovviamente non posso, ma è quello che stiamo cercando di dimostrare) lasciare fissi $t_1,\ldots, t_7$ e cambiare $t_8$ e $t_9$ in modo da ottenere una $n$-upla con somma minore.
Infine, nella tua dimostrazione non si usa mai l'ipotesi che gli $m_i$ siano decrescenti...
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Consuete scuse e ringraziamenti per EvaristeG.
In effetti il mio intervento era affetto da una pletora di ‘cappelle’, frutto della più crassa ignoranza, sposata alla superficialità e alla pigrizia :
1°) In virtù (si fa per dire) di una lettura (colpevolmente) frettolosa avevo percepito l’ ultimo degli m indicato come m1 e non come 1
2°) Ogni t della n-pla proposta come minima l’avevo letto come indicato tra parentesi quadre e non col simbolo (simile) che indica la parte intera
dell’ operazione di divisione (mai abbandonare gli occhiali….)
3°) Comunque il mio procedimento avrebbe dovuto essere impostato sulla premessa : “se esiste una soluzione come quella proposta dal testo essa
è la minima”.
4°) E avrebbe dovuto essere sottolineato il particolare che, ove fosse scaturito (dalle operazioni di sostituzione) un tj non intero, si sarebbe dovuta
attribuirgli solo la parte intera, e passare il resto alle operazioni sui t susseguenti ; e se anche tn fosse risultato non intero si sarebbe potuto
concludere che la n-pla non era soluzione, e bisognava ripartire con un altro b1.
Di tutta la mia delirante soluzione (tanto per illudersi di non avervi fatto perder tempo) possiamo conservare la notazione che, comunque, sotto le equivocate ipotesi di partenza da me fatte, il metodo (anche se fa ridere) potrebbe considerarsi valido come un banale caso particolare , nel quale,
tra l’ altro, era effettivamente giocoforza partire dalla t1. (Della serie : tu mi fai una domanda, io rispondo ad un' altra, e morta lì )
L’ unica osservazione di EvaristeG sicuramente errata è quella che non avrei considerato l’ipotesi di m decrescenti : anzi è sempre stata considerata, perché quando scrivo t2=b1 . m1/m2 > b1 ( e così via) metto proprio in conto la decrescenza degli m .
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Classico monete e resto

Messaggio da auron95 »

Sono io che ho capito male il testo oppure prendendo gli $m_i$ $(5, 4, 3, 1)$ e prendendo $c=7$ la quaterna minima non è $(1,0,0,2)$ come dovrebbe ma è $(0,1,1,0)$ (4+3=7 e non 5+1+1)?
This is it. This is your story. It all begins here.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico monete e resto

Messaggio da Gottinger95 »

Auron ha ragione. Quella che penso sia la soluzione non funziona per una questione di congruenze. Se per esempio prendo come \(m_i\)
\((c-k, m_2, \ldots, m_{n-1}, 1)\) con \(m_2 + \ldots + m_{n-1} = c\), \(k \geq n-2\) e \(m_{n-1} > k \), ho che il metodo proposto dà \(k+1\) (un \(m_1\) e \(k\) volte 1) mentre prendendo solo i termini medi ottengo \(n-2\), minore di \(k+1\). Di fatto questo è il controesempio postato da Auron.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Per un recupero parziale della validità del teorema impostato da Claudio e smentito dall’ esempio di Auron95 dovrebbe essere
sufficiente aggiungere una ipotesi aggiuntiva su C , e cioè : “ C deve avere tra i suoi divisori m1 “
Alla luce di questa nuova ipotesi la n-pla minima di t proposta dal teorema si ridurrebbe ad avere diverso da zero solo
il primo termine t1 = C / m1 . E ovviamente anche la somma minima dei t avrebbe valore C / m1
Ne risultano un problema è un po’ striminzito e una soluzione è un po’ squallidina , con la aggravante dell’ esposizione con
simbolismo rudimentale, di cui mi scuso con tutti, perdurando il mio analfabetismo integrale circa il LaTeX , ma tant ‘è .

Dunque il problema si riduce a dimostrare che :
la n-pla t1= C / m1, t2=0, t3=0, ……. , tn=0 è la n-pla a somma minima tra quelle per le quali vale :
(1) t1 . m1 + t2 . m2 +t3 . m3+ ……… + tn . 1 = C
Indichiamo tale somma come S1 = t1 + t2 + ….. + tn = C / m1
Non essendo previsti valori negativi per i vari t ed m , risulta evidente che le varie possibili n-ple alternative
devono avere tutte il primo termine t1’ < C / m1 , cioè :
(2) t1’ = t1 - k1 ( con k1 naturale, minore di t1)
Chiamiamo t2’, t3’,….., tn’ i valori assunti dagli altri t della n-pla , sarà quindi :
(3) t1' . m1 + t2' . m2 + t3' . m3 + ……… + tn' . 1 = C
Dobbiamo dimostrare che S1’ = t1’ + t2’ + t3’ + ……… + tn’ > = S1

Se la nuova n-pla ha 1 solo termine tj’ non nullo , dovrà essere mj . tj’ = C
Cioè tj’ = C / mj = S1’ > S1
Se la nuova n-pla avrà solo 2 termini non nulli avremo t1’ . m1 + tj’ . mj = C
ovvero, per la (2) : mj . tj’ = m1 . k1 e quindi :
S1’ = t1 – k1 + (m1 / mj) . k1 > S1

Consideriamo più in generale il caso in cui i termini non nulli della nuova n-pla siano più di 2
Per pura semplificazione delle notazioni grafiche possiamo ipotizzare (senza ledere la generalità) che i termini non nulli
siano t3’, t6’, t8’, t9’. Ciò significa che sarà :
-m1 . k1 + m3 . t3’ + m6 . t6’ + m8 . t8’ + m9 . t9’ = 0 ovvero :
k1 = (m3 / m1) t3’ + (m6 /m1) t6’ + (m8 /m1) t8’ + (m9 /m1) t9’ e quindi :
k1 < t3’ + t6’ + t8’ + t9’ da cui :
S1’ > S1
Ultima modifica di maurizio43 il 12 ago 2013, 01:12, modificato 1 volta in totale.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico monete e resto

Messaggio da Gottinger95 »

Lancio un'ipotesi aggiuntiva un po' più debole. Dimostrare che vale anche se \(m_{n-1} \mid \ldots \mid m_1\), e si potrebbe fare un'ipotesi anche più debole di cui per adesso non sono certo.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Gottinger95, scusa la mia ignoranza (peraltro proverbiale) : non ho capito la tua ipotesi . Me la potresti esplicitare a parole ?
( e non vale più m1=1 ? )
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Classico monete e resto

Messaggio da EvaristeG »

$m_1$ non è mai stato $1$, $m_n$ è 1. Comunque $a\vert b$ vuol dire $a$ divide $b$, quindi l'ipotesi sarebbe: siano dati degli interi $m_1,\ldots, m_{n-1},1$ tali che $m_1$ è multiplo di $m_2$, $m_2$ è multiplo di $m_3$, eccetera, $m_{n-2}$ è multiplo di $m_{n-1}$ (e mi fermo qui, perché dire che $m_{n-1}$ è multiplo di $1$ è inutile).
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Ringrazio Evaristeg che ha la pazienza di colmare puntualmente i miei obnubilamenti.
La soluzione si fa molto meno fatica a pensarla che a buttarla giù sulla carta.
E a buttarla giù sulla carta si fa infinitamente meno fatica che a trovare una strada per
formalizzarla su e-mail senza l’ausilio del LaTeX (!) .
E’ così che il mio personalissimo UCCS , “Ufficio Complicazione Cose Semplici”
( che, come è noto, trasforma il facile in difficile mediante l’inutile ) è riuscito a
trasformare una banalità in un lavoraccio faticoso , che comunque vi espongo
(chiedendo venia se annoio).

Riassunto delle principali ipotesi di partenza poste da Claudio , nonché di quella
aggiuntiva proposta da Gottinger95 :
tj = numeri naturali ; mj = numeri naturali ; C = numero intero positivo
t1 = (C /m1) + r1 (con r1 intero < t1) e m1 = h1 . m2
t2 = (r1 /m2) + r2 (con r2 intero < t2) m2 = h2 . m3
t3 = (r2 /m3) + r3 (con r3 intero < t3) m3 = h3 . m4
…= ………. + … (con … intero < …) …. = ……..
con hj intero > 1
Sia pari a C la somma T = m1 . t1 + m2 . t2 + ……………….. + tn

Tesi : la somma S = t1 + t2 + ……..+ tn ha il valore minimo .
------------
Per ogni j sarà : m1 = lj . mj con j intero > 1 (ovviamente)

Indichiamo la somma dei termini di una qualunque n-pla alternativa come :
S’ = t1’ + t2’ + t3’ + …….. + tn’ ;
sarà T’ = m1 . t1’ + m2 . t2’ + ....... + tn’ = C

Per fissare le idee supponiamo t1’ = t1 – k1 con k1 < t1
[ma si può cominciare anche con altri termini t’ < t diversi dal primo ]
[e anche con più d’un termine]
Allora sarà m1 . t1’ = m1 . t1 - m1 . k1
1° caso : Per ogni indice j sia tj’ = tj
ad eccezione di un solo indice i per il quale sia ti’ = ti + ki
Allora m1 . k1 = mi . ki cioè ki = (m1/mi) . k1
Essendo ki > k1 sarà S’ > S
2° caso : Oltre a t1’ siano solo 2 i termini t’ diversi dai corrispondenti termini t
Cioè tj’ = tj + kj ; ti’ = ti + ki
con : m1 . k1 = mj . kj + mi . ki
cioè k1 = (mj /m1) . kj + (mi /m1) . ki
Poichè k1 < kj + ki sarà S’ > S
[ Analogamente si possono trattare i casi in cui ci siano tanti tj’ = tj + kj ]
_________________
[ In realtà in maniera intuitiva si poteva considerare graficamente i problema rappresentando :
- m1 come la somma di t2 segmentini adiacenti lunghi ciascuno m2
- m2 come la somma di t3 segmentini adiacenti lunghi ciascuno m3
- ………..
- C come la somma di t1 segmenti lunghi m1 , più un segmento sfrido r1 < m1
- r1 come la somma di t2 segmentini lunghi m2 , più un segmento sfrido r2 < m2
- r2 come la somma di t3 segmentini lunghi m3 , più un segmento sfrido r3 < m3
- ………….
E saltava subito all’occhio che : se t1 cala di qualche unità, facendo mancare qualche segmento m1,
sono molte di più le unità di cui devono crescere i vari tj per compensare la mancanza degli m1
con tanti segmentini più piccoli ]
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico monete e resto

Messaggio da Gottinger95 »

Aggiunti un paio di tag code -- EG
L'idea è giusta, ma prova a dargli una veste sia formale che grafica un po' più comprensibile :)
Da quanto ho capito hai difficoltà nella forma, e ti capisco perchè ne faccio anche io, ma ti assicuro che la fatica paga.

1. Scrivi in Latex. Il testo in Latex va incluso tra

Codice: Seleziona tutto

\(
e

Codice: Seleziona tutto

\)
: scrivi sempre tutte le variabili e le equazioni tra

Codice: Seleziona tutto

\( \)
. Per i comandi, se non ti va di leggerti un manuale, puoi cercarli singolarmente su google (della serie "latex a divide b", o "latex esponente") oppure spizzarti il codice degli altri murofili dell'oliforum cliccando il tasto destro sul codice, poi premendo Show Math As > TeX Commands. Sono certo che in poco tempo saprai scrivere più o meno tutto quello che ti serve.
2. Fai in modo che il lettore sappia quello che hai intenzione di fare. In altre parole, spiega quello che le equazioni che stai per scrivere significano. Per esempio, scrivi: "Vogliamo dimostrare che, presa una una qualsiasi \(n\)-upla alternativa a quella che supponiamo avere somma minima, si ottiene una somma maggiore. Infatti, ..."
3. Definisci dei termini che ti possano aiutare a scrivere una soluzione più chiara, dando un nome alle cose che usi più spesso (come le \(f,S\) qui sotto). Per esempio:
"Definiamo:
1.\(T=(t_1, \ldots, t_n)\) e \(M = (m_1, \ldots, m_n)\);
2.Date \(X=(x_1, \ldots, x_n)\) e \(Y = (y_1, \ldots, y_n)\) generiche \(n\)-uple di interi, sia \(f(X,Y) = x_1 y_1 + \ldots + x_n y_n\) e \(S(X) = x_1 + \ldots + x_n\);

Allora la tesi è: per ogni \(T'\) tale che \(f(T,M) = f(T',M)\), si ha \(S(T') \leq S(T)\). Per dimostrarlo, poniamo \(D= T- T'\). Visto che \(f,S\) sono lineari, abbiamo:

\(f(T,M) = f(T',M)\ \ \Leftrightarrow\ \ \ f(D+T',M) = f(T',M)\ \ \Leftrightarrow\ \ f(D,M) + f(T',M) = f(T',M)\ \ \Leftrightarrow\ \ f(D,M) = 0\)
e
\(S(T') \leq S(T)\ \ \Leftrightarrow \ \ S(T') \leq S(T'+D)\ \ \Leftrightarrow \ \ S(T') \leq S(T') + S(D) \ \ \Leftrightarrow \ \ S(D) \geq 0\)

Allora il problema si riduce a: per ogni \(D\) che può esser scritto come \(T-T'\) e che rispetti \(f(D,M) = 0\), allora \(S(D) \geq 0\). Come possono esser fatti questi \(D\)?
eccetera eccetera eccetera. Ho scritto cose abbastanza a caso eh, non è che sia per forza la via per la dimostrazione.

Dai, prova a riscriverla!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

Sei estremamente gentile e ti sono molto grato.
Non so proprio come farò -la prossima volta- ad aver la faccia di far trionfare le mie pigrizia-e-malavoglia sulla giusta necessità di usare il LaTeX !
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico monete e resto

Messaggio da Gottinger95 »

Tranquillo! Non c'è di che, però esercitati a scrivere le soluzioni, mi raccomando! Non c'è niente di peggio che capire un problema ma prendere 0 perchè scritto incomprensibile :) E mi è successo, giurin giurello.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Classico monete e resto

Messaggio da maurizio43 »

E' tutto vero, però il meglio forse sono i pregi della sintesi :
Il flash sintetico di uno schizzo grafico che ti raffigura C come tanti segmenti adiacenti :

- 4 “segmentoni” lunghi m1, seguiti da 2 segmenti lunghi m3, poi da 3 “segmentini” lunghi m2 , e da un paio di segmenti unitari.
- Una circonferenza che racchiude a mo’ di lente di ingrandimento i primi 2 “segmentoni” m1 ( ciascuno con evidenziati i più segmenti m3 di cui è costituito)
- Una freccia che indica il trasferimento di questi segmenti nelle zone degli m3 / m2 / m1
- L’ immediata conclusione che la somma dei t non può che aumentare .

20 secondi per tracciare il grafico + 2 secondi per arrivare alle conclusioni : non è il massimo della soddisfazione ?
Rispondi