החידה המתמטית הפשוטה - שאף מתמטיקאי לא הצליח לפתור (כבר 90 שנה)

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

שמה: השערת קולץ. המכונה גם "בעיית 3X+1". ואתם מוזמנים לנסות אותה עכשיו.

כלל אחד, שתי פעולות, אין מנוחה

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

ניסיון מהיר: התחילו עם 7. הוא אי-זוגי, אז 7×3+1 = 22. 22 זוגי, חלקו ב-2: 11. אי-זוגי: 11×3+1 = 34. חלקו ב-2: 17. ×3+1 = 52. חלקו ב-2: 26. חלקו ב-2: 13. ×3+1 = 40. חלקו ב-2: 20. חלקו ב-2: 10. חלקו ב-2: 5. ×3+1 = 16. חלקו ב-2: 8. חלקו ב-2: 4. חלקו ב-2: 2. חלקו ב-2: 1.

• חידת יום ההולדת של שריל: ואיך היא יכולה לעזור לכם לסגור עסקה מוצלחת
• יונים חכמות יותר ממתמטיקאים? המחקר שמוכיח שגם המומחים טועים
• המלצת המערכת: כל הכותרות 24/7

שבע הוביל לרצף של 16 שלבים לפני שהגיע ל-1. נסו 27 - תקבלו מסע מסחרר של 111 שלבים, שבמהלכו המספר מזנק עד 9,232 לפני שסוף סוף מתמוטט ל-1. הרצפים האלה קרויים "מספרי ברד" - hailstone numbers - כי הם עולים ויורדים בצורה כאוטית, בדיוק כמו גרגירי ברד שמיטלטלים בתוך ענן סערה לפני שנופלים ארצה.

לותר קולץ, 1937: הרגע שבו נולדה החידה

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

ההשערה נבדקה בעזרת מחשבים על כל המספרים הטבעיים עד 2.36×10²¹ - כלומר יותר מ-2 קווינטיליון מספרים - וכולם, בלי יוצא מן הכלל, הגיעו בסוף ל-1. אבל בדיקת מקרים, ולו טריליוני מקרים, איננה הוכחה מתמטית. ייתכן שקיים מספר גדול מאוד שמשגע את הכלל - מספר שרצפו נמלט לאינסוף ולא מגיע לעולם ל-1. אף אחד לא מצא כזה. אבל אף אחד לא הוכיח שאין כזה.

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

חידות מתמטיות נוספות:

שני מתמטיקאים שברו שיא בן 84 שנים בדרך לפתרון הבעיה הגדולה ביותר במתמטיקה

מיליון דולר לפתרון חידה של 160 שנה: משוואת נאוויה-סטוקס שמציקה למתמטיקאים הגדולים בעולם

פול ארדש: "המתמטיקה עוד לא בשלה לכך"

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

הפרס של 500 הדולר נשאר לא ממומש. ב-90 שנה שחלפו מאז נוסחה הבעיה, איש לא זכה בו.

המתמטיקאי הגדול בעולם ניסה - ויצא עם שני "כמעט"

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

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

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

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

מדוע זה כל כך קשה? ההסבר האינטואיטיבי

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

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

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

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

ג'פרי לגריאס, שכתב ספר שלם על הבעיה - "The Ultimate Challenge: The 3x+1 Problem" - הציע את הסיכום הכי עגום בנושא: "זהו בעיה קשה להפליא, שנמצאת מחוץ להישג ידה של המתמטיקה הנוכחית לחלוטין." אמר זאת ב-2010. מאז, למעט פריצת הדרך החלקית של טאו, לא השתנה הרבה.

האם הבעיה תיפתר אי פעם - ומה יקרה אם תיפתר?

יש שלוש אפשרויות לפתרון:

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

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

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

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

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