Il torneo
Ad un torneo partecipano \(\displaystyle n \) squadre, \(\displaystyle n \ge 3 \). Ogni squadra gioca una volta con ogni altra squadra. Ci sono tre squadre \(\displaystyle A \), \(\displaystyle B \) e \(\displaystyle C \) tali che \(\displaystyle A \) sconfigge \(\displaystyle B \), \(\displaystyle B \) sconfigge \(\displaystyle C \) e \(\displaystyle C \) sconfigge \(\displaystyle A \). Dimostrare che alla fine del torneo ci sono almeno due squadre a pari punti.
Prove it!
Risposte
Ovviamente 
Salve, mi è stato proposto questo quesito e ho trovato la vostra risposta.
Purtroppo non riesco a comprenderla a fondo, potreste gentilmente descrivermela??
Purtroppo non riesco a comprenderla a fondo, potreste gentilmente descrivermela??
Teniamo buona l'ipotesi che il punteggio consista nel numero di partite vinte (con esclusione del pareggio).
Date $n$ squadre, se ciascuna di esse gioca un sola volta contro tutte le altre, il numero totale di partite sarà dato da $(n-1)+(n-2)+...+2+1$ cioè $sum_(i=1)^(n-1) i=(n(n-1))/2$; questo perché presa una squadra qualsiasi essa giocherà $n-1$ partite contro le altre $n-1$ squadre, presa poi un'altra squadra questa giocherà $n-2$ partite contro le altre $n-2$ squadre rimaste (contro quella precedente ha già giocato quindi non la contiamo).
Dato che ogni partita ha un vincitore e una partita vinta è uguale a un punto allora la somma dei punti totali è uguale al numero di partite totali (e cioè sempre $(n(n-1))/2$).
Ora, per assurdo, poniamo il caso che tutte le $n$ squadre abbiano tutte punteggi diversi (quindi avremo $n$ punteggi diversi fra loro), il max possibile fra questi punteggi è $n-1$ se una squadra vince tutte le partite; dato che dobbiamo avere $n$ punteggi diversi ed il max è $n-1$ allora significa che i punteggi delle nostre squadre corrispondono a tutti gli interi da $0$ a $n-1$.
Per ipotesi però nessuna squadra è a zero punti quindi le $n$ squadre si dovranno "distribuire" su non più di $n-1$ punteggi diversi e per il "PigeonHole Principle" almeno due squadre devono "condividere" lo stesso punteggio.
Cordialmente, Alex
Date $n$ squadre, se ciascuna di esse gioca un sola volta contro tutte le altre, il numero totale di partite sarà dato da $(n-1)+(n-2)+...+2+1$ cioè $sum_(i=1)^(n-1) i=(n(n-1))/2$; questo perché presa una squadra qualsiasi essa giocherà $n-1$ partite contro le altre $n-1$ squadre, presa poi un'altra squadra questa giocherà $n-2$ partite contro le altre $n-2$ squadre rimaste (contro quella precedente ha già giocato quindi non la contiamo).
Dato che ogni partita ha un vincitore e una partita vinta è uguale a un punto allora la somma dei punti totali è uguale al numero di partite totali (e cioè sempre $(n(n-1))/2$).
Ora, per assurdo, poniamo il caso che tutte le $n$ squadre abbiano tutte punteggi diversi (quindi avremo $n$ punteggi diversi fra loro), il max possibile fra questi punteggi è $n-1$ se una squadra vince tutte le partite; dato che dobbiamo avere $n$ punteggi diversi ed il max è $n-1$ allora significa che i punteggi delle nostre squadre corrispondono a tutti gli interi da $0$ a $n-1$.
Per ipotesi però nessuna squadra è a zero punti quindi le $n$ squadre si dovranno "distribuire" su non più di $n-1$ punteggi diversi e per il "PigeonHole Principle" almeno due squadre devono "condividere" lo stesso punteggio.
Cordialmente, Alex
"axpgn":
Teniamo buona l'ipotesi che il punteggio consista nel numero di partite vinte (con esclusione del pareggio).
Date $n$ squadre, se ciascuna di esse gioca un sola volta contro tutte le altre, il numero totale di partite sarà dato da $(n-1)+(n-2)+...+2+1$ cioè $sum_(i=1)^(n-1) i=(n(n-1))/2$; questo perché presa una squadra qualsiasi essa giocherà $n-1$ partite contro le altre $n-1$ squadre, presa poi un'altra squadra questa giocherà $n-2$ partite contro le altre $n-2$ squadre rimaste (contro quella precedente ha già giocato quindi non la contiamo).
Dato che ogni partita ha un vincitore e una partita vinta è uguale a un punto allora la somma dei punti totali è uguale al numero di partite totali (e cioè sempre $(n(n-1))/2$).
Ora, per assurdo, poniamo il caso che tutte le $n$ squadre abbiano tutte punteggi diversi (quindi avremo $n$ punteggi diversi fra loro), il max possibile fra questi punteggi è $n-1$ se una squadra vince tutte le partite; dato che dobbiamo avere $n$ punteggi diversi ed il max è $n-1$ allora significa che i punteggi delle nostre squadre corrispondono a tutti gli interi da $0$ a $n-1$.
Per ipotesi però nessuna squadra è a zero punti quindi le $n$ squadre si dovranno "distribuire" su non più di $n-1$ punteggi diversi e per il "PigeonHole Principle" almeno due squadre devono "condividere" lo stesso punteggio.
Cordialmente, Alex
Grazie mille per la celere risosta
Però ancora non capisco il fatto che per ipotesi nessuna squadra sia a 0 punti.. Questo è sicuramente valido per n=3, ma se ad esempio io vado con n=4, c'è il caso in cui la mia quarta squadra perde tutte e tre le partite e resta a zero.
grazie mille per la pazienza!
In effetti neanche io capisco la dimostrazione che è stata scritta. Comunque, propongo la seguente versione più forte:
Ci sono due squadre con lo stesso numero di punti SE E SOLO SE esistono tre squadre A, B, C tali che A batte B che batte C che batte A.
Ci sono due squadre con lo stesso numero di punti SE E SOLO SE esistono tre squadre A, B, C tali che A batte B che batte C che batte A.
Sì, scusate, l'ipotesi non significa che nessuna squadra è a zero punti, ma che le tre squadre $A$, $B$ e $C$ hanno lo stesso punteggio nel loro mini torneo a tre.
Beh, allora lo dimostriamo diversamente ...
Affinché nessuna squadra sia a pari punti con le altre significa che in un torneo a $n$ squadre i punteggi sono tutti diversi e sono i naturali da $0$ a $n-1$ (dato il sistema di punteggio in ipotesi).
La prima in classifica con $n-1$ punti avrà vinto con tutte le altre $n-1$ squadre, la seconda avrà perso solo con la prima e vinto con tutte le altre e così via in un processo che ha termine in quanto ogni sottoinsieme di naturali ha un minimo.
Poniamo che le nostre tre squadre $A$, $B$ e $C$ siano finite in quest'ordine (non necessariamente consecutive): allora $C$ deve aver perso sia con $A$ che con $B$ ma ciò è assurdo per ipotesi. Analogo ragionamento per gli altri $5$ ordinamenti possibili. Ergo, data l'ipotesi almeno due squadre sono a pari punti.
Cordialmente, Alex
Beh, allora lo dimostriamo diversamente ...
Affinché nessuna squadra sia a pari punti con le altre significa che in un torneo a $n$ squadre i punteggi sono tutti diversi e sono i naturali da $0$ a $n-1$ (dato il sistema di punteggio in ipotesi).
La prima in classifica con $n-1$ punti avrà vinto con tutte le altre $n-1$ squadre, la seconda avrà perso solo con la prima e vinto con tutte le altre e così via in un processo che ha termine in quanto ogni sottoinsieme di naturali ha un minimo.
Poniamo che le nostre tre squadre $A$, $B$ e $C$ siano finite in quest'ordine (non necessariamente consecutive): allora $C$ deve aver perso sia con $A$ che con $B$ ma ciò è assurdo per ipotesi. Analogo ragionamento per gli altri $5$ ordinamenti possibili. Ergo, data l'ipotesi almeno due squadre sono a pari punti.
Cordialmente, Alex
Questa sembra andare
E per la versione più forte?
E per la versione più forte?
Allora ...
Se almeno due squadre ($a$ e $b$) sono a pari punti significa che se escludiamo il loro scontro diretto una delle due aveva un punto in meno dell'altra (Es. $a$ batte $b$ perciò se entrambe hanno finito a $k$ punti, escludendo il loro scontro, $a$ ha $k-1$ punti).
Se entrambe avessero fatto il medesimo risultato (vittoria o sconfitta che sia) con le altre allora non sarebbe possibile che finiscano con lo stesso punteggio, perciò esiste almeno una terza squadra $c$ con cui $a$ ha perso e $b$ ha vinto.
Cordialmente, Alex
Se almeno due squadre ($a$ e $b$) sono a pari punti significa che se escludiamo il loro scontro diretto una delle due aveva un punto in meno dell'altra (Es. $a$ batte $b$ perciò se entrambe hanno finito a $k$ punti, escludendo il loro scontro, $a$ ha $k-1$ punti).
Se entrambe avessero fatto il medesimo risultato (vittoria o sconfitta che sia) con le altre allora non sarebbe possibile che finiscano con lo stesso punteggio, perciò esiste almeno una terza squadra $c$ con cui $a$ ha perso e $b$ ha vinto.
Cordialmente, Alex
Chiaro come la luce del sole ora grazie infinite.. era semplicissimo alla fine di tutto 
grazie infinite.. era semplicissimo alla fine di tutto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo