OII 2007-11-23 – 9

La regione organizza un torneo di calcio fra le classi di scuola superiore.

  • Al torneo partecipano 380 squadre.
  • Il torneo è a eliminazione diretta e quindi ogni sfida ha un vincitore.
  • Ad ogni turno le squadre vengono divise in coppie: le due squadre si sfidano e la vincente passa al turno successivo.
  • Se ad un turno il numero delle squadre rimaste è dispari si sorteggia una squadra che passa automaticamente il turno.

Qual è il numero totale di partite giocate fra tutte le squadre per determinare la squadra vincente?


Soluzione: 379.


Soluzione #1

Infatti ogni partita giocata ha un perdente che viene eliminato ed essendoci un solo vincitore ci sono 379 perdenti complessivi.


Soluzione #2

(Forza bruta) Simulo i turni del torneo, secondo il regolamento, fino ad arrivare a un vincitore e poi calcolo il numero totale di sfide

Turno Squadre
partecipanti
Sfide Squadre
passate
Osserva
1 380 190 190
2 190 95 95
3 95 47 48 Una squadra passa per sorteggio
4 48 24 24
5 24 12 12
6 12 6 6
7 6 3 3
8 3 1 2 Una squadra passa per sorteggio
9 2 1 1 Squadra vincitrice
379