Puzzelen met tuinslangen

X en Y zijn twee getallen tussen de 1 en 36. Alice weet alleen de waarde van X, en Bob weet alleen de waarde van Y. Ze willen erachter komen of X en Y gelijk zijn.

Tussen hen in liggen acht buizen. Daarnaast hebben ze stukken tuinslang waarmee ze uiteindes, aan hun eigen kant, van deze buizen onderling met elkaar kunnen verbinden. Alice heeft ook een waterkraan die ze kan verbinden met één van de buizen.

Wanneer Alice en Bob de buizen met elkaar verbonden hebben, zet Alice de waterkraan aan. Het water zal dan ergens uit een buis stromen.

Als X gelijk is aan Y, moet het water uit de kant van Alice stromen, en anders aan de kant van Bob.

Hoe moeten Alice en Bob de tuinslangen aansluiten, afhankelijk van X en Y, zodat dit altijd goed gebeurt?

Stel dat we de acht buizen de namen geven A, B, C, D, E, F, G, H, en de waterkraan K noemen, is dit een voorbeeld oplossing voor vier mogelijkheden (in plaats van 36):

Alice doet:
Bij invoer 1 verbindt ze KA, DE
Bij invoer 2, KA, CE
Bij invoer 3, KB, DE
Bij invoer 4, KB, CE

Bob's strategie:
Bij invoer 1 verbindt hij aan zijn kant A met C
Bij invoer 2, AD
Bij invoer 3, BC
Bij invoer 4, BD

Hint voor de puzzel: Lukt het om zes mogelijkheden te doen met de eerste vier buizen?

Dit tuinslangmodel is voor het eerst voorgesteld in de publicatie The Garden-Hose Model van Harry Buhrman, Serge Fehr, Christian Schaffner en Florian Speelman als manier om protocollen voor kwantumcryptografie te bestuderen. Nieuwe inzichten over deze puzzel zouden daarbij kunnen helpen!