במרתף היין של המלך נמצאות 1,000 חביות. מתנקש החדיר רעל קטלני לאחת החביות - די בטיפה אחת מהרעל כדי להרוג את הקורבן בתוך 24 שעות. למלך יש 24 שעות בלבד לגלות את החבית המורעלת - ולשם כך הוא יכול לצוות על המשרתים שלו לשתות מהיין, ולבדוק מה מצבם כעבור יום - מהו המספר המינימלי של משרתים להם זקוק המלך על מנת לגלות את החבית המורעלת?
פתרון
|
10 משרתים. ניתן לייצג כל חבית באמצעות מספר בינארי בן 10 ספרות (יש 1,024 אפשרויות למספרים באורך זה). עשרת המשרתים מסתדרים בשורה, כך שכל משרת מייצג ספרה בינארית - כל משרת שותה מכל החביות שהוא משתתף בייצוג הבינארי שלהן. למשל - מחבית מספר 1 (ייצוג בינארי 0000000001) ישתה רק המשרת הראשון, ואילו מחבית מספר 341 (0101010101) ישתו המשרתים שמספרם 1,3,5,7,9. כעבור 24 שעות יבדוק המלך מי מהמשרתים נפגע מן הרעל - והחבית המורעלת היא זו שמספרה הבינארי מיוצג על ידי הספרות של המשרתים שנפגעו.
|
|