Sei amiche (Ada, Bea, Cleo, Dina, Eli, Fede) giocano spesso a tennis nel campetto del condominio dove abitano. Dato che la loro forma fisica varia nel tempo e non sempre possono esserci tutte, hanno ideato un metodo per stilare una classifica relativa che si aggiorna a ogni gara. Partendo dall’ultima partita giocata e andando a ritroso, si prepara un ordine parziale dato dalle partite giocate: se una di queste partite non è coerente con l’ordine finora trovato viene scartata perché rispecchia un momento passato. Per fare un esempio pratico, immaginiamo che ci siano solo quattro amiche e le partite giocate siano state nell’ordine le seguenti, dove le lettere corrispondono alle amiche e la prima nella coppia dica chi ha vinto: CD, CA, BD, BC, AB. Andando a ritroso, abbiamo le seguenti classifiche parziali: AB, ABC, la coppia ABC / ABD (non sappiamo ancora ordinare C e D), una partita non considerata perché A è davanti a C, ABCD. Supponiamo che la partita successiva sia B contro D; se B vince non succede nulla, se vince D passerà davanti a B e si ricalcolerà tutta la classifica.

Questo metodo di stabilire una gerarchia è forse un po’ scomodo, ma parrebbe abbastanza equo, oltre ad avere il vantaggio di essere indipendente dal numero di partite giocate. Ma esistono dei casi in cui a una delle amiche conviene perdere una partita per migliorare la propria posizione in graduatoria, come Stan Wagon ha mostrato in uno dei suoi Problem of the Week!

Immaginiamo che siano state giocate le seguenti partite, sempre con la stessa convenzione che la vincitrice è la prima indicata nella coppia: BC, FA, BD, AB, FD, DE, CD, CF, EF. Calcoliamo ora l’ordine, partendo sempre dall’ultima partita e indicando tra parentesi qual è la partita considerata:

• (EF) EF
• (CF) EF e CF
• (CD) EF, CF, CD
• (DE) CDEF
• (FD) partita scartata
• (AB) CDEF e AB
• (BD) CDEF e ABDEF
• (FA) partita scartata
• (BC) ABCDEF

Supponiamo ora che la partita successiva sia C contro E. Se C vince, la classifica rimane la stessa, e C resta terza. Cosa succede se E vince? La striscia di partite è ora BC, FA, BD, AB, FD, DE, CD, CF, EF, EC. Ricalcoliamo la classifica:

• (EC) EC
• (EF) EC e EF
• (CF) ECF
• (CD) ECD e ECF
• (DE) partita scartata
• (FD) ECFD
• (AB) ECFD e AB
• (BD) ECFD e ABD
• (FA) ECFABD

Come vedete, anche se Cleo ha perso è passata in seconda posizione! Meglio ancora: Fede, che era ultima in classifica e non ha giocato l’ultima partita, è balzata in terza posizione… Morale della favola: ogni classifica totale distorce i valori in campo, ma ce ne sono alcune che li distorcono di più!

(immagine di firkin, da OpenClipArt, CC0)

La scorsa settimana ho parlato del principio dei cassetti e vi ho lasciato tre problemi. Se non siete riusciti a risolverli ecco qua come si fa.

I 15 cavalieri della tavola rotonda hanno pasteggiato un po’ troppo prima di sedersi a discutere, e quando si sono seduti nessuno di essi era seduto al proprio posto. Dimostrate che è possibile ruotare la tavola in modo che ci siano almeno due persone al posto corretto.

Per ciascun cavaliere calcoliamo di quanti posti in senso orario è spostato rispetto alla posizione che dovrebbe avere. Visto che sappiamo che nessuno è al suo posto, a ciascuno di loro sarà assegnato un numero da 1 a 14. Ma i cavalieri sono 15: per il principio dei cassetti due cavalieri devono avere lo stesso numero. Basterà allora ruotare la tavola in senso antiorario di quel numero di posizioni perché loro due siano al loro posto.

Se scegliete sei numeri interi tra 1 e 999 ce ne saranno almeno due la cui differenza è un multiplo di 5.

In questo caso il 999 è una falsa pista: quello che conta è che i numeri sono interi. Calcolate i resti modulo 5 dei sei numeri: possono essere solo 0, 1, 2, 3 e 4. Essendoci sei numeri e cinque possibili resti, per il principio dei cassetti due di essi devono avere lo stesso resto, e quindi la loro differenza sarà un multiplo di 5.

Avete una bilancia a due piatti e 28 monete, una delle quali è più pesante delle altre. Dimostrate che non è possibile trovare quale sia la moneta più pesante con tre pesate.

In questo caso si usa il principio dei cassetti in una forma leggermente diversa da quella standard. Ogni pesata ha tre esiti possibili: il braccio sinistro è più pesante, il braccio destro è più pesante, la bilancia resta in equilibrio. Qualunque combinazione di monete si scelga di pesare ci sarà la possibilità che la moneta più pesante sia in un gruppo di almeno dieci monete; nell’ipotesi migliore 27 monete possono essere assegnate a nove a nove ai tre esiti, ma la ventottesima creerà un gruppo da 10. Con lo stesso ragionamento la seconda pesata lascerà la possibilità che la moneta più pesante sia in un gruppo da 4, ed evidentemente la terza pesata non potrà trovare con certezza la moneta pesante perché gli esiti possibili sono solo tre. Attenzione: questo ragionamento non dimostra che sia sempre possibile trovare la moneta pesante in un gruppo da 27 (nella pratica lo è, ma occorre trovare un modo per suddividere le possibilità in modo uniforme tra i tre esiti), ma è semplicemente una dimostrazione di impossibilità.

Ultimo aggiornamento: 2024-01-06 17:15