חידת הנורות
חידת הנורות
תנאי החידה
אתם נמצאים במסדרון עגול אשר אינכם יודעים איפה ההתחלה ואיפה הסוף. לאורך כל המסדרון יש מפסקי אור בעלי שתי מצבים (כבוי ודלוק) ויש נורה אחת לכל מפסק. אתם מתחילים במקום אקראי ואתם יכולים לנוע ימינה או שמאלה אך אינכם יודעים אם סיימתם סיבוב שלם או לא. כמות הנורות לא ידועה והיא יכולה להיות כל מספר אקראי. גם מצב המפסקים הוא אקראי כלומר שיש נורות דלוקות, יש כבויות ולא ניתן לצפות מה יהיה מצבן.
יש לכם 2 פעולות מותרות: שינוי מצב המפסק (להדליק או לכבות), תנועה במורד המסדרון ימינה או שמאלה. עליכם לספור כמה נורות יש, כיצד תעשו זאת?
-----------------------------------------------------------------------------------------------------------------------
הקושי
המסדרון הוא מעגלי ואנחנו לא יודעים היכן הוא מתחיל או נגמר. זה יוצר קושי לדעת האם הנורה אותה אנחנו רואים היא נורה חדשה או נורה שכבר עברנו לידה.
איור 1
ישנם כמה פתרונות לא נכונים שאנשים בדרך כלל מציעים. למשל: אנחנו נלך במעגל ונרשום את הרצף של הנורות הדלוקות. נגיד 0 זה כבוי ואילו 1 זה דלוק. אם נלך מספיק זמן אנחנו נראה שהרצף חוזר על עצמו. נגיד באיור 1 הרצף הוא 0111010, אולי אם נמשיך ללכת נראה שאחרי 100 נורות פתאום הרצף המלא חוזר על עצמו. אנחנו יכולים להסיק מזה מסקנה שאולי יש סה"כ מאה נורות. אך הדבר הזה הוא לא בהכרח נכון. בואו נגיד שלאחר שעברנו במשך זמן ורשמנו את מצבי הנורות, ראינו את התמונה הבאה:
011011011110 011011011110
אנחנו רואים שהרצף 011011011110 חוזר על עצמו פעמיים. מכאן אנחנו יכולים בטעות לחשוב שסיימנו מעגל. אנחנו נעצור כאן ונגיד שזהו, זה כל הסיבוב. אבל בפועל, הסיבוב המלא הוא:
011011011110 011011011110 011011011110 011011011110 011
היינו בטוחים שכל המעגל הוא 24 נורות, כשבמציאות יש 51, פשוט במקרה יצא ככה שהרצף הזה 011011011110 חוזר על עצמו 4 פעמים ואז יש עוד 3 נורות נוספות 011. לכן השיטה הזאת היא לא מספיק וודאית.
שיטה נוספת שניתן להציע זה ללכת כל הזמן לכיוון אחד ולכבות (או להדליק) את כל הנורות עד שלא נגיע למצב שאנחנו לא רואים עוד נורות כבויות. הבעיה בשיטה הזאת שאם ניפול על רצף ארוך של נורות באותו המצב אנחנו עלולים בטעות לחשוב שסיימנו סיבוב.
איור 2
הביטו באיור 2. עברנו את הדרך המסומנת באדום והדלקנו את כל הנורות. לאחר מכן עברנו בדרך הכחולה וראינו שכל הנורות דולקות. מכאן הגענו למסקנה שסיימנו סיבוב ואמרנו שמספר הנורות הוא ככל הנראה 7. אבל כאשר אנחנו מסתכלים מהצד ורואים את המציאות אנחנו רואים שלמעשה יש הרבה יותר מ-7 פשוט יצא רצף של הרבה נורות דלוקות שחשבנו שאנחנו הדלקנו. לכן גם השיטה הזאת היא לא טובה.
-----------------------------------------------------------------------------------------------------------------------
הפתרון
השיטה הוודאית שבה בטוח לא נטעה היא קצת יותר מורכבת אבל היא לא מבוססת השערה אלה חישוב. אנחנו יודעים שאם הרמנו מפסק, הנורה אמורה להישאר דלוקה. ואנחנו יודעים שאם סיימנו סיבוב הגענו לאותו המפסק ממנו התחלנו. לכן, זה מה שנעשה. אנחנו נרים את המפסק הראשון כדי להדליק נורה אחת, לא משנה איזו נורה זו, העיקר שאנחנו יודעים שהדלקנו אותה והיא נקודת ההתחלה.
תגובות
הוסף רשומת תגובה