מספרים עולים ויורדים

הבעיה הבאה, שהומצאה על ידי לותָר קולָץ (Lothar Kollatz) הגרמני ב-1937, היא משחק “סולמות וחבלים” מתמטי. עולים ויורדים בסדרה, על פי הכלל הבא: כשמגיעים למספר זוגי מחלקים אותו ב-2; כשמגיעים למספר אי זוגי כופלים אותו ב-3 ומוסיפים 1. נניח, כדוגמה, שמתחילים מ-10. מכיוון ש-10 זוגי, עלינו לחלקו ב-2. התוצאה, 5, אינה זוגית, ועל כן יש לכפול אותה ב-3 ולהוסיף 1. הגענו ל-16, שהוא זוגי, ועל כן נחלקו ב-2. הסדרה המתקבלת היא:\(10,5,16,8,4,2,1\). אם מתחילים מ-100 מקבלים את הסדרה:

\(100,50,25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1\)

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

מדוע אם כן מאמינים בכל זאת בהשערה? יש סיבה “היוריסטית”, כלומר לא מדויקת, להאמין בנכונותה. הסיבה היא שיש יותר “חבלים” מאשר “סולמות”. אומנם, הסולמות ארוכים יותר, משום שכאשר עולים כופלים ב-3, ומוסיפים 1, בעוד שכאשר יורדים מחלקים רק ב-2. אולם כנראה מספר הירידות גדול יותר, משום שלאחר כל עלייה באה ירידה. עלייה מתרחשת כשמגיעים למספר אי זוגי; אבל כפל מספר אי זוגי ב-3 נותן מספר אי זוגי, ולאחר הוספת 1 מתקבל מספר זוגי, שבו על פי הכלל יורדים. הנחה שאין לה הוכחה אבל הכול מאמינים בה היא שלאחר כל ירידה יש עדיין סיכוי של 50% לרדת שוב, ואחר כך שוב סיכוי של 50% לרדת, וכן הלאה. אם אומנם כך הוא, קל להראות שעל כל עליה (שהיא בערך פי 3) יורדים בממוצע פי 4. כלומר בממוצע יורדים יותר מאשר עולים, כך שבסופו של דבר חייבים להגיע ל-1.

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

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

6 תגובות על מספרים עולים ויורדים

  • מאת עמי סגל‏:

    מספרים עולים ויורדים: 1. בשתי הדוגמאות חסר 8 אחרי 16. 2. בדוגמא של 100: אחרי 13 צריכים להגיע ל 40 (ולא כרשום ל 30).
    לכן, עשרת המספרים מ 30 עד 80 אינם “שייכים” לסדרה של 100. בברכה, עמי סגל

  • מאת רון אהרוני‏:

    נכון, ננסה לתקן

  • מאת יוסי כהן‏:

    תודה רבה. נתקן בהמשך היום.

  • מאת גיל‏:

    מעניין

  • מאת יהושפט גבעון‏:

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