צילום: State Government Photographer, Wikimedia Commons (CC0)

מרתף המלך מכיל אלף חביות יין, כולן נראות זהות. יומיים לפני המשתה הגדול מגיעה ידיעה מודיעינית: אחת מהחביות - ורק אחת - הורעלה. הרעל חסר טעם, חסר ריח ובלתי ניתן לזיהוי בבדיקה כימית, אבל יש לו תכונה אחת ידועה היטב: מי ששותה ממנו, ולו לגימה זעירה, קורס בדיוק עשרים וארבע שעות לאחר מכן. פחות מזה - שום סימן.

למלך נשארו בדיוק עשרים וארבע שעות עד המשתה. הוא רוצה לדעת איזו חבית מורעלת כדי לזרוק אותה ולהגיש את שאר תשע מאות תשעים ותשע. לרשותו טועמים שמוכנים לשתות, כל אחד מהם יכול ללגום מכמה חביות שירצה, וכל הלגימות נעשות באותו רגע - אין זמן לסבב שני.

השאלה: מהו מספר הטועמים הקטן ביותר שמבטיח זיהוי ודאי של החבית המורעלת - ואיך בדיוק מחלקים ביניהם את הלגימות?

רמז דק

אחרי עשרים וארבע שעות מתקבל מכל טועם מידע בינארי בלבד: הוא קרס או שלא. אם יש n טועמים, כמה תמונות מצב שונות אפשר לקבל בסך הכול - וכמה תשובות שונות אנחנו צריכים להבחין ביניהן?

רמז עבה

ממספרים את החביות מ-0 עד 999 וכותבים כל מספר בבסיס שתיים. עכשיו מצמידים לכל טועם ספרה בינארית אחת קבועה: הטועם הראשון אחראי לספרה הימנית ביותר, השני לזאת שלפניה וכן הלאה. מה צריך הטועם ה-i ללגום?

פתרון

די בעשרה טועמים.

הרעיון הוא שכל טועם הוא בעצם "נורית" שמדליקה או לא מדליקה. עשרה טועמים מייצרים 2 בחזקת 10, כלומר 1,024 תמונות מצב אפשריות - יותר מ-1,000, ולכן בעיקרון יש מספיק מקום לקודד כל חבית בנפרד. תשעה טועמים היו נותנים 512 אפשרויות בלבד, פחות מ-1,000, ולכן בהכרח שתי חביות שונות היו מייצרות בדיוק אותה תוצאה - ולא היה אפשר להבדיל ביניהן.

וכך בונים את זה בפועל: ממספרים את החביות מ-0 עד 999 וכותבים כל מספר בבסיס שתיים בעשר ספרות. הטועם מספר i (מ-1 עד 10) לוגם מכל חבית שבייצוג הבינארי שלה יש 1 במקום ה-i. למשל חבית 5 היא 0000000101, ולכן ילגמו ממנה הטועם הראשון והטועם השלישי בלבד.

למחרת מסתכלים מי קרס. רושמים 1 עבור כל טועם שקרס ו-0 עבור כל טועם שנשאר על רגליו, מסדרים את הספרות לפי מספרי הטועמים - ומקבלים ישירות את מספר החבית המורעלת בבסיס שתיים. אם, למשל, קרסו רק הטועמים 2 ו-5, הקוד הוא 0000010010, כלומר החבית מספר 18.

זאת אותה שיטה בדיוק שבה מחשבים מאתרים שגיאות ומעבירים מידע: כל שאלה של כן או לא היא ביט אחד, ו-n שאלות מקבילות מספיקות כדי להבחין בין 2 בחזקת n אפשרויות. במקרה שלנו עשר שאלות מספיקות בשביל אלף חביות - וגם בשביל 1,024.