Quizzino della domenica: Multilingue

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.


discussione
(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.)

Un pensiero su “Quizzino della domenica: Multilingue

  1. LightKnight
    Spoiler
    La condizione sui tre delegati è equivalente a dire che, presi tre delegati qualunque A, B, C, almeno due delle tre coppie (A,B), (A,C), (B,C) si comprendono. Ad esempio, se (A,B) e (B,C) si comprendono, B può fare da interprete fra A e C.

    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…

I commenti sono chiusi.