שלום לכם,

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

24 שעות לפני המשתה התגלה לו שאחת החביות הורעלה (העניין עדיין בחקירה ואיננו רשאים למסור פרטים עליה). נודע גם שהרעל משפיע בתוך 24 שעות. הקיסר החליט להשתמש בעכברי מעבדה כדי שיטעמו מהיין וכך יגלה איזו חבית היא החבית המורעלת (ידוע שעכבר שיטעם מחבית מורעלת ימות).

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

ועכשיו השאלה מופנית אליכם, קוראים יקרים: מהו מספר העכברים הנמוך ביותר שבעזרתם יוכל הקיסר רפיק למצוא את החבית הנגועה ולהציל את אורחיו מהרעלה?

תודה רבה לניצן מקרני שומרון על הרעיון לחידה.


אילוסטרציה: Shutterstock

סקובידו



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

36 תגובות

  • איתי

    1

    יעביר בין החביות עד שבאחת מין החביות לא ישרוד העכבר וזאת החבית המורעלת

  • עטרה

    חידת המשך

    העכברים שהגיעו מהמעבדה היו חמודים מאוד, והקיסר לא רצה שימותו.
    הקיסר ראה, שאם מספר החביות הוא חזקה שלמה של 2, כלומר N=2^E, אז תוחלת מספר העכברים המתים היא roundup(log2(N))/2=E/2, ואין אפשרות להקטין את התוחלת. אבל לקיסר היו 1000 חביות, ולא חזקה שלמה של 2.
    באיזה אופן הקיסר יכול להקטין את תוחלת מספר העכברים המתים, בלי לשנות את מספר העכברים שבודקים את החביות?

  • רמי

    תוחלת מוקטנת

    מתוך 1024 המספרים שניתן לתת לחביות יש אפשרות לגמישות של 24 מהם.
    לא נשתמש במספר 1023 שביצוג הבינארי שלו יש 10 אחדים.
    לא נשתמש בכל המספרים שביצוג הבינארי שלהם יש 0 אחד בלבד (9 אחדים). יש 10 מספרים כאלה.
    לא נשתמש בחלק מהמספרים שביצוג הבינארי שלהם יש שני אפסים בלבד (8 אחדים). יש 45 מספרים כאלה. נוותר על 13 מהם. כך שבסה"כ ניפטר מ 24 מספרים שמעלים את התוחלת.
    חישוב מראה כי כעת, לאחר הסרת המספרים מרובי האחדים, תוחלת מספר העכברים המתים ירדה מ 5 ל 4.916 .

  • רמי

    חידת הרחבה : עכברים רגישים

    כל עכברי המעבדה שהמלך קיבל היו רגישים יותר ממה שחשב. נאמר לו שעכבר שיטעם מהחבית המורעלת ימות בתוך 12 שעות (ולא 24 שעות).
    המלך, שזה עתה סיים תואר במתמטיקה, שיער שניתן להקטין (יחסית ל 24 שעות) את כמות העכברים לבדיקת 1000 החביות.

    - האמנם ניתן למצוא את החבית המורעלת בפחות עכברים מאשר במצב בו העכברים פחות רגישים (ומתים תוך 24 שעות)?
    - ואם כן, כמה עכברים נדרשים למציאה? מהו התהליך למציאה?

  • עטרה

    פתרון

    דרושים 9 עכברים רגישים.
    התהליך: בשלב א, בודקים 9^2=512 חביות בשיטה הרגילה. אם יש עכבר או עכברים שמתו, אז יודעים מה החבית המורעלת. אם כל העכברים נשארו חיים, אז החבית המורעלת היא מבין 1000-512 החביות שנותרו, או שהיא החבית בעלת אינדקס 0, שאף עכבר לא טעם ממנה. לכן, בשלב ב, יש לבדוק 1000-512+1=489 חביות, וניתן לבצע זאת על ידי 9 עכברים.
    הערות:
    א) אי אפשר לחסוך עכברים במקרה שמספר כל החביות הוא חזקה שלמה של 2.
    ב) אי אפשר לחסוך עכברים במקרה שמספר החביות המורעלות גדול מ-1 או שאינו ידוע.

  • רמי

    יפה אך יש פתרון טוב יותר

    יש לי אלגוריתם (אפילו שניים) שמאפשר בדיקה עם פחות מ 9 עכברים.

  • עטרה

    דרושים 7 עכברים

    נגדיר את הפונקציה הבאה:
    (sum_choose(n,k
    sum_choose=0
    choose=1
    for i=1 to k
    choose=choose*(1+n-i)/i
    sum_choose=sum_choose+choose
    נשים לב לכך שמונה הלולאה הראשון הוא 1 ולא 0.

    כעת נגדיר את הפונקציה הבאה:
    המשתנה m מציין את המספר ההתחלתי של העכברים.
    המשתנה t מציין את מספר הבדיקות שעורכים העכברים.
    (casks_number(t,m
    if (t casks_number=0
    else if (t==1) then
    casks_number=2^m
    else
    casks_number=0
    for d=1 to m
    (small_sets_number=sum_choose(m,d
    (small_sets_size=casks_number(t-1,m-d
    (large_sets_size=casks_number(t-1,m
    c=small_sets_number*small_sets_size+1*large_sets_size
    (casks_number=max(casks_number,c

    בחידה של רמי, העכברים מתים תוך 12 שעות, ויש 24 שעות עד המשתה, ולכן t=2. מתקיים casks_number(2,7)>1000. לכן, עבור 1000 חביות, דרושים 7 עכברים.

  • רמי

    הפתרון שלי

    אני מצאתי מספר פתרונות עם 8 עכברים (המינימום שלי).
    למשל ע"י הפעולות הבאות:
    חלוקת החביות ל 8 קבוצות של 109 חביות בקבוצה ועוד קבוצה תשיעית של 128 חביות.
    בשלב הראשון כל עכבר מה 8 מקבל לטעום את 109 החביות שלו.
    אם אחד מהעכברים מת, שאר 7 העכברים יכולים לבדוק את 109 החביות בבדיקה אחת (אי אפשר בפחות מ 7).
    אם כולם חיים, 7 מהם בודקים את ה 128 הנותרים.

    להלן חישוב עבור מקסימום חביות ש 8 עכברים יכולים לבדוק בשיטה שלי : 8x128+128=1152
    להלן חישוב עבור מקסימום חביות ש 7 עכברים יכולים לבדוק בשיטה שלי : 7x64+64=512

    התוכנית שלך מאוד יפה, אך לא מסתדר שגם 7 (שלך) וגם 8 (שלי) מובילים לתשובה המינימלית. כדאי לבדוק שוב את התוכנה ולוודא תקינות מצידה ו/או למצוא טעות בפתרון שלי , ו/או למצוא פתרון אחר.

  • רמי

    תיקון מקסימום

    להלן חישוב מתוקן עבור מקסימום חביות ש 8 עכברים יכולים לבדוק בשיטה שלי : 8x128+256=1280
    להלן חישוב מתוקן עבור מקסימום חביות ש 7 עכברים יכולים לבדוק בשיטה שלי : 7x64+128=576

  • עטרה

    השיטה שלי

    מקסימום חביות ש 7 עכברים יכולים לבדוק בשיטה שלי : 63x16+128=1136

    תהא S קבוצת המספרים הטבעיים, שמספר הספרות בייצוג הבינארי שלהם הוא לכל היותר 7, וסכום הספרות בייצוג הבינארי שלהם הוא בין 1 ל 3.
    נניח שיש 1136 חביות. לוקחים 1008 חביות, ומחלקים אותן ל 63 קבוצות. נותנים לכל אחת מהקבוצות האלו אינדקס מתוך הקבוצה S.
    בשלב הראשון, כל עכבר i טועם את כל החביות השייכות לקבוצות שהספרה ה i בייצוג הבינארי של האינדקסים שלהן היא 1.
    בשלב זה מספר העכברים המתים הוא לכל היותר 3, ולכן מספר העכברים החיים הוא לכל הפחות 4.
    אם מתו עכברים בשלב הראשון, אז יש קבוצה בגודל 16 שהחבית המורעלת שייכת אליה, וניתן למצוא את החבית על ידי 4 עכברים.
    אם לא מתו עכברים בשלב הראשון, אז נשארו 7 עכברים חיים, וניתן לבדוק בעזרתם עוד 128 חביות.
    לכן, בשני שלבים וב 7 עכברים ניתן לבדוק 63x16+128=1136 חביות.

  • יונתן

    יש לי פתרון עם עכבר אחד!

    אני אסביר את זה על 7 עכברים למרות שטכנית אפשר גם עם אחד.
    בודקים עם שבעת העכברים את 128 הבקבוקים הראשונים ומחקים שעה.
    כעבור שעה בודקים את 128 הבקבוקים הבאים עם אותם עכברים, כעבור שעה שוב, ושוב עד שעוברים על כל הראשרויות (8 פעמים).
    אם עכבר(ים) מת אחרי 12 שעות בודקים איזה בקבוק מתאים בבדיקה הראשונה, אם עכבר(ים) מת כעבור 13 שעות הולכים לבדיקה השנייה וכו'.
    טכנית עכבר אחד יכול לטעום מכל הבקבוקים בהפרש של כמה שניות, אבל יש להניח שהרעל לא מדויק עד רמה של שניות.

  • רמי

    עכבר אחד

    נכון. אם דיוק הרעל הוא לעשריות השניה, עכבר אחד יכול לטעום מכל אחת מהחביות, בהפרש של 3.6 שניות בין חבית לחבית , ועל פי שניית מותו ניתן לזהות את החבית המורעלת.
    כמובן שיש הבדל בין טעימת מעט חביות לטעימת 1000 חביות.
    העכבר עלול למות מטביעה לפני שימות מהרעל (:

  • רמי

    נפלא. תשובה נהדרת!!

    נהניתי לקרוא את תשובתך.
    פתרון מרשים.
    התוכנה אכן עושה את העבודה.

  • עדי

    אני חושבת שאני יודעת את הפיתרון..

    נכון הוא גילה שיש חבית מורעלת 24 שעות לפני המשתה?ונכון שעד שהרעל יפעל יקח 24 שעות?אז בעצם עד שידעו את תוצאות הבדיקה המשתה כבר יתחיל ולכן אין טעם לבדוק איזה חבית מורעלת ועדיף להזמין חביות חדשות..צדקתי?

  • adam

    ???

    גם העכבר לוקח לו 24 שעות למות אם שתה מהיין המורעל ??
    אם הוא מת מיד אז הוא ישתמש ב עכבר 1

  • רמי

    ראה הבהרות ב־א', 10.11.2013 , 20:33.

    תשובה יפה למקרה של מוות מידי.
    במקרה שלנו העכברים מתים 24 שעות לאחר טעימת היין המורעל.

  • מומחה מצוות מכון דוידסוןפזיה

    רמז

    מספרים בינאריים

  • טל

    30

    10 לכל מימד של קוביה

  • מומחה מצוות מכון דוידסוןפזיה

  • שי

    אפשרות לפתרון תוך 72 שעות

    עם 30 עכברים. הרעיון הוא כזה: לוקחים 10 עכברים ונותנים להם לטעום מ-100 חביות כל אחד. לאחר 24 שעות (כאשר אחד העכברים מת) משאירים בבדיקה רק את אותן 100 החביות שמהן טעם העכבר שמת. כעת חוזרים על תהליך זה עוד פעמיים: עם 100 החביות שנשארו (כל עכבר כעת טועם רק מ-10 חביות), ואז את אותו התהליך עם 10 החביות שנשארו (כל עכבר כעת טועם מחבית אחד בלבד). החבית שממנה טעם העכבר שמת בפעם האחרונה של התהליך היא החבית המורעלת. אך כמובן שבדרך הזו נגיע לתוצאה רק לאחר 72 שעות, ואם זו הדרך שבה יבחר הקיסר, כנראה שהוא יאלץ לדחות את המסיבה ביומיים...

  • מומחה מצוות מכון דוידסוןפזיה

    :-)

    פתרון חמוד, אבל הקיסר רפיק רוצה לעמוד בזמנים....
    ואפשר לעשות זאת, ואפילו עם פחות עכברים!

  • עטרה

    הערה

    בשיטה שלך דרושים 12 עכברים, כי אפשר להשתמש שוב באלו שנשארו חיים.

  • רמי

    פתרון ל 10 חביות

    לכל היותר 4 עכברים לבדיקת 10 חביות בשיטה הבאה:

    עכבר 1 יטעם מחביות 1,5,6,7
    עכבר 2 יטעם מחביות 2,5,8,9
    עכבר 3 יטעם מחביות 3,6,8
    עכבר 4 יטעם מחביות 4,7,9

    העכברים שימותו ואלו שיחיו יסמנו איזו מהחביות מורעלת ואילו לא:
    רק עכבר 1 ימות : חבית 1 מורעלת
    עכברים 1+2 בלבד : חבית 5 מורעלת
    וכו'...

  • עטרה

    פתרון אופטימלי

    נראה לי שהפתרון שלך הוא אופטימלי, ומספר העכברים הוא roundup (log2 (N.
    יש שיטה יותר נוחה להתאים בין העכברים והחביות.

    פתרתי חידה קודמת שלך (עם התפלגות נורמלית) אבל יש לי בעיות עם המחשב אז עזבתי את זה בינתיים.

  • מומחה מצוות מכון דוידסוןפזיה

    נכון

    מספר העכברים הוא roundup (log2 (N.
    עכשיו הסבירו איך.....

  • רמי

    הסבר

    כמו בדוגמא שלי, אסביר עבור 10 חביות. נסמן אותן מ 1 ועד 10.
    נסתכל על המספרים הבינאריים השווים למספרים העשרוניים מ 1 ועד 10 :

    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1011

    יש 4 עמודות (אחת לכל עכבר).
    כל עמודה יש אפסים ואחדים. 1 מציין שהעכבר טועם מחבית שבשורה שלה האחד נמצא.
    למשל בשורה שלישית המספר 0011. עכברים 1 ו 2 יטעמו יין מחבית שלישית.
    לא צריך לבדוק חבית אחרונה. אם 3 העכברים יישארו בחיים, החבית האחרונה מורעלת.
    מסקנה : מספיק 3 עכברים לבדיקת 10 חביות!!

    עבור 1000 חביות מספיקים 9 עכברים למציאת החבית המורעלת.
    חישוב : כי 10^2=1024>1000 ומפחיתים 1 מ 10 9=10-1
    (חבית אחרונה לא צריך לבדוק).

  • עדי

    קשר

    לא הבנתי מה הקשר בין הרעיון שהדגמת עם הטבלה, לפתרון שלך ולשימוש ב-3 עכברים הרי קודם השתמשת ב-4

  • רמי

    פתרון טוב יותר

    פשוט מצאתי פתרון כמו שהצעתי אך מעט טוב יותר.
    בפתרון הראשון שלי חלקתי את החביות לטעימה בצורה בינארית.
    בפתרון האחרון ראיתי כי את החבית האחרונה לא חייבים לבדוק ולכן צומצם הפתרון ב 1 .
    אם נשתמש בנוסחה של עטרה: שיפרתי ממספר עכברים ( roundup (log2 (N למספר roundup (log2 (N))-1

  • עטרה

    לא מדויק

    יש טעות בחישוב שלך. החסרת 1 ממספר העכברים, ולא ממספר החביות.
    בנוסף, העובדה שחבית אחת אינה נבדקת, אינה משנה את מספר העכברים.
    ניתן לתת לחבית זו את האינדקס 0, ואז ממילא כל הביטים שלה הם 0, ואף עכבר לא צריך לטעום אותה.
    זה מתאים לנוסחה ((roundup (log2 (N.
    קל לראות זאת אם בודקים מה קורה כאשר מספר החביות קרוב לחזקה שלמה של 2.
    למשל, עבור 15 או 16 חביות דרושים 4 עכברים, ואילו עבור 17 חביות דרושים 5 עכברים.

  • רמי

    את צודקת. טעיתי ב"פתרון טוב יותר".

    לא ניתן להוריד עכבר מהמינימום האפשרי.
    והפתרון המינימלי הוא ((roundup (log2 (N.

  • עדי

    פתרון שקפץ לי לראש

    אפשר לתת רק ל999 עכברים לשתות בקבוקים אם כולם חיים אז הבקבוק שלא שתו היא המורעל. אני די בטוח שיש פתרון יותר טוב מזה

    נ.ב. בכלל לא שמתי לב לשינוי מבקבוקים לחביות

    נ.נ.ב. בשביל מה שמים את השאלה המתמטית פה, במקום הקפצ'ה שמגן מרובוטים שיענו?

  • מומחה מצוות מכון דוידסוןפזיה

    אכן

    אכן יש פיתרון טוב מזה

  • רחל ורמשטיין

    פתרון לחידת החביות המורעלות

    הקיסר הז
    מין בקבוקים ולא חביות כך שאין קשר בין היין שהזמין בבקבוקים להרעלת החביות
    לא צריך עכברים

  • מומחה מצוות מכון דוידסוןפזיה

    הוא הזמין חביות

    זאת הייתה טעות בשאלה

  • רמי

    שאלות הבהרה

    מה הקשר בין חבית יין לבקבוק יין?
    האם עכבר שטועם יין מורעל מת מייד או לאחר 24 שעות?

  • מומחה מצוות מכון דוידסוןפזיה

    הבהרות

    המלך הזמין חביות יין, אבל אפשר להשתמש בבקבוקים כדי ליצור ערבוב בין יינות מחביות שונות.
    העכבר מת לאחר 24 שעות.
    זמן הערבוב והשתייה של היין הוא זניח ואפשר להתעלם מזה.