חידת יום הולדת

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

הנה החידה בנוסח המקורי, ומייד אנסח אותה גם בעברית:ובכן, אלברט וברנרד פגשו זה עתה את שריל (באנגלית הם מייצגים את האותיות A,B,C, ובעברית כל זה מתחרבש עם שריל) והם רוצים לדעת מתי יום הולדתה. היא נותנת להם רשימה אפשרית של עשרה תאריכים, וכמו כן מספרת לאלברט בסוד את החודש ולברנרד בסוד את היום בחודש (ואני מניח באופן מובלע שאלברט יודע שברנרד שמע מה היום בחודש, וברנרד יודע שאלברט יודע מה החודש).

התאריכים הם:

• מאי 15, מאי 16, מאי 19.
• יוני 17, יוני 18.
• יולי 14, יולי 16.
• אוגוסט 14, אוגוסט 15, אוגוסט 17.

כעת מתנהל השיח המוזר הבא:

• אלברט: איני יודע מתי יום הולדתה של שריל, אבל אני יודע שגם ברנרד אינו יודע.
• ברנרד: קודם באמת לא ידעתי מתי יום הולדתה של שריל, אבל עכשיו אני יודע!
• אלברט: אז גם אני יודע!

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

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

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

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

	מאי 15	מאי 16			מאי 19
			יוני 17	יוני 18
יולי 14		יולי 16
אוגוסט 14	אוגוסט 15		אוגוסט 17

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

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

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

הקלף המנצח עבורנו הוא השורה השלישית בדיאלוג - אלברט אומר שעכשיו הוא יודע בודאות מתי יום ההולדת. איזה מידע יש לאלברט שאין לנו? את החודש, כמובן. עכשיו, אם החודש היה אוגוסט, אז אלברט היה בבעיה כי עדיין היו לו שני ימים פוטנציאליים לבחור ביניהם (או ה-15 או ה-17). מכאן שהחודש אינו אוגוסט אלא יולי, ולכן יום ההולדת של שריל הוא ה-16 ביולי. זה מסיים את החידה.

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