In azienda da me è appena finito l’annuale torneo di tennis, e mi hanno cooptato per stilare la classifica finale. A differenza dei tornei ufficiali, da noi per far giocare tutti a lungo hanno fatto un girone all’italiana (di sola andata, naturalmente). Guardando i tabellini, ho notato che tutti i partecipanti hanno vinto almeno una partita, al che ho commentato “Ma allora ci sono tre giocatori A, B, C dove A ha battuto B, B ha battuto C e C ha battuto A!” Come mai ne sono certo?
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p712.html; la risposta verrà postata lì il prossimo mercoledì. Problema dalle Irish Mathematical Olympiads, via Futility Closet; immagine da SVG Silh)
Ultimo aggiornamento: 2024-09-14 22:15
Sia dunque il numero di giocatori >= 4.
Poniamo per assurdo che, presi a caso tre giocatori, sia sempre vero che uno di loro batte gli altri due.
Ad esempio tra A, B e C sia A il più forte.
Scegliamo un quarto giocatore D e confrontiamolo con A. Le possibilità sono due:
1. Se A batte D, A batte tutti i giocatori dell’insieme {B, C, D}.
2. Se D batte A, considerato l’insieme {D, A, B}, D batte anche B (altrimenti c’è il circuito D->A->B->D, contraddizione). Analogamente D batte C.
Quindi D batte tutti i giocatori dell’insieme {A, B, C}.
In entrambi i casi, allargando l’insieme iniziale di 3 giocatori a uno di 4, è possibile individuare un giocatore più forte di tutti gli altri.
Iterando questo procedimento è possibile trovare il giocatore del torneo che batte tutti gli altri, cosa che è in contraddizione con l’ipotesi.
Più semplice.
Per assurdo sia falsa la tesi, cioè:
per ogni insieme T = {x, y, z} di tre giocatori, se x > y e y > z, z non batte mai x. Cioè necessariamente x > z.
Questa è la definizione di transitività. Per l’arbitrarietà di T come sottoinsieme dei giocatori del torneo, tutto il torneo è transitivo.
Poiché ogni giocatore gioca con tutti gli altri, la relazione “>” è (o, ponendo x x o x = y, può essere banalmente estesa a) una relazione d’ordine totale.
Essendo l’insieme finito c’è un elemento minimo, un giocatore che non ha mai vinto, contro l’ipotesi.
La pagina del quizzino non esiste.
Stavo mettendola su ora ed è saltato tutto :-(