כל אדם נורמלי הישן שנת ישרים היה יוצא מכליו אם לפתע פתאום היה מתפרץ צלצול טלפון פראי לתוך חלומו המתוק – ובאמת מה פלא שמתי זעק לשפופרת בזעם, "מי זה?!"

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

מתי חש חרטה עמוקה על תגובתו, "אני מתלבש ובא מיד!" אמר.

"אין צורך להתלבש!" השיב הפקד. "נהפוך הוא – ככל שתשכב יותר במיטה כך תיטיב להבין את עוצמת אסוני!"

"אינני מבין", השיב מתי, מבולבל מעט.

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

"סלח לי", אמר מתי בזהירות, חרד לשפיותו של ידידו. "מתי כל זה אירע?"

הפקד השתהה מעט, בוודאי כדי להציץ בשעונו. "לפני כשעתיים".

יש להזעיק אמבולנס במהירות, הרהר מתי, ואת הפקד שאל בעדינות, "נו, ואיך אילת?"

"שום אילת!" זעם הפקד. "אני מסתכל מהמטוס למטה – איזה יופי: ים תכול, אלמוגים, הרים, ג'ונגלים..."

"אם זיכרוני אינו מטעני אין ג'ונגלים באילת", העיר מתי, מאוד בזהירות.

"אתה לא מקשיב", רתח הפקד, "שום אילת! זה אי קסום באוקיינוס השקט!"

מתי החליט לעשות ניסיון אחרון להחזיר את ידידו לעולם השפיות בטרם יאושפז. "אלברט ידידי, אתה טוען שאתה בפיג'מה – "

"מה רע בפיג'מה?" תמה הפקד.

"במטוס ריק?"

"זה אמצע הלילה – לא היו עוד נוסעים".

"שטס לאוקיינוס במקום לאילת?"

"מה הבעיה לשנות יעד?"

"הבעיה היא שבמציאות אי אפשר להגיע בתוך שעתיים לאי שמרוחק 12 שעות טיסה!"

"אני מסכים שבמציאות לא. אבל בחלום?"

השתררה דממה.

"אתה מתאר לי חלום?"


"כל ילד יכול להבין את זה. מה קרה לך, מתי? פעם היית יותר אינטליגנטי!"

מתי החליט לבלוע את העלבון. "אז חלמת הלילה שאתה טס לאי קסום באוקיינוס. מה הקשר לד"ר לא? ובעיקר למה הערת אותי?!"

"תיארתי רק את תחילת החלום. ההמשך שלו מדהים! המטוס נוחת ואני רואה כאלף ילידים יושבים במעגל כמצפים לבואי. אני שואל את הטייס, 'איפה אנחנו? דומני שזו לא ממש אילת?' והוא עונה, 'לא ממש... אנו בשקרמתיה, אי השקרנים ודוברי האמת' ופורץ בצחוק. את הצחוק הזה אזהה תמיד, ישן או ער: הטייס הוא ד"ר לא!
היה לי ברור שנקלעתי לצרות איומות! ואכן הוא חייך אלי בידידות ואמר, 'ועכשיו, ברשותך, אטוס מכאן ואתה תוכל להפוך לשקרמתי לנצח'.
אני מודה שלרגע התפתיתי: חולות זהובים, ים אזמרגד, אלמוגים, דגים טרופיים ודקלי קוקוס – אבל מי יילחם בד"ר לא אם אשכב פה לנצח על הגב ואשוחח עם שקרנים? פניתי אליו ואמרתי, 'אוקיי, מה המבחן שיקנה לי כרטיס חזרה?'
הלה ענה, 'תחילה עליך לשאול שאלה אחידה את כל השקרמתים'.
בלי לאבד זמן ובלי לחשוב שאלתי, 'האם כל שאר האנשים במעגל הם שקרנים?'
ואז רעמה תשובת כולם יחדיו, 'בום!'

"מעוצמת הרעש התעלפתי, וכשחזרתי להכרתי הסביר לי הדוקטור, 'בשקרמתית, במקום "כן" ו"לא" הם אומרים "בום" ו"שמום", אבל מי מהשניים הוא "כן" ומי "לא" – זהו סוד כמוס! ועתה – למשימה שלך: אם ברצונך לחזור אי פעם למשפחתך, למולדתך, לבית אביך ולוועד למלחמה בי, עליך לגלות, במספר השאלות האישיות הקטן ביותר גם במקרה הגרוע ביותר, מי כל אחד מ-1,026 השקרמתים: השקרן הוא או דובר אמת'.
חרדה גדולה ירדה עלי: הרי כדי לפענח כל שקרמת בנפרד נדרשת לפחות שאלה אחת, כלומר לפחות 1026 ומי יודע אם לא הרבה יותר, ומנין אדע שזה המספר הקטן ביותר. ובכלל, מה פירוש 'במקרה הגרוע  ביותר'? וכך, מרוב בהלה שמא לא אראה שוב את פניך – התעוררתי ומיד התקשרתי כדי שתציל אותי".

מתי חייך ואמר בנועם, "אבל עתה, משהתעוררת, שוב אינך בשקרמתיה. אין בעיה!"

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

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

פקד כהן חשב וחישב ופתר את בעית השקילה.

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

ואכן, החידה נפתרה. ההוכחה? הפקד נמצא בבוקר נוחר במיטתו.

איך? זה האתגר שלכם!

שאלות

1)    מהו פתרון בעית השקילה?

2)    מה מספר השאלות האישיות הקטן ביותר שמבטיח זיהוי של כל אחד מ-1026 השקרמתיים?

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

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

איננו מתחילים מאפס – קיבלנו את תשובת ה"בום" מ-1,026 המשתתפים.
מה אפשר ללמוד מהתשובה הזאת על הרכב השקרמתים?
א) מהן האפשרויות  אם "בום" הוא "כן"?
ב) מהן האפשרויות אם  "בום" הוא "לא"?
ג) לאחר שענינו על א' וב', היש דרך יעילה יותר לזיהוי אישי מאשר לשאול כל שקרמת בנפרד?

בהצלחה!

אמנון זקוב

9 תגובות

  • עידו

    קצת באיחור- הרחבה לחידה ופיתרון...

    לצערי נתקלתי באוצר החידות של אתרכם רק עכשיו. מצאתי פיתרון אשר מאפשר הרחבת החידה. לצערי הרב הבנתי שלמחבר החידה פיתרון זה לא יגיע, אבל אולי לאחרים...
    ההרחבה היא שמקום 1026 שקרמתים יש 2046. ואני רוצה להציע פיתרון ב-11 שאלות (כמו לחידה המקורית).
    ראשית כל נבחין, כמו בפתרון המקורי, שיש 3 אפשרויות-
    א. כולם דוברי אמת ובום=לא
    ב. כולם דוברי שקר ובום=לא,
    ג. דובר אמת אחד והשאר דוברי שקר ובום=כן. אפשרות זו כוללת בתוכה למעשה 2046 אפשרויות שונות.
    סה"כ 2048 אפשרויות, המקסימום שניתן לפתור ב-11 שאלות של כן/לא (או בום שמום במקרה שלנו).
    ניתן להבחין שאפשרות ג' (דובר אמת אחד) היא עיקר המשקל כאן. לכן ננסה להניח שהיא האפשרות הנכונה, לפתורה באמצעות חיפוש בינרי, ועל הדרך לאמת או להפריך הנחה זאת.

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

    בהתחלה נשאל את הנציג את השאלה על קבוצה של 1022 איש, לא כולל הנציג.

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

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

    לסיכום, אם קיבלנו בום אז או שיש דובר אמת אחד מחוץ לקבוצה (ולא זה ששאלנו אותו), כלומר 1023 איש, או שכולם דוברי אמת. סה"כ 1024 אפשרויות.
    אם קיבלנו שמום אז או שיש דובר אמת אחד בקבוצה ששאלנו אליה (1022), או שזה שאנחנו שואלים אותו הוא דובר אמת, או שכולם דוברי שקר. סה"כ 1024 אפשרויות.

    אפשרות א- תשובת בום לשאלה הראשונה:
    יש לנו 1023 חשודים, שזה 2 בעשירית פחות 1. נמשיך בביצוע חיפוש בינארי בקבוצה. נשאל כל פעם על קבוצה המהווה חצי מה"חשודים" הנתורים שהיא חזקה של 2 את שאלת הבסיס (למשל בהתחלה על 512). תשובת שמום תשאיר אותנו רק עם הקבוצה עליה שאלנו כחשודים, ומה שנשאר הוא חיפוש בינארי רגיל. תשובת בום תחזיר אותנו ל 2 בתשיעית פחות אחד חשודים ואופצייה שכולם דוברי אמת. נמשיך באותה דרך עד שנקבל תשובת שמום או שנגיע לבסוף, לאחר 10 שאלות לחשוד אחד או האפשרות שכולם דוברי אמת. במצב זה אנו יודעים בוודאות שהחשוד האחד דובר אמת, לכן נשאל אותו אם השמים כחולים. אם יענה בום הרי שבום=כן והוא דובר האמת היחידי. אם יענה שמום כולם דוברי אמת.

    אפשרות ב- תשובת שמום לשאלה הראשונה:
    יש לנו 1022 חשודים- 2 בעשירית פחות 2. נמשיך בחיפוש בינארי בקבוצה. נשאל כל פעם על קבוצה המהווה חצי מה"חשודים" הנתורים שהיא חזקה של 2 פחות 2 את שאלת הבסיס (למשל בהתחלה על 510). תשובת בום תשאיר אותנו רק עם הקבוצה עליה לא שאלנו הפעם כחשודים (חזקה של 2), ומה שנשאר הוא חיפוש בינארי רגיל. תשובת שמום תחזיר אותנו ל 2 בתשיעית פחות שנים חשודים, ואופצייה שכולם דוברי שקר, או שהנציג הוא דובר האמת היחידי. נמשיך באותה דרך עד שנקבל תשובת בום או שנגיע לבסוף, לאחר 9 שאלות לשני חשודים, האפשרות שכולם דוברי שקר, והאפשרות שהנציג דובר האמת היחידי. נשאל את הנציג האם השמים הם כחולים. אם הוא דובר אמת היחידי תשובתו תהיה שמום. אם כולם שקרנים תשובתו תהיה שמום גם כן. אם אחד מהשניים דובר אמת תשובתו תהיה בום.
    אם ענה בום ההמשך ברור.
    אם הוא ענה שמום כל אחד חוץ ממנו שקרן. נשאל מישהו אחר האם השמים כחולים ונדע איזה מהמצבים לפנינו.

  • dr krembo

    bum shmum

    11
    Either there is exactly one lier and then bum=yes or none and then bum=no
    Form two groups of 512 people and two observers.
    Ask observer one if there is a lier in group1 and then observer two.
    If you get a different answer, then its one of them, we will get back to this case.
    If both said bum, we should assume there is a lier in group1. If they say shmum, then in group2.
    Now that we know that the observers are telling the truth, we can reuse one of the for the next binary search iteration in the same manner. It will take 11 questions in total.
    Going back, if observers give a different answer, one of them is the lier. Just ask one of them a general question like is it snowing, bum=he is the lier, shmum=the other observer.

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

    מעולה! :-)

    הפתרון נכון ומלא.
    היום אפרסם אותו.

  • dr krembo

    coins problem

    Can be solved in 3 iterations in worst case.
    Can actually solve it for 15 coins in 3 iterations.

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

    כמעט

    2 שקילות יספיקו. ראה את הפתרון שיתפרסם היום.

  • עדי

    ניחוש

    אולי צרך 12 שאלות?

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

    קרוב, אבל מספיק פחות

    11 שקילות יספיקו. ראי את הפתרון שיתפרסם היום.

  • עדי

    בום שמום

    בום זה כן אם יש דובר אמת אחד והשאר שקרנים ובום זה לא אם כולם שקרנים

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

    כמעט...

    "בום" יכול להיות גם "לא" אם כולם דוברי אמת.
    אבל לא סיימת: עכשיו, מה כדאי לשאול כדי לגלות איזו אפשרות נכונה ומי דובר אמת ומי דובר שקר?