[L03] Una catena molto preziosa

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L03] Una catena molto preziosa

Messaggioda Gerald Lambeau » 12/06/2016, 11:56

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 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)
Gerald Lambeau
 
Messaggi: 901
Iscritto il: 07/01/2015, 18:18

Re: [L03] Una catena molto preziosa

Messaggioda Roob » 06/12/2016, 19:20

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?
Ultima modifica di Roob il 06/12/2016, 19:37, modificato 1 volta in totale.
Roob
 
Messaggi: 28
Iscritto il: 23/11/2016, 16:52

Re: [L03] Una catena molto preziosa

Messaggioda Gerald Lambeau » 06/12/2016, 19:28

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}$.
"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)
Gerald Lambeau
 
Messaggi: 901
Iscritto il: 07/01/2015, 18:18

Re: [L03] Una catena molto preziosa

Messaggioda Roob » 06/12/2016, 19:43

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:
Roob
 
Messaggi: 28
Iscritto il: 23/11/2016, 16:52

Re: [L03] Una catena molto preziosa

Messaggioda Gerald Lambeau » 06/12/2016, 20:08

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)
Gerald Lambeau
 
Messaggi: 901
Iscritto il: 07/01/2015, 18:18


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite