אלה הפתרונות לחידת "בום-שמום".
1. חידת השקילה
הפתרון אינו קשה, אך חשוב לדעת איך מגיעים אליו: בכל שקילת מאזניים אנו מחלקים את קבוצת הנשקלים לשלוש קבוצות משנה: כף ימין, כף שמאל ואלה שאינם נשקלים. הקבוצה האחרונה יכולה להיות ריקה. אם ידוע שיש מטבע קל אחד, כל שקילה מבהירה לנו בהכרח באיזו קבוצה המטבע נמצא, ולכן מספר המטבעות בשקילה אחרונה אינו יכול לעלות על 3, כי רק אז נוכל בשקילה אחת לגלות את הקל ביניהם. אם יש שלושה מטבעות או שניים, נשקול מטבע אחד בכל כף ונדע אם אחד מהם קל יותר או שמא הקל הוא השלישי, שאינו נשקל.
לכן עבור תשעה מטבעות נזדקק לשתי שקילות: הראשונה של שלושה מול שלושה, כך שנדע שהמטבע הקל נמצא בכף הקלה יותר או בקבוצת הבלתי נשקלים במקרה שהכפות תהיינה מאוזנות.
יש כמובן גם ברירה אחרת. יכולה לעלות ההצעה 'הבה נשקול ארבעה מול ארבעה, ואם הכפות ישתוו המטבע הקל הוא המטבע הבלתי נשקל ופתרנו את התעלומה בשקילה אחת, בעוד חלוקה של שלושה מול שלושה מחייבת תמיד שתי שקילות.
אך מה קורה אם יש רביעייה קלה? אז אולי נזדקק לשלוש שקילות אם נשווה זוגות! לכן, כשההוראה היא "המספר הקטן ביותר במקרה הגרוע ביותר", עלינו לבחור בדרך הראשונה. אולם אם נתונה לנו רק שקילה אחת, עלינו לחפש את השקילה בעלת ההסתברות הגבוהה ביותר להצליח, וכאן יש חישוב מפתיע: בחירה אחת היא לשקול ארבעה מול ארבעה, ואם ישתוו סימן שהמטבע הקל הוא זה שלא שקלנו. ההסתברות שנבחר להוציא דווקא אותו מהשקילה היא 1 ל-9 . אבל יש בחירה הרבה יותר טובה. אם נבחר זוג מטבעות מקרי ונשקול אותן זה מול זה, נוכל למצוא את המטבע הקל רק אם הוא כלול בזוג. יש שמונה זוגות כאלה בכל 9*8/2=36 הזוגות, כלומר הסתברות של 2 ל-9. ההסתברות כפולה!
2. ועתה לחידת ד"ר לא
תשובת ה"בום" הכללית נותנת לנו מידע רב. היא פירושה הוא "לא", אזי לא ייתכן שיש בקהל אנשים משני הסוגים, כי אז כל שקרן מתיחס לשאר שכולל לפחות דובר אמת אחד ולכן תשובת האמת לשאלה "האם כל השאר שקרנים" היא "לא", והשקרן היה חייב לענות "כן". מסקנה: אם "בום" היא "לא", מתקיים כי כל השקרמתים הם או שקרנים או דוברי אמת. (אפשרות א')
אם " בום" פירושו "כן", לא ייתכן שכולם שקרנים, כי אז כולם היו צריכים לענות "לא". לא ייתכן גם שיש לפחות שני דוברי אמת, כי כל אחד מהם היה כולל בשאר דובר אמת אחד לפחות ולכן היה עונה "לא" לשאלה "האם כל השאר שקרנים?" המסקנה: אם "בום" הוא "כן", מתקיים כי יש דובר אמת יחיד בין ה-1,026. (אפשרות ב')
כדי להכריע בין השניים יש לגלות מה פירושו של "בום" במספר השאלות הקטן ביותר. התשובות לשאלות אלה תהיינה "בום" או "שמום", ועלינו למצוא את הפתרון התואם לכל סדרת תשובות.
הפתרון שאני מציע הוא גרסה רב-שלבית ומסובכת של פתרון חידה עתיקה, ואשמח אם מישהו מהקוראים יגלה פתרון קצר יותר:
ראשית בוחרים שני שקרמתים אקראיים – א' וב' – ושואלים את א', "לו הייתי שואל את ב' האם 2+2=4 האם היה עונה 'כן'?" על כך, שני שקרנים או שני דוברי אמת חייבים לענות "כן", כי אמת על אמת או שקר על שקר הם אמת. ננתח את התשובות האפשריות.
אם קיבלנו "בום" לא תיתכן אפשרות א', כי פירושה הוא "לא". לכן אנו נמצאים בב', שפירושה "כן". וכיוון שזה דורש שניים מאותו סוג ובאפשרות ב' יכול להיות רק דובר אמת אחד, אזי א' וב' הם שני שקרנים.
עתה נותרו לנו עוד 1024 לזיהוי ונוכל לעשות זאת בעשר שאלות, אם נחלק את הנותרים בכל שלב לשתי קבוצות שוות. לדוגמה, בשלב הראשון נחלק לשתי קבוצות של 512 שקרמתים ונשאל את א' השקרן, "האם דובר האמת מצוי בקבוצה הראשונה?" מאחר שהוא ישקר, נדע היכן מצוי דובר האמת, נחצה את הקבוצה הזאת לשניים ונשאל את אותה שאלה שוב, וכך הלאה עד שבשאלה העשירית ייוותרו רק שניים ונגלה בה את דובר האמת. סך השאלות יהיה 11!
אנו יכולים כמובן להמר ולשאול את השקרמתים בזה אחר זה את השאלה המתמטית ולאתר במזל את דובר האמת בשאלה הראשונה, אך במקרה הגרוע ביותר נאתר אותו רק אחרי 1,023 שאלות מתמטיות, ובסך הכל 1,024 שאלות!
אם התשובה היא "שמום" פרושה לגבי אפשרות א' היא "כן", ולכן ייתכן שכולם שקרנים או שכולם דוברי אמת. לגבי ב' פירושה הוא "לא", וזה ייתכן רק אם השניים הם דובר אמת ושקרן, כי אמת על שקר או שקר על אמת היא שקר.
לכן יש שלוש אפשרויות: או שכולם שקרנים, או שכולם דוברי אמת, או שהנשאלים הם שקרן ודובר אמת, אך לא ידוע מי מהם הוא מי.
נשאל את א' ואת ב' את השאלה המתמטית. אם שניהם יענו את אותה התשובה, אזי אפשרות א' היא הנכונה ולכן אם התשובה היא "בום" – פירושה "לא", וכולם שקרנים. אם "שמום", כולם דוברי אמת. אם התשובות שונות, לפנינו שקרן ודובר האמת היחיד ואנו באפשרות ב'. לכן זה שענה "בום", שפירושו "כן", הוא דובר האמת היחיד. וכך נזהה את כולם בשלוש שאלות.
כיוון שעלינו לבחור במקרה הגרוע ביותר, התשובה היא 11.
והנה הפתרון בתרשים זרימה:
אמנון זקוב
