OliForum Matematico

Federico vuole corrompere Ludovico per avere di nascosto e in anticipo le soluzioni delle edizioni 2017 e 2018 delle ITAMO, così da potersi classificare primo assoluto con il massimo del punteggio negli anni a venire.
Ludovico pretende un pagamento particolare: una catena d'oro lunga $n$ anelli. Federico patteggia per poter pagare a rate di un anello al giorno, ma Ludovico vuole che la catena che riceverà sia divisa nel minor numero $k$ di pezzi possibile.
Si possono presentare due situazioni:
(a) Federico ha soldi infiniti, ma nessuna catena d'oro; Ludovico gli dice un numero $k$ di pezzi minimi in cui vuole che la catena sia divisa e dice di volere la catena di lunghezza massima affinché $k$ vada bene. Trovare la lunghezza massima $n$ che deve avere la catena che Federico deve comprare affinché $k$ sia il numero minimo di pezzi in cui dividerla per poter pagare le rate.
(b) Federico ha una catena d'oro di lunghezza $n$; trovare il numero minimo $k$ di pezzi in cui dovrà dividerla per poter pagare le rate.

i) Con un'induzione un po' zoppa: se $k=1$ evidentemente la collana più lunga possibile è composta da $1=2^k-1$ anelli; supponendolo vero per $j$, vediamo quanti anelli possiamo aggiungere con un altro pezzo: evidentemente c'è un modo per consegnare un ulteriore pezzo lungo $2^j$, basta consegnare prima tutti gli altri, poi dare quest'ultimo riprendendo i piccoli e ripetere. Se volessimo aggiungere un pezzo di lunghezza $>2^j$? Non è possibile dato che anche consegnando prima tutti gli altri dovremmo dargliene almeno due in più in un sol giorno. Da cui $k=j+1\Rightarrow n_{max}=2^{j+1}-1$, il che conclude.

ii)Sia $k=\{min\space x \in \mathbb{N}|2^x-1\geq n\}$ per il punto precedente è possibile farlo in questo modo, e sempre per il punto precedente è il minimo (se ci fosse una possibilità che lo rende non minimo allora sarebbe violato il punto i).

Troppo campata per aria o ha senso?

È giusta! Una volta fatto il punto (a), il punto (b) è immediato.
Per evitare l'induzione zoppa nel punto (a) un modo alternativo è il seguente: date $k$ catene piccole, il numero di sottoinsiemi non vuoti è $2^k-1$; supponendo che le somme delle lunghezze delle catene piccole di ogni sottoinsieme siano diverse l'una dalle altre (in modo da poter fare più numeri possibile), dato che vogliamo tutti i numeri da $1$ a $n$, otteniamo un limite superiore: $n \le 2^k-1$, non si possono fare più numeri di così.
Per $n=2^k-1$, consideriamo le $k$ catene lunghe $1, 2, 4, \dots, 2^{k-1}$. La somma è chiaramente $n$. Dato un numero $m \le n$, scriviamolo in base $2$, se c'è un $1$ nella $h$-esima posizione (contando a partire da destra) allora mettiamo la catena $2^{h-1}$, altrimenti non ce la mettiamo, e il gioco è fatto.