הצטרפות לדואר חשמלי | הסרת מנוי מדואר חשמלי | שלח מכתב | דף ראשי

פתרון החידה: האוטוסטראדה של גולדבך 16/06/2007 | גיליון מספר 94 | משה הלוי halemo פתרון מסלול הנסיעה באוטוסטראדה שבנה גולדבך החידה המקורית, כאן פתרון החידה: הנסיעה הלוך וחזור אפשרית ללא עצירה רק אם שני המסלולים הם שני מספרים ראשוניים שונים זה מזה. נסביר: כדי לייצג מספר M כלשהו בבסיס B כלשהו, יש לחלק את המספר M במספר B ולייצר את המספר המתאים לפי בסיס B על סמך השאריות שנותרו בחלוקה (חיבור השאריות מתבצע מלמטה למעלה). החלוקה הרקורסיבית מסתיימת כאשר התוצאה של החלוקה היא 0, עם שארית אחרונה כלשהי אשר מהווה את הספרה השמאלית ביותר של המספר החדש שנוצר בבסיס B. החלוקה הראשונה היא המספר M המחולק על ידי המספר B. השארית (הראשונה) של חלוקה זו היא ספרת האחדות. כדי שספרת האחדות תהיה שווה לאפס, B חייב להיות מחלק של המספר M. כלומר, כדי שהשארית תהיה שווה ל 0, המספר M חייב להיות פריק ולהתחלק ללא שארית על ידי המספר B. לעומת זאת, אם המספר M הוא ראשוני, תמיד תהיה שארית R שונה מאפס בחלוקה ל B. זה יקרה בכל B קטן מ M. נזכור שעל פי החידה, במסלול M, בקילומטר ה M, מוצב שלט עם הכיתוב X והמחסום תמיד פתוח, למרות ש M מחלק את M ושארית החלוקה היא אפס. כלומר, כדי שהנהג יצליח לנסוע נסיעה מלאה של הלוך וחזור באורך כולל של 2*N קילומטרים, הוא חייב לבחור שני מסלולים שונים, P ו Q, כאשר שניהם הם מספרים ראשוניים. בנסיעה על מסלול P או Q, לעולם הנהג לא יפגוש שלט עם מספר בבסיס כלשהו קטן מ N שספרת האחדות שלו היא אפס. לכן, בשום חלק של המסלול, המחסום לא יהיה סגור. הנהג יגיע בשלום לנקודה N בהלוך ויחזור לנקודה 0 בחזור. נסכם: נסיעה של הנהג על אוטוסטראדת גולדבך באורך N קילומטר, במסלולים P ו Q ראשוניים כלשהם, תאפשר נסיעה של 2*N קילומטרים ללא עצירות. האם החידה מזכירה למישהו את השערת גולדבך? ;-) אכן כן. אם היינו יוצרים פונקציה T (מלשון Travel) המקבלת כקלט את מספר המסלול M ומחזירה כפלט את המרחק (בקילומטרים) שיכול נהג לעבור במסלול זה עד לעצירה (במחסום סגור או בסוף המסלול), תוצאת החידה היתה חייבת למלא את התנאי הבא: 2*N = T(P) + T(Q) . כאשר P ו Q הם מספרי המסלולים והם מספרים ראשוניים. למי שלא זוכר, השערת גולדבך טוענת שכל מספר זוגי הוא חיבור של שני מספרים ראשוניים. 2*N = P + Q . את השערת גולדבך לא הצליחו להוכיח מעולם, אבל הרבה מתימטיקאים שהתעסקו וניסו להוכיח את ההשערה הזו, קיבלו תוצאות ביניים נחמדות. כמו החידה לעיל שמצא כותב שורות אלה...

תגובות הקוראים