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

חידה: האוטוסטראדה של גולדבך 16/06/2007 | גיליון מספר 94 | משה הלוי halemo בממלכת המתימטיקה החליטו יום אחד לבנות אוטוסטראדה גדולה, כדי שהמתימטיקאים תושבי הממלכה יוכלו לעבור מקצה לקצה. לשם העבודה נשכר המהנדס הראשי של הממלכה, כריסטיאן גולדבך. עזרו לנהגים למצוא את דרכם אל האינסוף. בממלכת המתימטיקה החליטו יום אחד לבנות אוטוסטראדה גדולה, כדי שהמתימטיקאים תושבי הממלכה יוכלו לעבור מקצה לקצה. המהנדס הראשי של הממלכה, כריסטיאן גולדבך, החליט שאורכה של האוטוסטראדה יהיה N קילומטרים. בכל קילומטר של כל מסלול החליט המהנדס לשים שלט וכן מחסום בעל שני מצבים: פתוח או סגור. כדי שלא תיווצר צפיצות בנסיעה, החליט המהנדס לבנות N מסלולי נסיעה מקביליים. כל מסלול M מסומן במספר 1 עד N בהתאם למיקומו הסידורי. בכל מסלול M כלשהו, נקודת 0 היא נקודת ההתחלה, נקודה 1 היא הקילומטר הראשון במסלול, נקודה 2 היא הקילומטר השני במסלול ואילו נקודה N היא הקילומטר ה N של המסלול. כלומר, האוטוסטראדה היא פסודו-ריבועית כאשר אורכה הוא N (קילומטר), וברוחבה יש N מסלולי נסיעה, ממסלול 1 ועד מסלול N. הנסיעה במסלול 1 אסורה וסגורה מטעמים מתימטיים, אבל הנסיעה מותרת בכל מסלול שמספרו 2 עד N. כדי שלא ישעמם לנהגים וכדי שלא ישכחו על איזה מסלול הם נוסעים כרגע, החליט מהנדס הממלכה לשים בכל קילומטר שלט ובו יצוין באיזה מסלול מצוי כרגע הנהג: למשל, אם הנהג נוסע על מסלול 5, כל השלטים במסלול בכל קילומטר יציינו את המספר 5, אבל בבסיס מספרי שנקבע על פי הקילומטר הנוכחי שבו נמצא כרגע הנהג (אפשר להניח שבשלט ייכתב גם מספר הבסיס לחישוב). תנאי נוסף שהכניס המהנדס הוא שבכל קילומטר M במסלול M, יהיה שלט שיכיל את הכיתוב X, כלומר ללא ציון מספר. למשל, במסלול נסיעה מספר 7, בקילומטר ה 7 לא יהיה שלט המכיל מספר, אלא שלט המכיל את הכיתוב X. במקום שנמצא השלט עם הכיתוב X, המחסום יהיה פתוח ויאפשר להמשיך בנסיעה (מה שאומר ששלט עם הכיתוב 10 בבסיס כלשהו, אף פעם לא יוצב על המסלול). דוגמה: נהג נוסע במסלול מספר 5. בקילומטר ה 2, השלט יכתב בבסיס בינארי, הוא בסיס 2. כאשר הנהג יחלוף על פני הקילומטר השני, הוא יראה את המספר 101 שמציין את המספר 5 בבסיס 2. כאשר הנהג יחלוף על פני הקילומטר השלישי, הוא יראה שלט עם המספר 12 המציין את המספר העשרוני 5 בייצוג בבסיס 3. כאשר הנהג יחלוף על פני הקילומטר הרביעי, הוא יראה שלט עם המספר 11 המציין את המספר העשרוני 5 בייצוג בבסיס 4. כאשר הנהג יחלוף על פני הקילומטר החמישי, הוא יראה שלט עם הכיתוב X במקום עם המספר 10 (המציין את המספר העשרוני 5 בייצוג בבסיס 5). בהמשך הנסיעה הוא כל הזמן יראה שלט עם המספר 5, מכיוון שבכל בסיס גדול מ 5, המספר העשרוני 5 ייכתב כ 5. דוגמה נוספת: אם הנהג יבחר לנסוע במסלול מספר 10 (בבסיס עשרוני), הוא יראה את כל השלטים מציינים את המספר 10, כאשר כל שלט ייציין את המספר 10 בבסיס המתאים לפי הקילומטר שבו נמצא הנהג: למשל, בקילומטר ה 5 במסלול מספר 10 יראה הנהג את המספר 20 (בבסיס 5) שמציין בעצם את המספר 10 בבסיס עשרוני. אם הנהג ימשיך לנסוע במסלול מספר 10, הוא יראה בקילומטר ה 16 את השלט ובו כתוב המספר A, שמציין בבסיס הקסאדצימלי את המספר 10. בבסיס 16, הספרה A מציינת את המספר 10. למי שלא זוכר, המספר F מציין בבסיס 16 את המספר 15. המספר 10 בבסיס 16 מציין את המספר 16 בבסיס עשרוני. מכיוון שיש N מסלולים, הרי במסלול N יהיו N שלטים בבסיסים קטנים מ N, כאשר בכל קילומטר יהיה שלט המציין את המספר N בבסיס מספרי לפי הקילומטר שבו נמצא כרגע הנהג. בבסיס N עצמו יהיו N סימנים, כאשר 10 הסימנים הראשונים הן הספרות העשרוניות הראשונות (0 עד 9), וכל שאר הסימנים הם אותיות וכיוצא בזה. בכל מקרה, אף סימן שונה מאפס, אינו נחשב אפס. ועוד תנאי עם המחסומים שהכניס המהנדס: הנסיעה מקצה לקצה, כלומר מנקודת ההתחלה 0 עד נקודה N, תסתיים רק אם בדרך לא ייעצר הנהג על ידי מחסום שנמצא בכל קילומטר, ופועל על פי הכלל הבא: אם הספרה הימנית ביותר במספר המצויין בשלט היא אפס (0), המחסום סגור והנהג לא יכול להמשיך לנקודה N. אם המספר בשלט אינו מכיל את הספרה אפס (0) בספרה הכי פחות משמעותית (כלומר הספרה הימנית ביותר במספר, היא ספרת האחדות), המחסום פתוח והנהג יכול להמשיך בנסיעתו עד לקילומטר הבא, שם שוב יהיה מחסום פתוח או סגור לפי התנאים לעיל. כלומר, כדי להשלים נסיעה מלאה על המסלול M, בלי להעצר באף מחסום סגור, לאף שלט שנמצא על הדרך וכתוב בבסיס B, כאשר B מציין את מספר הקילומטר שבו מצוי הנהג, אסור שיהיה כתוב מספר באותו בסיס בספרת האחדות - אפס (0). יש לזכור שבקילומטר M במסלול M, תמיד יהיה שלט המכיל את הכיתוב X והמחסום יהיה במצב פתוח ויאפשר המשך נסיעה. דוגמה: ניתן להבין מכך למשל שנסיעה במסלול מספר 2 היא אפשרית לכל אורכה עד לנקודה N, מכיוון שבקילומטר השני יוצב השלט X, ובשאר חלקי המסלול יהיה שלט שבו כתוב 2, תמיד. המספר 2 בכל בסיס מספרי הגדול מ 2 תמיד יהיה 2. עוד דוגמה: נסיעה במסלול מספר 16 לא תעצר בקילומטר ה 16, מכיוון שבנקודה זו יהיה השלט עם הכיתוב X והמחסום יהיה פתוח. לעומת זאת, בהמשך הנסיעה, בקילומטר ה 32, יהיה שלט ובו המספר 20 בבסיס הקסאדצימלי, ולכן המחסום יהיה סגור (כי יש אפס בספרת האחדות) ולא ניתן יהיה להמשיך בנסיעה. דוגמה כללית: בנסיעה במסלול M, אסור שהמספר M בכל בסיס B (שמציין את הקילומטר שבו מצוי הנהג כרגע) יכיל בספרת האחדות שלו את הספרה אפס (0). כדי להשלים נסיעה מלאה עד לקילומטר ה N, כל השלטים במסלול הנסיעה, חייבים שלא להכיל את הספרה אפס בספרת האחדות (הספרה הימנית ביותר במספר). ועכשיו לחידה: על כל נהג בממלכת המתימטיקה הוטלה המשימה הבאה: לנסוע מנקודת ההתחלה 0 עד לנקודה N בכל מסלול נסיעה שיבחר מ 2 עד N, ולחזור בחזרה מנקודה N לנקודת ההתחלה, כך שלמעשה יבצע נסיעה הלוך וחזור שאורכה 2*N קילומטר. אבל, תנאי נוסף הוא שאסור לנהג לחזור באותו מסלול שנסע בו הלוך. כלומר, הנסיעה הלוך צריכה להתבצע במסלול X כלשהו והנסיעה חזור צריכה להתבצע במסלול Y אחר כלשהו. למשל: נסיעה הלוך במסלול מספר 2 ונסיעה חזור במסלול מספר 3 (משהו שהוא אפשרי בהחלט ואחד הפתרונות לחידה). השאלה: באילו מסלולים X ו Y יוכל הנהג לנסוע מנקודת ההתחלה 0 עד לנקודה N וחזרה מנקודה N עד לנקודת ההתחלה, בלי שייעצר בדרך על ידי המחסומים הפועלים על פי ספרת האחדות 0 בשלט המספרי (שכתוב בבסיס כלשהו שנקבע על פי מספר הקילומטר). השאלה באופן אחר: באילו מספרי מסלולים יוכל הנהג להשלים נסיעה מלאה הלוך חזור של 2*N קילומטר בלי להעצר בדרך על ידי שערים חסומים? מה מייחד את מספרי המסלולים הללו? תנו פתרון כללי והסבירו מדוע. דוגמה לפתרון כללי: לא מספיק לתת פתרון כמו "מסלולים 2 ו 3" אלא לתת את כל רשימת המסלולים האפשריים הקיימים. למשל: פתרון כללי (שגוי): כל המסלולים שמספריהם מתחלקים גם ב 2 וגם ב 3. למי שלא מתאפק, פתרון החידה, כאן

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