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

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

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

אפשר לעשות זאת – זה לא ספוילר, כך בחידה המקורית – באמצעות 18 ערכי מטבעות שונים: 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90. זה נותן לנו בעצם את כל שילובי ה"אחדות" ו"עשרות" בין 1 ל-99 כולל, וכדי להגיע לסכום 100 פשוט לוקחים את 10 ו-90, או 20 ו-80 וכן הלאה. כמובן, יש בין הצירופים האפשריים המון כפילויות. אז הנה האתגר האמתי: מהו המספר המינימלי של ערכי מטבעות שעדיין יקיים את הדרישה, ומהם הערכים האלה?

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

הכיוון השני שעלה בדעתי – פשוט כי זה משהו שאני יודע לחשב – היה לבדוק מהו המינימום האבסולוטי. כלומר, כמה ערכי מטבעות שונים אצטרך כדי להבטיח מאה או יותר צירופים שונים, בלי להיכנס עדיין לשאלה האם הצירופים האלה מכסים את טווח הערכים 1-100 או לא. החישוב הוא כזה: אם יש לי N ערכי מטבעות, אני יכול להפיק מהם את N הערכים של המטבעות עצמן (למשל, אם יש מטבע בערך 8, אני יכול לקחת אחת כזו ולקבל את הערך 8), וכן את N הערכים של זוגות זהים (8+8=16). בנוסף, יש לי N-כפול-(N מינוס 1) צירופים של שתי מטבעות עם ערכים שונים, אך את המספר הזה צריך לחלק בשניים – כי הערך של 4+5, לדוגמה, זהה לערך של 5+4. אחרי קצת סידור, הנוסחה המתקבלת היא

2*N + (N^2 – N)/2

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

בשלב זה נתקעתי. כל כיוון מחשבתי חדש שניסיתי התגלה כמבוי סתום. הפתרון לא קשור לייצוג בינארי, לא להשערת גולדבך, ואפילו לא לבנייה הדרגתית (מתחילים מ-1, ממפים את כל האופציות [1 ו-2], מוסיפים את המספר הבא שחסר [3, שאיתו האופציות הן 1,2,3,4,6], ואז את החסר הבא [5] וכן הלאה). טבלאות ושרטוטים שונים, שבהם ניסיתי למפות את הבעיה למשהו מרחבי, גם לא הועילו – בין אם בגלל שזו לא גישה טובה או סתם כי לא מצאתי את הייצוג הנכון. נשאר לי רק המחשב.

במחשב הבעיה קיבלה צורה אחרת לגמרי. להפיק סדרות של 13-17 מטבעות בכל הערכים השונים בין 1-100, ולבדוק אם סדרה מקיימת את התנאי של החידה, זה קל, אבל אם ננסה לעבור על כל האפשרויות בלי אופטימיזציה זה ייקח אלפי שנים. איפה אפשר לקצץ?

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

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

ההגבלות האלה חוסכות המון חישובים, אבל לא מספיק – לפחות אם אתם רוצים תוצאות באותו יום. מקום נוסף לבצע בו אופטימיזציות הוא הבדיקה של כל סדרת מטבעות. הגישה הנאיבית תהיה לעבור על כל הסכומים מ-1 עד 100 (או, אם נעבוד חכם קצת יותר, 100 עד 4), לחפש לכל אחד צירוף מטבעות מתאים בסדרה הנתונה, ולנטוש את הלולאה אם התגלה סכום שאי אפשר לממש. גיליתי שאם בונים מערך צירופי סכומים תוך כדי בניית הסדרה עצמה, ומשנים כל פעם רק את האלמנטים שרלוונטיים לשינוי בסדרה (לא ניכנס לפרטים המדויקים כאן), הבדיקה הסופית יכולה להתבצע בפקודת if אחת, והזמן הכולל קצר הרבה יותר. כך יכולתי לבדוק די בקלות עד לאילו סכומים מגיעות סדרות של 10, 11 או 12 מטבעות, ואפילו לראות שאין פתרון עם 13 ערכים. אבל הבדיקה של 14 עדיין הייתה ממושכת מדי לטעמי.

אגב, מהתבוננות בתוצאות ההן, היה ברור שהכיוון לפתרון לא מבוסס על מרווחים שווים, כפולות, חזקות או כל דבר מובן-מאליו כזה. אפילו תוספת הטווח שמתקבלת מכל ערך מטבע נוסף לא הייתה אחידה. היה איזה אלמנט אחר ניתן לזיהוי, אך לא מספיק מובחן כדי שאבין איך בדיוק הוא עובד ואיך ליצור על בסיסו את התשובה לחידה. עם זאת, היו שני דברים מעניינים שראיתי. אחד, הערך הגבוה ביותר בסדרה "טובה" היה תמיד זהה או קרוב מאוד לחצי של הסכום המקסימלי המבוקש. למשל, בסדרה של 12 מטבעות שיכולה לכסות את הסכומים 1-64, הערך הגבוה היה 32 ולא, נניח, 50 או 61. שנית, ככל שהתקדמתי במספר ערכי המטבעות, הסדרות ה"טובות" התכנסו לשתיים או שלוש תת-סדרות קבועות בהתחלה, בחמשת הערכים הראשונים.

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

בשלב זה הייתי עייף ומרוצה מספיק כדי לגשת, סוף כל סוף, לפרק התשובות בספר. הסתבר שחצי מהתשובה שלי היה נכון – 16 הוא אכן המינימום – והחצי השני היה נכון למחצה – גיליתי את הסדרה שיכולה להגיע עד 100, אבל יש סדרה אחרת, שמתחילה אחרת, שמגיעה עד 104! ומה שהכי מתסכל, לא הוצע שם שום הסבר…

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