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.
[L03] Una catena molto preziosa
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
[L03] Una catena molto preziosa
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: [L03] Una catena molto preziosa
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?
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?
Ultima modifica di Roob il 06/12/2016, 19:37, modificato 1 volta in totale.
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: [L03] Una catena molto preziosa
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:
Ad esempio 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}$.
Per le formule più grandi scrivi il seguente codice prima di tutta la formula:
Codice: Seleziona tutto
\displaystyle
Codice: Seleziona tutto
$\displaystyle \frac{1}{2}, \frac{1}{3}, \frac{1}{5}$
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)
Re: [L03] Una catena molto preziosa
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:
Grazie mille, più che altro quella sommatoria e i binomiali mi davano fastidio c:
-
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: [L03] Una catena molto preziosa
Sì, avevo preso un esempio a caso, comunque in genere si usa per frazioni, binomiali, sommatorie e produttorie.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)