Robin Hood

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

Robin Hood

Messaggioda Giovanni98 » 06/11/2016, 15:18

Per ogni $n$ intero positivo si divida una circonferenza mediante $2n$ punti in $2n$ archi di ugual lunghezza. Dimostrare che se si disegnano $n+1$ archi di lunghezza $1,2,\cdots,n+1$ ne esistono due tali che uno sia contenuto nell'altro.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Robin Hood

Messaggioda Gerald Lambeau » 07/11/2016, 16:49

Gli $n+1$ archi che andiamo a disegnare devono avere gli estremi coincidenti con quelli dei $2n$ iniziali o posso metterli a caso?
Se fosse la prima cosa che dico allora ho la soluzione.
"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: 920
Iscritto il: 07/01/2015, 18:18

Re: Robin Hood

Messaggioda Giovanni98 » 08/11/2016, 18:08

La prima.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: Robin Hood

Messaggioda Gerald Lambeau » 08/11/2016, 18:39

Testo nascosto:
Molto bene, diamoci dentro con l'induzione!

Passo base: $n=1$. Ci sono due archi, se disegno l'arco lungo $n+1=2$ occupo tutto il cerchio e quindi l'arco lungo $1$ dev'essere necessariamente disegnato dentro l'arco lungo $2$.

Passo induttivo: tesi vera per $n$ implica tesi vera per $n+1$. Per farlo dimostrerò che, se la tesi fosse falsa per $n+1$, allora lo sarà anche per $n$.
Diciamo che un arco fra quelli disegnati ne divora un altro quando il secondo è contenuto nel primo.
Supponiamo che, per $n+1$, possiamo disegnare nel cerchio da $2n+2$ unità gli archi da $1$ a $(n+1)+1$ senza che nessuno divori qualcun altro. Allora ovviamente l'arco lungo $1$ non si sovrappone con nessuno, altrimenti questi lo divorerebbe. Muoviamoci, a partire dall'arco lungo $1$, vero sinistra, finché non incontriamo l'inizio di un altro arco: notiamo che nell'unità lunga $1$ dove inizia questo secondo arco non ne può iniziare un altro, altrimenti il più grande dei due divorerebbe il più piccolo, ed essendo questo il primo arco che incontriamo a sinistra di quello lungo $1$ possiamo dedurre che nell'unità dove inizia c'è solo lui (poi dopo si può anche sovrapporre con altri, non ci interessa), quindi il tratto lungo $1$ all'estrema destra di questo arco non si sovrappone con nessun altro arco.
Facciamo queste azioni:
- cancelliamo l'arco lungo $1$, togliamo l'unità lunga $1$ dove si trovava e richiudiamo il cerchio, che ora è lungo $2n+1$. Così facendo cancelliamo solo l'arco lungo $1$, il quale non poteva divorare nessuno, e comunque se lo tolgo completamente la situazione non cambia: nessuno divora qualcun altro;
- cancelliamo il tratto lungo $1$ all'estrema destra di ogni arco disegnato da quello lungo $2$ a quello lungo $(n+1)+1$, per farli diventare da $1$ a $n+1$. Se per caso ora qualcuno divorasse qualcun altro, anche prima avrebbe avuto gli estremi più larghi o coincidenti e quindi anche prima di quest'azione lo avrebbe divorato, ma sappiamo che non è così quindi ancora nessuno divora nessuno. Inoltre, l'arco che prima era il primo a sinistra di quello lungo $1$ ormai perduto perde il tratto lungo $1$ all'estrema destra, che non avendo sovrapposizioni in quella specifica unità lascia uno spazio vuoto;
- togliamo dunque quell'unità vuota e richiudiamo il cerchio, che ora è lungo $2n$ e ha disegnati tutti gli archi da $1$ a $n+1$ in maniera che nessuno divora nessuno.
Quindi, ricapitolando: se posso farlo per $n+1$, cioè se la tesi fosse falsa per $n+1$, allora lo sarebbe anche per $n$; la tesi è vera per $n$, quindi è vera anche per $n+1$.
Fine.

Capisco che alcune cose potrebbero non essere molto chiare in quanto sono concetti scomodi da spiegare senza un disegno, in caso qualcosa non ti tornasse fammelo pure sapere e cercherò di spiegarla meglio.
"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: 920
Iscritto il: 07/01/2015, 18:18


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite