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…

    Rispondi

Rispondi

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.