צילום: Roman Mager, Unsplash דרך Wikimedia Commons (CC0)

המורה בוחר שני מספרים שלמים, כל אחד מהם גדול מ-1, וסכומם אינו עולה על 100.

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

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

מר מכפלה: "אני לא יודע מהם שני המספרים."
מר סכום: "ידעתי שאתה לא יודע."
מר מכפלה: "אם כך - עכשיו אני כן יודע."
מר סכום: "ואם אתה יודע, אז גם אני יודע."

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

השאלה: מהם שני המספרים שהמורה בחר?

רמז דק

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

כלומר: אף אחד מהפירוקים האפשריים של הסכום שברשותו לא היה יכול לתת למר מכפלה תשובה מיידית. שאלו את עצמכם - מתי בכלל מר מכפלה יודע מיד?

רמז עבה

מר מכפלה יודע מיד כאשר המכפלה מתפרקת בדרך אחת בלבד לשני גורמים הגדולים מ-1 - למשל כשהמכפלה היא מכפלה של שני ראשוניים.

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

הרשימה מתחילה כך: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53 וכן הלאה.

פתרון

התשובה: 4 ו-13. הסכום הוא 17 והמכפלה היא 52.

שלב ראשון - מה מסגיר מר סכום

מר סכום מצהיר שהוא ידע מראש שמר מכפלה לא יודע. לכן הסכום שברשותו אינו סכום של שני ראשוניים, ומכאן שהוא אי-זוגי, ושהסכום פחות 2 הוא מספר פריק. הסכומים החשודים הם 11, 17, 23, 27, 29, 35, 37, 41, 47, 53 וכן הלאה.

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

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

ניקח את 52. הפירוקים האפשריים הם 2 × 26 (סכום 28) ו-4 × 13 (סכום 17). הסכום 28 זוגי ולכן פסול, ונשאר רק 17. מר מכפלה יודע: 4 ו-13.

שלב שלישי - ואיך מר סכום מסיים

מר סכום מחזיק ב-17. הוא עובר על כל הפירוקים שלו ובודק לגבי כל אחד אם מר מכפלה היה מצליח לדעת:

2 + 15, מכפלה 30 - מתפרקת גם ל-5 × 6 שסכומם 11, וגם 11 ברשימה. עדיין מעורפל.
3 + 14, מכפלה 42 - מתפרקת גם ל-2 × 21 שסכומם 23. עדיין מעורפל.
5 + 12, מכפלה 60 - מתפרקת גם ל-3 × 20 שסכומם 23. עדיין מעורפל.
6 + 11, מכפלה 66 - מתפרקת גם ל-2 × 33 שסכומם 35. עדיין מעורפל.
7 + 10, מכפלה 70 - מתפרקת גם ל-2 × 35 שסכומם 37. עדיין מעורפל.
8 + 9, מכפלה 72 - מתפרקת גם ל-3 × 24 שסכומם 27. עדיין מעורפל.
4 + 13, מכפלה 52 - הפירוק היחיד ששורד.

רק אפשרות אחת מאפשרת למר מכפלה להכריז שהוא יודע. לכן גם מר סכום יודע עכשיו: 4 ו-13.

קצת רקע

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

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