Håndtrykk på fest – par
Det var fire ektepar på en fest. Mange håndhilste. Ingen håndhilste på ektefellen sin. En person, Sam, ble overrasket da Sam spurte de syv andre personene hvor mange håndhilste de hadde gjort – antallene på de syv håndtrykkene var forskjellige!
UTFORDRINGEN
Hvordan er dette mulig, og hvor mange håndtrykk gjorde Sams ektefelle?
Merknader
UTFORDRINGEN
Ingen håndhilste på seg selv, og hvis de ikke håndhilste på ektefellen, var det maksimale antallet for en person seks. Hvis de syv tellingene var forskjellige, måtte de være nøyaktig hele listen med tall fra 0 til 6.
Tenk deg personen med seks håndtrykk. De håndhilste på alles unntatt ektefellen. Sagt på en annen måte, vi vet at alle andre enn personens ektefelle hadde minst ett håndtrykk. Derfor måtte personen med 0 håndtrykk være gift med personen med seks håndtrykk!
Hvis du fjerner dette paret og håndtrykkene de var involvert i, sitter du igjen med tre ektepar, og hver av disse seks personene vil få håndtrykkantallet redusert med ett. Vi har nå et nytt problem som er veldig likt det opprinnelige. Disse tre parene vil ha håndtrykkantall som er nøyaktig listen med tall fra 0 til 4 (uten å liste Sams antall). Av samme grunner som før, kan vi være sikre på at personen med fire håndtrykk på denne listen (fem håndtrykk opprinnelig) er gift med personen med null håndtrykk på denne listen (ett håndtrykk opprinnelig).
Hvis vi gjentar denne logikken én gang til, kommer vi til konklusjonen at 6 og 0 er gift, 5 og 1 er gift, og 4 og 2 er gift. Den eneste gjenværende personen hadde 3 håndtrykk, og de må være gift med Sam!
Forresten, Sam hadde også tre håndhilsting (Sam håndhilste på 4, 5 og 6).