Numismatica del Kissàndostan

[franco]

Il dittatore del Kissàndostan ha emesso un decreto che riforma totalmente il sistema monetario nazionale.
Art. 1 - La nuova valuta è il Tallero Kissàndostano (TK) che equivale a 6543 vecchi Scellini Kissàndostani.
Art. 2 - Tutti i prezzi e tutti i pagamenti dovranno essere espressi con numeri interi di TK (non sono ammessi i centesimi o altri sottomultipli)
Art. 3 - Il Tallero Kissàndostano sarà emesso in 12 tagli diversi (6 monete e 6 banconote).
Art. 4 - I valori nominali dei tagli dovranno consentire il pagamento esatto di qualsiasi importo fra 1 e 6543 TK utilizzando al massimo 8 pezzi fra monete e banconote (non necessariamente diversi fra loro).

Il problema è che adesso il presidente della Banca Nazionale Kissàndostana deve dare indicazioni alla zecca per i valori delle singole monete e banconote...

Siete in grado di aiutarlo senza utilizzare il computer?


G287

[Dani Ferrari]

Ah, bellino questo. Allora: se devo lavorare senza PC, devo suddividere il problema. Visto che sono 12 tagli e max. 8 pezzi, divido tutto per 4: 3 tagli, 2 pezzi. Con 1-3-4, con 2 pezzi max. posso fare i numeri da 0 a 8. Poi moltiplico i tagli per 9, e ho una secoda terna di tagli da 9-27-36, con cui posso fare con due pezzi da 0 a 8 "novine" (e con due pezzi dei tagli piccoli, con 4 pezzi arrivo a 80). Seguo con altri tre tagli moltiplicando per 9 i precedenti, 81-243-324, e l'ultima terna moltiplicando questi per 9: 729-2187-2916. Giusto?

Dani

[franco]

Dani,

Direi proprio che i conti tornano, complimenti!

Questo problema è stato posto ai candidati delle Olimpiadi della Matematica in Russia nella primavera 2013 ed è una variante del "Postage Stamp Problem" del quale si può reperire abbonante documentazione su Internet.

Nel sito francese da cui ho pescato il quesito vengono aggiunte due domande che probabilmente non fanno per te (1)

Q2 Con l'aiuto del computer, trovare una serrie di 12 tagli differenti tale per cui l'articolo 4 sia rispettato per prezzi sino a 13.000 TK.
Q3 Per i più coraggiosi (e forniti di un computer potente): determinare il massimo prezzo che puo essere fissato mantenendo inalterati il numero di 12 tagli e di 8 pezzi massimi per il pagamento.

(1) Non nel senso che non ne saresti capace, ma mi pare di capire che non le troveresti divertenti/stimolanti

ciao

[Dani Ferrari]

Si, è un derivato del problema dei francobolli. Non ho cercato gli aggiornamenti di cui parli su Internet, ma il problema fu posto al mio gruppo nel lontano 1997 da Dario Uri. Per metterla nei termini attuali, il problema originario era:
"Contestualmente alla riforma monetaria, il dittatore ha deciso una riforma del sistema postale. Verrà emessa una serie di 7 francobolli di diverso valore (inter0) tale che con un massimo di tre francobolli sia possibile comporre affrancature per tutti i valori interi fino a un massimo n. P. es. con 3 valori 1, 4, 5 si possono costruire tutti i valori fino a 15. Se i valori dei 7 francobolli non saranno scelti in modo da consentire di raggiungere tutti i valori fino al massimo possibile, il Direttore delle Poste sarà impalato sulla pubblica piazza. Potete aiutarlo nella scelta? Qual è il massimo valore di n?"
Quando un problema veniva posto al nostro gruppo, per noi non era bastante risolverlo: il problema doveva essere polverizzato. E se il Dittatore avesse deciso di emettere una serie di 8, 9, 10 valori? Dovevamo risolverlo, ma non sapevamo come fare. I calcoli necessari apparivano mostruosi, e i computers dell'epoca erano delle lumache. Bisognava fare un programma velocissimo. E su questo ci scontrammo io e il famigerato Quick Nick, il solutore più veloce del West - uno che, carezzando nervosamente il calcio della sua tastiera, usava mormorare: "L'unico problema buono è un problema risolto". Quando sbucava fuori un problema - ZA-BANG! risolto. Uno di meno. E quando programmava, di lui si diceva che se avesse guidato la macchina come programmava sarebbe morto da tempo: era in preda del demone della velocità.
Be' io non ero da meno: fu uno scontro fra giganti. Vinsi io per un soffio, ma non c'era proprio di che andarne fieri: io avevo programmato in Assembler, lui in C. E, almeno con i compilatori dell'epoca, l'assembler era tre volte più veloce: a parità di linguaggio, Quick Nick mi aveva stracciato. Ma con questi programmi riuscimmo a risolvere il problema fino a serie di 10 valori per elaborare la soluzione ci volevano quasi 3 ore)
Scrissi un articolo ammettendo la pesante sconfitta morale... e a questo punto successe l'imprevisto. Che, per timore che salti la connessione, vi narro nel prossimo post.

Dani

[Dani Ferrari]

Dunque dicevo: quando ci scontravamo io e Quick Nick, non c'era trippa per gatti: era molto ma molto difficile fare qualcosa di meglio. Ma questa volta, dopo la pubblicazione dell'articolo, mi scrisse uno sconosciuto lettore che, con una geniale gestione delle variabili e un complicatissimo lavoro di potatura dell'albero (taglio dei rami inutili senza perder tempo a sviluppare casi che non portano a niente) era arrivato a scrivere un programma OTTO VOLTE più veloce dei nostri. Con quello si arrivava - non ricordo in quante ore - fino a serie di 12 valori (sempre, ricordiamo, con tre esemplari). Mi scrisse anche che aveva avuto le idee risolutiva da miei precedenti articoli, cosa di cui fui molto fiero. Ma mettere insieme tutte le idee giuste... è spaventosamente difficile.
I PC di oggi sono qualche migliaio di volte più veloci di quelli di allora - ma se si fa matematica ricreativa sul serio, anche oggi non basta fare programmi che girino veloci come il vento: devono andare molto ma molto più svelti. Ora avete capito perché per trovare i valori ottimali di una serie di 12 valori usando fino a 8 pezzi (l'ultimo problema citato da Franco) occorra un computer molto potente e... tanta capacità di programmarlo: è roba da far tremar le vene e i polsi. Io ormai ho smesso da tanto di programmare, ma se qualcuno ci vuol provare, magari posso dargli un po' di ideucce...

Dani