[L03] Una catena molto preziosa

[Gerald Lambeau]

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.

[Roob]

a) Abbiamo a disposizione [tex]k[/tex] quantità di anelli, e vogliamo vedere a quante diverse catene di anelli possiamo dare luogo sommando [tex]m[/tex] di queste quantità (ci preoccuperemo dopo che siano distinte e consecutive). Tutte le possibili somme sono:
Le [tex]\binom{k}{1}=k[/tex] quantità prese una a una
Le [tex]\binom {k}{2}[/tex] somme a due a due
[tex]\cdots[/tex]
Le [tex]\binom {k}{k-1}[/tex] somme a [tex]k[/tex] a [tex]k[/tex]
L'unica somma di tutte le [tex]k[/tex] quantità
Non consideriamo la (non)somma di 0 quantità perché se una somma è uguale a 0 non è di alcuna utilità al problema.
Poiché [tex]\sum_{m=0}^k \binom {k}{m}=2^{k}[/tex], ma noi non consideriamo [tex]\binom{k}{0}[/tex], con [tex]k[/tex] quantità possiamo ottenere al più [tex]2^{k}-1[/tex] somme differenti.
Poiché nel nostro caso le somme devono essere consecutive e la più piccola uguale ad uno, il più grande numero [tex]n[/tex] teoricamente ottenibile è appunto [tex]2^{k}-1[/tex], che in effetti è ottenibile se le quantità sono [tex]2^{0}, 2^{1}, \dots, 2^{k-1}[/tex] (si dimostra facilmente per induzione)

b) dovrei dimostrare in qualche modo che col metodo di sopra e qualche somma che si ripete posso ottenere anche i numeri che non sono scrivibili come [tex]2^{k}-1[/tex], che hanno bisogno dello stesso [tex]k[/tex] del più piccolo [tex]2^{k}-1[/tex] maggiore di loro, e quindi per ogni [tex]n[/tex], [tex]k[/tex] è l'esponente della più piccola potenza di due maggiore di [tex]n[/tex]

Mi dispiace se la b) è molto bruttina, ma non mi è venuta nessuna idea per formalizzarla un pochino di più

P. S. Come faccio a scrivere le formule in latex più grandi?

[Gerald Lambeau]

Giuste entrambe, la b) alla fine non sei molto lontano dalla formalizzazione: se $2^k-1<n<2^{k+1}-1$ sai che con $k$ non riesci a farne $n$ diverse perché ne fai al più $2^k-1$, mentre con $k+1$ ci riesci senza problemi.

Per le formule più grandi scrivi il seguente codice prima di tutta la formula:

Codice: Seleziona tutto

\displaystyle

Ad esempio

Codice: Seleziona tutto

$\displaystyle \frac{1}{2}, \frac{1}{3}, \frac{1}{5}$

produce il seguente testo: $\displaystyle \frac{1}{2}, \frac{1}{3}, \frac{1}{5}$, che a quanto ho capito tu vorresti al posto di $\frac{1}{2}, \frac{1}{3}, \frac{1}{5}$.

[Roob]

Ah giusto, basta che il [tex]k+1[/tex]-esimo sia [tex]n-2^{k}+1[/tex]

Grazie mille, più che altro quella sommatoria e i binomiali mi davano fastidio c:

[Gerald Lambeau]

Sì, avevo preso un esempio a caso, comunque in genere si usa per frazioni, binomiali, sommatorie e produttorie.