Alla conferenza Wikimania ci sono 1000 partecipanti di varie nazioni. Presi tre delegati a caso, possono parlarsi tra di loro, anche se può darsi che uno debba fare da interprete per gli altri due. Dimostrate che tutti i delegati possono essere ospitati in camere doppie in modo che i due occupanti possano comprendersi a vicenda.
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p703.html; la risposta verrà postata lì il prossimo mercoledì. Problema da D.O. Shklyarsky, N.N. Chentsov, and I.M. Yaglom, Selected Problems and Theorems in Elementary Mathematics, via Futility Closet; immagine da SVG Silh.)
Prendiamo quattro delegati, A, B, C, D. Supponiamo, senza perdita di generalità, che fra A, B e C le coppie che si comprendono siano (A,B) e (B,C). Prendiamo ora la terna A, C, D: se (A,D) si comprendono, allora le due doppie possono essere (A,D) e (B,C); altrimenti (A,C) e (C,D) devono comprendersi e le due doppie possono essere (A,B) e (C,D).
Così abbiamo alloggiato un quartetto di delegati. Si vede facilmente che in questo modo si può alloggiare un qualunque numero di delegati multiplo di 4, quindi anche 1000=250×4.
Rimane aperto il problema di alloggiare un numero di delegati congruo a 2 modulo 4, nonché di alloggiarne un numero dispari (ammettendo una singola o una tripla).
Ovviamente si può riformulare il problema nel linguaggio della teoria dei grafi, ma non sono abbastanza bravo…