הפעם, כדי למנוע כל דליפה מהדיונים, התכנסה הוועדה למלחמה בד"ר לא במחסן סודי תת-קרקעי אי שם בארץ. אך יש להודות: המתדיינים היו מתוסכלים מאוד. לשאלה המרכזית – איך לתפוס את הדוקטור – לא נמצאה כל תשובה.
בשל מצב הרוח העגום החליט מתי מתוק להשתעשע ולשעשע את הנוכחים. "אין בעיה", אמר. "נתפוס אותו כמו שתופסים אריה".
"איך?" תמה פקד כהן.
"פשוט מאוד", ענה מתי. "נניח שאנו יודעים שהוא מסתובב בשטח שגודלו 1,000 ק"מ מרובע. מחלקים אותו לשני חלקים שווים של 500 קמ"ר. הוא צריך להימצא באחד מהם. ממשיכים לחלק בצורה הזו עשר פעמים ואז האריה חייב להימצא בקילומטר רבוע מסוים – ובעצם אפילו פחות, כי 2 בחזקת 10 הם 1024.
כיוון שכל עשר חלוקות מקטינות את השטח פי 1024, וקמ"ר הוא מיליון מטר מרובע, הרי אחרי עשרים חלוקות הוא יימצא בשטח של פחות מאלף מטרים מרובעים, כלומר פחות מדונם, ואחרי שלושים חלוקות הוא יימצא על פחות ממטר מרובע, ולכן יהיה חייב לעמוד על רגל אחת – שזה מעייף מאוד ולא יציב. לכן יהיה קל מאוד לתפוס אותו".
הנוכחים פרצו בצחוק אדיר. מששכך הצחוק שאל הפקד, "האם השיטה היא תמיד לחלק את האפשרויות לשתי קבוצות זהות?"
מתי הרהר וענה, "הדברים מורכבים יותר. ניקח דוגמה פשוטה. נניח שהאריה נמצא בשטח של 21 קמ"ר. אך 20 קמ"ר מהם הם מדבר, ובקילומטר אחד נמצאים נהר ועשב המושכים אליהם את הטרף. הסיכוי שהאריה יארוב שם גדול פי עשרה מאשר במדבר. איך הייתם 'מחלקים לשניים' את השטח כך שהסיכוי לפגוש את האריה יהיה זהה?"
לפני שהספיקו הנוכחים להגיב נשמע הקול המפורסם ביותר בארץ:
"שלום לידידיי. כאן מדבר האריה. לפני שאתם פותרים איך לתפוס אותי אני רוצה להציב בפניכם בעיה מתמטית, שהיא אגב גם בעיה של חיים ומוות: איך נמלטים אנשים מציפורניו של אריה?"
ואז נשמעה חבטה אדירה, דלת המחסן ננעלה, וד"ר לא פרץ בצחוקו הנורא ואמר, "אף שצחוקי דומה לצחוקו של צבוע, תגלו שאני אריה רב-חסד. במקום לטרוף אתכם אציב בפניכם מיד שורה של בעיות, שאם תפתרו אותן תוכלו להשתחרר. הבעיות עתיקות, אך הכנסתי בהן חידושים משלי.
בעיה ראשונה : בחרתי מספר, העליתי אותו בריבוע והוספתי 1. מהו המספר הקטן ביותר שאינו מחלק את התוצאה עבור כל מספר התחלתי שנבחר?"
בקהל הנדהם השתררה דממה, אך מתי ענה בשקט, "המספר הוא..." וציין את תשובתו.
"אתה במקרה צודק", אמר הדוקטור המאוכזב, "אבל זאת הייתה הקלה בבעיות. אם תגשו שמאלה תגלו מאזני כפות ולידם 13 מטבעות, 12 מהם שווים במשקלם ואחד שונה. עליכם לגלות את השונה במספר שקילות השוואה זהה למספר שפתר מתי, כי אחרי המספר הזה המאזניים יפסיקו לתפקד, ובלי המטבע השונה לא תיחלצו מפה לעולם!"
פקד כהן התבונן במאזניים וקבע, "כפי שאמר מתי, יש לחלק את האפשריות לשתיים. אמנם 13 לא מתחלק ב-2, אך הקרובה ביותר היא שקילה של 6 מול 6". הוא כמעט הטיל את המטבעות על המאזניים, אך מתי עצר אותו ברגע האחרון ואמר, "אמרתי שהדברים מסובכים יותר. לפני השקילות המטבע השונה יכול להיות כל אחד מ-13 המטבעות. כל שקילה מספקת לנו מידע נוסף ומצמצמת את מספר האפשרויות. לכל שקילה יכולות להיות תוצאות שונות ועלינו לבחור אותן כך שבכל תוצאה נוכל להישאר במסגרת מספר השקילות המותר.
לדוגמה, אנו יכולים להמר ולהשוות בין שני מטבעות מקריים בשקילה הראשונה. אם יהיה לנו מזל הם לא יהיו שווים, כלומר כל השאר תקינות. נשווה בשקילה השנייה בין אחד מהם לשני. אם גם הם לא יהיו שווים, הרי המטבע המקורי אינו תקין. אם יהיו שווים, אז זה המטבע שהשארנו בצד, וגילינו את המטבע בשתי שקילות. אך מה אם בשקילה הראשונה לא היה לנו מזל והמטבעות שבחרנו יהיו שווים ולכן תקינים? נישאר עם 11 מטבעות, ושאיבדנו שקילה אחת. האם זה נבון?
במקום להסתמך על המזל עלינו למצוא אסטרטגיה שבה כל תוצאה בכל שלב של שקילה תהיה פתירה במסגרת מספר השקילות המותר, ובאופן כללי אפשר לומר שנחפש אסטרטגיה שבה כל התוצאות האפשריות 'שקולות'.
במקרה שלנו, 'שקולות' פירושו: שלכל תוצאה יידרש מספר השקילות המותר (או פחות) עד לפתרון, אך אין פירושו שכל התוצאות נראות זהות. לדוגמה, שלושה מטבעות, כשידוע שאחד מהם הוא הכבד, שקולים לשני מטבעות שידוע שאחד מהם שונה (אך לא ידוע אם הוא כבד או קל) ועוד מטבע שלישי תקין. בשתי הקבוצות נדרשת שקילה יחידה כדי לגלות את המטבע השונה.
שתי הקבוצות אינן זהות מבחינת המידע שיש עליהן, ואף על פי כן הן שקולות מבחינת מספר השקילות הנדרש לגילוי המטבע השונה. אך אם נשנה את הדרישה מ"לגלות את השונה" ל"לגלות אם השונה הוא קל או כבד", נגלה שבקבוצה הראשונה די בשקילה אחת ואילו בשנייה אולי נזדקק לשתי שקילות. לכן, הקבוצות אינן שקולות לגבי הדרישה השנייה. כמו במקרה של האריה והנהר, אין אנו מחלקים לשתי קבוצות "זהות", אך הקבוצות שקולות מבחינת הסיכויים למצוא את האריה (או את המטבע השונה בהמשך)".
ותוך כדי הסבר ערך מתי את השקילות וזיהה את המטבע השונה במספר השקילות המותר.
"אוקיי", נשמע קולו של ד"ר לא, "במקרה הצלחת, כי זו בעיה קלה יחסית לעומת הבעיה הבאה. לכו אל הקצה הימני הרחוק של המחסן".
כל הוועד צעד ימינה ונעצר מול מאזני שקילה קטנים המורים את המשקל המדויק, ולידם עשרות שקיקים, המכילים 30 מטבעות כל אחד.
"לפניכם 105 שקיות של מטבעות", המשיך הדוקטור. "104 מהן מכילות מטבעות תקינים, ומשקל כל מטבע הוא 10 גרם. שקית אחת מכילה מטבעות זהים אך המשקל של כל אחד מהם שונה בגרם ממטבע תקין. כל מטבע כזה יפתח לכם את הדלת לחופש אם תשלשלו אותו בסדק שהתקנתי, אך אם תשלשלו מטבע רגיל, יתרחש פיצוץ אדיר, ואיני רוצה לפרט איך תיראו אחריו. הי הי. תוכלו לגלות את השקיק על ידי שקילות, אולם לצערי יש שתי מגבלות: האחת היא שהמאזניים אינם מסוגלים לשקול יותר מ-2,121 גרם, והשנייה היא שמספר השקילות הוא המספר הראשוני היחיד שאם תוסיפו אותו לראשוני אחר אתם עשויים לקבל מספר ראשוני אחר. ולהזכירכם, 1 אינו ראשוני!"
מתי שקע מעט בחישוביו, אחר חייך, ביצע את השקילות, מצא את השקיק השונה, הכניס מטבע לסדק והדלת נפתחה. מתי, שיצא אחרון, קרא בקול, "להתראות, אריה".
והדוקטור ענה, "בפעם הבאה – אטרוף!"
והשאלה הקבועה היא: איך פתר מתי את כל השאלות?
כרגיל ניעזר בסדרת שאלות, ופה ושם ברמזים.
שאלות
א. איך הייתם מחלקים את 21 הקילומטרים של האריה לשני אזורים שקולים מבחינת הסיכוי להימצאות האריה?
ב. לו היו לכם מטבע יחיד או שניים, כמה שקילות הייתם צריכים כדי לגלות במאזני השוואה מהו המטבע השונה? (שאלה מכשילה…)
ג. ולו היו שלושה מטבעות? וארבעה?
ד. ולו ידעתם אם המטבע כבד או קל מהאחרים, מהו מספר המטבעות המקסימלי שמתוכם הייתם מגלים בשקילה יחידה את המטבע השונה?
ה. לו היו לכם חמישה מטבעות שאחד מהם שונה, וכן שקית של מטבעות תקינים, לכמה שקילות הייתם נזקקים כדי לגלות את המטבע השונה?
ו. מהו מספר השקילות הראשון שגילה מתי? (נגלה לכם כי זה מספר השקילות הקטן ביותר הנדרש)?
ז. איך מצא מתי את המטבע השונה מתוך ה-13?
ח. מהו המספר הראשוני שהוא גם מספר השקילות השני?
ט. לו היו רק שלושה שקיקים, איך הייתם מגלים את השקית השונה בשקילה אחת? ( במאזני שקילה – לא במאזני השוואה).
י. מהו המספר המרבי של שקיקים שמתוכם ניתן לגלות בשקילה אחת את השקיק השונה? (אין לעבור על 2,121 גרם).
יא. ועתה, בעזרת פתרון בעיה י', נסו לפתור את הבעיה הקשה: איך אפשר לגלות במספר השקילות הדרוש את השקית השונה מבין 105 השקיות?
תשובות
א. ה"ערך" של קילומטר רבוע של נהר שווה לעשרה קילומטרים מדבריים, לכן אם נוסיף לו חמישה קמ"ר של מדבר יהיה ערכו 15 ויוותרו 15 מדבריים, כך ששתי התוצאות תהיינה שוות-ערך.
ב. לעולם לא היינו מגלים, כי אין מטבע תקין להשוואה.
ג. משלושה מטבעות אפשר לגלות את השונה בשתי שקילות לכל היותר: בראשונה משווים שני מטבעות, ואם הם שווים אזי השונה הוא המטבע השלישי וגילינו בשקילה אחת. אם המטבעות אינם שווים, משווים אחד מהם לשלישי, שכבר ידוע שהוא תקין. כשיש ארבעה, משווים שניים. אם הם אינם שווים, משווים אחד מהם למטבע תקין אחד משני הנותרים. אם הם שווים סימן ששניהם תקינים. משווים אחד מהם למטבע שלישי – אם אין שוויון, המטבע השלישי הוא השונה. אם יש – השונה הוא המטבע הרביעי.
ד. 3.
ה. שתי שקילות. בראשונה היינו משווים שלושה מטבעות לשלושה תקינים. אם הם היו שווים, היינו משווים את הרביעי למטבע תקין. אם היו שונים היינו יודעים שהשונה נמצא ביניהם ואם הוא קל או כבד. אז היינו משווים בין שני מטבעות ומגלים את הפתרון.
ו. המספר הוא 3. כל מספר - שאריתו מ-3 היא 0, 1 או 2. אם נעלה אותו בריבוע, שאריתו תהיה רק 0 או 1, כך שאם נוסיף 1 לתוצאה השארית תהיה 1 או 2, ולעולם לא 0, ולכן המספר אינו מתחלק בשלוש. אותו דבר נכון לעוד אינסוף מספרים, למשל 4, 6 ו-7, אך 3 הוא הקטן ביותר, כי כל אי-זוגי שמעלים בריבוע ומוסיפים לו 1 מתחלק בהכרח ב-2.
ז. נשווה ארבעה מטבעות עם ארבעה מטבעות אחרים. אם הם שווים, השונה נמצאת בחמשת הנותרים ואת זה כבר פתרנו בתשובה ה'. אם אינם שווים, ניטול שלושה מטבעות "כבדים" ושניים "קלים" ונשווה לחמישה תקינים. אם הם "כבדים", השונה נמצא בין השלושה. עכשיו נשווה בין שניים מהם. או שהכבד נמצא ביניהם או שהשונה הוא השלישי. אם הם קלים, המטבע הוא אחד מהשניים ועלינו להשוות אחד מהם למטבע תקין. לבסוף, אם החמישה תקינים, ניקח את ה"כבד" ואחד משני ה"קלים" שנותרו ונשווה לשניים תקינים. אם אינם שווים – נניח שהם "קלים" – הרי זה המטבע ה"קל". אם שווים – זה ה"קל" שנותר בצד.
ח. הראשוני היחיד האפשרי הוא 2, כי כל ראשוני אחר יהיה אי-זוגי, והסכום של שני אי-זוגיים הוא זוגי ולכן אינו ראשוני.
ט. ניטול מטבע אחד משקיק מס' 1, שניים משקיק 2, ושלושה משקיק 3. אילו כולם היו תקינים, המשקל שלהם היה צריך להיות 60 גרם. מידת הסטייה היא מספר השקיק. אם, למשל, הסטייה היא של שני גרם, סימן שגרמו לה שני מטבעות זהים ולכן זהו שקיק 2.
י. ראשית, מגבלת משקל של 2,121 גרם פירושה שאיננו יכולים לשים על המשקל יותר מ-211 מטבעות, כשמכל שקיק ניקח לכל היותר 11 מטבעות, או 210 מטבעות , ואז לא יותר מ-21 מטבעות מאותה שקית, פן נעבור על המשקל המקסימלי.
הפתרון הוא 21 שקיקים. נמספר אותם ואת מס' 21 נניח בצד. ניטול מטבע אחד משקיק מס' 1, שניים משקיק 2 וכו' – n מטבעות משקיק מס' n – וכך עד 20. לפי הנוסחה הידועה, יהיו לנו 210=21/2*20 מטבעות, ומשקלם המרבי הוא 2,120 גרם. לפי מידת הסטיה מ-2,100 נדע לזהות את השקיק השונה: אם הסטיה היא n, שקיק n הוא השונה. אם אין סטייה, השונה הוא השקיק ששמנו בצד!
יא. פתרונות ט' וי' מנחים אותנו לפתרון: לשקילה השנייה (האחרונה) עלינו להותיר 21 שקיות לכל היותר. לכן נשים בצד 21 שקיות, ולשקילה הראשונה נמספר את השקיות הנותרות מ-1 עד 84. מ-1 עד 21 ניטול מטבע מכל שקית, מ-22 עד 42 ניקח שני מטבעות מכל שקית, מ-43 עד 63 ניקח שלושה מכל שקית ומ-64 עד 84 ניקח ארבע מכל שקית.יהיו לנו בדיוק 210 מטבעות ולקחנו לכל היותר ארבעה מטבעות מכל שקית, לכן מידת הסטיה מ-2,100 גרם תורה לנו איזו מארבע הקבוצות כוללת את המטבע השונה! אם, למשל, המשקל יהיה 2,102 גרם, נדע שזו הקבוצה השניה: 42-22. אם המשקל יהיה 2,097 גרם, נדע שהשונה נמצא בקבוצה השלישית: 63-43. אם אין סטיה, השקיק השונה יהיה בין ה-21 שהשארנו בצד!
וכך, אחרי השקילה הראשונה, נותרנו עם 21 שקיות "חשודות" – חמישית מהמספר ההתחלתי! ואת ההמשך כבר פתרנו בשאלה י'!
הערה למתענינים: ניסוח מדויק הוא שאנו מחפשים אסטרטגיית שקילה כך שבמקרה הגרוע ביותר מספר השקילות יהיה הקטן ביותר האפשרי בהשוואה לאסטרטגיות אחרות. לכן אין הכרח שכל התוצאות האפשריות אחרי כל שקילה תהיינה "שוות", כלומר מספר שווה של שקילות הנדרש להשלמת הפתרון – אלא שהגרועה שבהן תהיה טובה או שווה לתוצאות הגרועות באסטרטגיות חליפיות.
לכן עלינו לתכנן אסטרטגיות שונות הנזקקות לאותו מספר שקילות במקרה הגרוע ביותר. השיקול לבחירה בכל אחת מהן תלוי במקרה כזה במידת יעילותן כאשר לא קורה הגרוע ביותר.
לעתים הבעיה היא שאין לנו מספיק שקילות לפתרון כשקורה הגרוע ביותר. איך עלינו לנהוג אז כדי שהסיכוי למציאת פתרון יהיה הגדול ביותר? זה נושא מרתק אך מורכב, ולא נדון בו הפעם.
אמנון זקוב
