EURII

[Barozz]

[Spostato da Teoria dei Numeri. M.]
-------------------

Trovare il numero di soluzioni intere non negative dell' equazione
$ a+2b+5c+10d+20e+50f+100g=100 $

[Boll]

MMMh, se ho ben compreso il tuo problema. Il minimo dell'espressione che hai a sinistra è $ 1+2+5+20+50+100 $, che è$ >100 $ quindi la risposta è banlmente "non ne esistono".

[Loth]

Forse si intendeva intere non negative...

[Barozz]

Sì scusate, intendevo naturalmente le soluzioni non negative... se no il problema non avrebbe senso..

[mark86]

A meno che non ci siano modi più semplici io sto calcolando le soluzioni con una struttura ad albero.... faccio una stima in base ai risultati che ho ottenuto fino ad ora: l'insieme di soluzioni (cioè di 7-uple) dovrebbe essere maggiore di 700 e al limite minore di 1000; Baroz dimmi se la mia stima è più o meno corretta perché altrimenti mi metto le mani ai capelli......

[Barozz]

Mark a dire la verità non ne ho molta idea.. ma sono rimasto un poco sorpreso dalle tue conclusioni perchè la mia stima si aggira in torno ai 6 miliardi, precisamente ho calcolato (in bianco):
6153732201.
Secondo voi è possibile? Aspetto di sapere di quanto ho sbagliato.
Comunque sono sicuro che è molto più di mille, molto più..

[Igor]

Barroz, credo che la tua stima sia sbagliata.Infatti a,b,c,d,e,f,g possono assumere rispettivamente 101,51,21,11,6,3 e 2 valori, dunque il numero di soluzioni sarà
certamente minore di 101*51*21*11*6*3*2=42835716, ben al di sotto di sei miliardi.

Ho provato anch'io a risolvere il problema usando una struttura ad albero, ma non riesco a venirne fuori, penso quindi che ci sia qualche metodo più immediato.

[Catraga]

Penso che la struttura ad albero aiuti a capire la soluzione del problema; ma siete sicuri di avere cosi' tante foglie? a me ne vengono molte meno....
Comunque si, esiste una soluzione molto piu' elegante, chiamata teoria del cambio (essenzialmente si tratta di dire in quanti modi si puo' cambiare una banconota da k euro), ma e' parecchio ostica e non e' di certo adatta a questo forum.
In questo caso semplice si puo' utilizzare una struttura ad albero...

[Marco]

Mark a dire la verità non ne ho molta idea..

Ciao. Solo una nota di metodo, per Barozz, ma anche per tutti gli altri.

Proponendo un problema, quando non si è convinti della sua elmentarità, sarebbe bene metterlo non sotto Problem-Solving Olimpico, ma sotto Matematica non Elementare. In generale, suggerisco che, nel dubbio, andrebbero messi sotto P.S.O. solo problemi di pb.solving conclamato (dati a gare, stages, da libri, ecc...). Il resto (come questo filo) lo sistemerei sotto M.N.E.

Inoltre, quando si posta un problema SENZA conoscerne la soluzione, andrebbe dichiarato con il problema (vedi Regole di Fph).

In conclusione, a meno che non salti fuori una soluzione elementare (dal p.to di vista olimpico) entro breve, procediamo a spostare la discussione di là, così possiamo divertirci ad attaccarlo con roba più tosta, come suggerisce Catraga qui sopra.

Comunque, buon lavoro con i vostri euri.

Ciao. M.

[mark86]

Catraga, puoi allora dirci qual è il tuo risultato? Così appena finisco i "conti" lo confronto con il mio.

[Barozz]

Ok Marco, hai ragione. In effetti dovrei leggermi bene il regolamento del forum per evitare di alterare il buon ordine che va formandosi all' interno di questo sito.
Prometto che più avanti starò molto più attento.

Intanto rilancio
$ 4563 $.

Mi scuso anche per la castroneria che ho sparato in precedenza...Ora questo numero non mi sembra così brutto.

[Igor]

Io ne ho contate 4269.Ho controllato e non mi sembra di aver fatto errori di calcolo,ma è possibile che mi sia sfuggita qualche soluzione.Ora lo rivedo meglio.

[Simo_the_wolf]

Da farlo computare al PC non pare così brutto... Dovrebbe essere qualcosa del tipo:
$ \displaystyle N_{modi}=\sum_{a_1=0}^{\lfloor \frac {100}{100} \rfloor} $ $ \displaystyle \sum_{a_2=0}^{\lfloor \frac {100-100a_1}{50} \rfloor} \sum_{a_3=0}^{\lfloor \frac {100-100a_1-50a_2}{20} \rfloor} $ $ \displaystyle \cdots \sum_{a_7=0}^{\lfloor \frac {100-100a_1-50a_2-20a_3-10a_4-5a_5-2a_6}{100} \rfloor} 1 $

Ma "olimpicamente", al momento non mi sovviene nulla...