Þú ert með lykla að þrennum dyrum, $A,B$ og $C$, í höndunum, en veist ekki hvaða lykill gengur að hvaða dyrum. Þú vilt prófa lyklana til að geta merkt þá rétt. Hver er minnsti fjöldi tilrauna sem þú getur fyrirfram sagt með vissu að dugi til að komast að því hvernig á að merkja lyklana, óháð því hvernig einstaka tilraunir fara?
Lausn
Svar : $3$
Lausn : Byrjum á að athuga hvað við þyrftum margar tilraunir ef lyklarnir væru tveir og tvennar dyr, merktar með $A$ og $B$. Byrjum á að prófa annan lykilinn á dyrum $A$. Ef þær ljúkast upp, þá getum við merkt lykilinn sem við prófuðum með $A$ og hinn með $B$. Ef fyrsta prófunin gengur ekki, þá vitum við að lykillinn sem við prófuðum gengur að dyrum $B$ og hinn gengur að $A$. Því dugar ein prófun ef lyklarnir eru tveir og dyrnar aðeins tvær.
Snúum okkur nú að verkefninu í dæminu þar sem lyklarnir eru þrír og dyrnar þrjár. Prófum fyrsta lykilinn á dyrum $A$. Ef það gengur þá getum við merkt fyrsta lykilinn og við eru með tvo lykla og tvennar dyr fyrir framan okkur og við vitum að þá dugar ein tilraun. Í þessu tilfelli komumst við því af með tvær tilraunir.
Gerum nú ráð fyrir að fyrsti lykillinn sem við prófum gangi ekki að dyrum $A$. Prófum hann þá á dyrum $B$. Ef hann gengur að dyrum $B$ þá erum við aftur komin í þá stöðu að hafa tvo lykla og tvennar dyr. Því dugar ein tilraun í viðbót. Allt í allt þurftum við þrjár tilraunir.
Ef aftur á móti lykillinn gengur ekki heldur að dyrum $B$, þá getum við verið viss, án þess að prófa, að hann gengur að dyrum $C$. Nú höfum við tvo lykla eftir sem ganga að dyrum $A$ og $B$. Okkur dugar ein tilraun til að finna út að hvaða dyrum hvor lyklanna gengur. Aftur höfum við notað þrjár tilraunir.
Við getum þá verið viss um að þrjár tilraunir duga. Tvær tilraunir duga hins vegar ekki. Ef við prófum tvo lykla á sömu dyrunum og hvorugur gengur, þá vitum við að þriðji lykillinn gengur að þeim og við höfum tvo lykla og tvær dyr eftir en ekki fleiri tilraunir.