Soluzione all'enigma 42, proposto da Elisa A.M. il 9 maggio 2005

Siamo nel mondo dei leggendari cavalieri della tavola rotonda, a Camelot. Sir Lancillotto deve partire per una missione di durata massima di un mese (30 giorni) su ordine di Artù (sono solo scuse per tenerlo lontano da Ginevra... ). Purtroppo, il nobile destriero di Lancillotto si è azzoppato rincorrendo la puledrina di Ginevra, così Lancillotto è costretto a chiedere in prestito un cavallo alla scuderia di Artù. Anche nel mondo fantastico di Camelot, purtroppo, nessuno dà niente per niente... Artù desidera qualcosa in cambio.
Ora, Lancillotto possiede una catena d'oro composta da trenta anelli e non richiusa su se stessa. Artù chiede a Lancillotto un anello di questa catena per ogni giorno in cui Lancillotto utilizzerà il destriero che Artù gli presta. Merlino, eletto arbitro della situazione, sarebbe il depositario della catena fino al ritorno del cavaliere e avrebbe il compito, ogni giorno di assenza di  Lancillotto, di pagare in modo adeguato Artù utilizzando gli anelli della catena. Lancillotto, che era un gran bel pezzo di cavaliere, ma non proprio un'aquila, si lamenta con Merlino perchè non vuole che la sua catena ogni sia spezzata in corrispondenza di ogni anello. Egli confida infatti di riuscire a tornare prima dei trenta giorni richiesti da Artù. Inoltre, l'eventuale "riaggancio" degli anelli costerebbe una cifra dal fabbro di Camelot!
Merlino lo rassicura: esiste un numero minimo, ben inferiore a 29, di anelli da spezzare per coprire i pagamenti di ogni giorno della sua
assenza. Qual è il numero minimo di anelli della catena che occorre rompere perchè questo sia possibile?
Per capirci meglio, immaginiamoci cosa accade:
Il primo giorno in cui Lancillotto non ha fatto ritorno, Artù si presenta da Merlino e chiede il pagamento e Merlino deve dargli un
anello. Il secondo giorno in cui Lancillotto non fa ritorno, stessa scena: Merlino deve dare ad Artù due anelli. Il terzo giorno idem, e così via... Facciamo fino al 20mo giorno in cui Lancillotto non fa ritorno. Artù va da Merlino e chiede il pagamento per 20 anelli (staccati, attaccati, ad Artù poco interessa). Il 21mo giorno Lancillotto torna.
Ora, se Merlino non fosse intelligente, dovrebbe ogni giorno staccare un anello dalla catena.
Ma, dato che è intelligente, ha trovato un modo per ottenere tutte le combinazioni possibili di quantità di anelli (dal minimo di 1 ad un massimo di 30) rompendo (volendo anche a priori, senza sapere quando tornerà Lancillotto) la catena in pochi punti strategici.

Ecco la soluzione proposta da Stefano.

Intanto io ho fatto questa assunzione, che spero sia corretta:
Quando Artu' viene a reclamare da Merlino un nuovo anello della catena, Merlino ha facolta di chiedere ad Artu' di restituirgli parte degli anelli gia' consegnati nei giorni precedenti, fatto salvo il fatto che Artu' deve tornarsene a casa a sera con un anello in piu' di quelli che aveva il giorno precedente.

Cio' supposto, per il caso specifico bastano 3 tagli, ma 2 sono troppo pochi. Perche? Beh, intanto se ho una catena e taglio un anello qualsiasi (che non sia il primo o l'ultimo) ottengo TRE gruppi di anelli: quello formato dagli anelli che precedevano quello che ho tagliato, quello formato dagli anelli che lo seguivano e l'anello stesso, che se ne sta da solo.

Ti propongo due soluzioni: la prima e' specifica per il caso con 30 anelli, la seconda e' il caso generale da cui anche questo e' deducibile, ma e' un po' elaborata (e in fin dei conti poco "elegante") e questa e' la ragione per cui ti mando comunque anche la prima.

Ora: 2 tagli (che producono 5 gruppi) non bastano, infatti di tali gruppi due sono formati da un singolo anello (i due che ho tagliato) e gli altri da, diciamo, x,y,z anelli (tali che x+y+z+2=30, visto la sfortunata circostanza fisica che non consente di creare anelli d'oro dal nulla). In quanti modi e' possibile combinare questi 5 numeri?  Beh, la matematica ci aiuta: sono i possibili "sottoinsiemi" di "X={1,1,x,y,z}", quindi sono 2^5 = 32. Ovviamente non e' detto che la somma dei numeri contenuti in ciascuno di questi 32 sottoinsiemi (facciamo 31 escludendo l'insieme vuoto) sia sempre diversa: due sottoinsiemi diversi potrebbero avere la stessa somma degli elementi contenuti! In particolare, visto che l'1 compare due volte, per ogni sottoinsieme A che contiene il primo 1 (ma non il secondo) tra i 31 ci sara' anche un insieme che contiene il secondo 1 (ma non il primo) e poi gli stessi altri elementi di A, e quindi dal punto di vista della somma e' "uguale" al precedente. Quindi sicuramente i sottoinsiemi di X che contengono esattamente un 1 "compaiono" due volte; quanti sono? Beh, la matematica aiuta ancora: i sottoinsiemi di X che contengono il primo 1 sono 2^4, quelli che contengono il secondo 1 pure loro sono 2^4, quelli che li contengono entrambi sono 2^3, quindi alla fine quelli che contengono uno ed un solo 1 sono 2^4 - 2^3 = 8. Questo ci dice che i valori *distinti* delle somme dei sottoinsiemi di X sono *al massimo* 31 - 8 = 23, troppo pochi per ricoprire tutti i numeri minori di 30.

Resta ora da vedere che, invece, 3 tagli sono sufficienti; basta tagliare per esempio in modo da ottenere i seguenti pezzi:
4 -- 4 -- 7 -- 12
ed in piu' ci sono i 3 anelli che ho tagliato (totale: 3+4+4+7+12 = 30, i conti tornano! ;-)). E' facile verificare che la cosa funziona: si possono ottenere tutti i numeri interi minori o uguali a 30 e maggiori o uguali ad 1.

Ma il tuo giochino (proprio carino!) mi ha stimolato: se avessi una catena di lunghezza N, quanti tagli al minimo dovrei fare?? Beh... provo a rispondere visto che di fatto quello sopra e' un caso particolare. (In realta' rispondo con eleganza solo alla domanda: "fissato il numero n di tagli da fare, qual e' la catena di lunghezza massima che posso prendere in considerazione?")
Intanto indichiamo con f(n) la funzione che associa ad un certo numero di tagli n di una catena la lunghezza massima di tale catena (ovviamente per lunghezza di una catena si intende il numero di anelli di cui e' costituita) affinche' ogni numero intero minore o uguale ad f(n) sia "rappresentabile". E' facile verificare che la catena di lunghezza massima con n tagli corrisponde ad avere n + 1 spezzoni di catena fatti cosi':
(*)  n+1 -- 2(n+2) -- 4(n+1) -- ... -- 2^n(n+1)
(piu', sempre, gli n anelli che ho tagliato). Quanto e' lunga la catena in totale? Beh si tratta di sommare tutti i precedenti, farsi due conticini e ottenere:
f(n) = (n+1)2^(n+1) - 1
E' chiaro che la catena di lunghezza f(n) e' spezzettabile in n pezzi (nel modo qui sopra), ma non in n-1 perche' f(n-1) < f(n).
Ora il problema e': i valori compresi tra f(n-1) + 1 e f(n) sono sempre realizzabili con n tagli, oppure potrebbero servirmene di piu'? A priori non mi sembra di poter escludere quest'ultima possibilita'... Per questa domanda, purtroppo non ho una risposta elegante... ti mando il mio modo di risolvere il problema, ma dopo averlo trovato mi e' rimasto quello spiacevole retrogusto da "ci deve essere un modo piu' 'bello' per farlo...". Aspetto trepidante di sapere se qualcun'altro che ha affrontato il caso generale e' stato piu' abile di me! :-)
Calcoliamo la somma dei termini della sequenza di tagli (*) escludendo l'ultimo spezzone a dx:
f(n) - 2^n(n+1) = ... = (n+1)2^n-1
Tutti i numeri compresi tra questo valore e f(n) li posso ottenere sostituendo al posto dell'ultimo numero di (*) i numeri da 1 a 2^n(n+1), quindi questi numeri sono costruibili. Ora, ipotizziamo invece di aggiungere un ulteriore taglio alla sequenza (*):
n+1 -- 2(n+2) -- 4(n+1) -- ... -- 2^n(n+1)   --   2^(n+1)(n+1)
Tale sequenza ha somma 2f(n) + 2 e mi permette, al variare dell'ultimo termine di costruire tutti i numeri compresi tra f(n) e 2f(n) + 2 (ma attenzione: con un taglio in piu' rispetto a prima perche' ho aggiunto un pezzo!).
Morale: con n tagli posso sicuramente costruire tutti i numeri compresi tra f(n-1) + 1 e 2f(n-1) + 2 e tutti quelli compresi tra (n+1)2^n - 1 e f(n); se per caso fosse
2f(n-1) + 2 >= (n+1)2^n - 1  per ogni n >= 1
sarei a posto, potrei costruire tutti i numeri. La  fortuna ci viene in aiuto, come e' facile verificare risolvendo la disequazione.
E questo e' quanto.