dimostrazione di un torneo

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
call
Messaggi: 20
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da call »

dimostare che in un torneo (ad es di tennis il numero degli incontri è sempre uguale al numero dei partecipanti -1)
<BR>es: partecipanti: 128
<BR>incontri: 64+32+16+8+4+2+1=127
I problemi che valgono un attacco, lo dimostrano con un controattacco.
lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss »

Beh, innanzitutto affinchè alla fine del torneo vi sia un vincitore unico, il numero dei partecipanti deve essere una potenza di due.
<BR>Se il numero dei partecipanti è 2^n, allora il numero di incontri sarà uguale (partendo dal fondo) a sum[j=0...n-1]2^j. Basta dunque dimostrare che questa somma è uguale a 2^n -1. Dimostriamolo, che so, per induzione:
<BR>i)si verifica subito che sum[j=0...1]2^j=2²-1.
<BR>ii)supponiamo che sum[j=0...n]2^j=2^(n+1)-1 Allora sum[j=0...n+1]2^j=2^(n+1)-1+2^(n+1)=2*2^(n+1)-1=2^(n+2)-1 che è cio che volevamo dimostrare.
<BR>Ciao
<BR>
<BR>[addsig]
call
Messaggi: 20
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da call »

Domani ti posto una dimostrazione semplice ma molto elegante[addsig]
I problemi che valgono un attacco, lo dimostrano con un controattacco.
jimmy
Messaggi: 10
Iscritto il: 01 gen 1970, 01:00
Località: Pavia
Contatta:

Messaggio da jimmy »

Prima di tutto non e\' necessario che il numero di partecipanti sia una potenza di due... se non lo e\' infatti basta costruire il tabellone di conseguenza.... non tutti faranno lo stesso numero di incontri ma esistono le teste di serie etc. etc.
<BR>Poi per dimostrare l\'affermazione basta dire che in un torneo con n partecipanti se c\'è un vincitore ci saranno (n-1) sconfitti. Ogni partita viene sconfitto uno ed un solo partecipante, dunque ci sono (n-1) incontri) <IMG SRC="images/forum/icons/icon_razz.gif">
call
Messaggi: 20
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da call »

complimenti jimmy a dimostrazione che volevo postare era proprio quella che hai dato tu[addsig]
I problemi che valgono un attacco, lo dimostrano con un controattacco.
Bloccato