עומק היסטורי: מסע האביר הוא רצף מתמטי שבו אביר מבקר בכל משבצת בלוח השחמט פעם אחת בלבד. זהו אתגר אסטרטגי ובעיה קלאסית במתמטיקה פנאי.
מקורות:
בעיה זו אינה תגלית מודרנית. הפתרונות המוקדמים ביותר הידועים לנו מתוארכים למאה ה-9, וניתנו על ידי גדולי בגדאד כגון אל-אדלי ואס-סולי. בנוסף, בספרות ההודית של המאה ה-9, המשורר הקשמירי רודרטה הדגים את האסתטיקה המתמטית הזו ביצירתו Kavyalankara, בה חיבר שיר העוקב אחר רצף מסלולו של אביר.
ספרות מערבית:
במאה ה-13, המלך אלפונסו ה-10 מקסטיליה הציג תמרונים מורכבים המבוססים על תנועת האביר בספרו המפורסם Libro de los Juegos (ספר המשחקים). עם זאת, הבסיס המתמטי המודרני לבעיה הונח בשנת 1759 על ידי לאונרד אוילר, שניתוחו מוכר כיום כאחד מאבני היסוד של תורת הגרפים.
מאפיינים:
סיור סגור (חוזר): אם האביר מסיים את תנועתו על משבצת המרוחקת בדיוק תנועה אחת של אביר מהמשבצת ההתחלתית, הוא יכול להתחיל את הסיבוב מחדש מיד.
סיור פתוח:
אם האביר מבקר בכל משבצת אך מסיים במשבצת שממנה אינו יכול להגיע לנקודת ההתחלה בתנועה אחת.
הבעיה, שהועלתה על ידי מקס בזל בשנת 1848 ומשכה את תשומת לבם של גאונים כגון קרל פרידריך גאוס, הפכה ל“מניפסט תכנות” בשנות ה-70 על ידי אחד מאבות מדעי המחשב המודרניים, אדסגר ו. דייקסטרה.
במחקרו החלוצי, הערות על תכנות מובנה (1972), Dijkstra השתמש בבעיית 8 המלכות כדי להדגים כיצד ניתן לבנות אלגוריתם באופן שיטתי באמצעות תהליך שכינה “זיכוך הדרגתי”.”
כוחו של החזרה לאחור:
לדברי דייקסטרה, גישה זו מהווה את אבן הדרך הראשונה בחפיפת תהליך “ניסוי וטעייה” לרצף לוגי מושלם, אשר...
אגדה ומקור:
על פי הסיפור, כאשר ממציא השחמט, סיסה בן דהיר, הציג את המשחק למלך הודו, המלך שאל אותו איזו תמורה הוא מבקש. סיסה ביקש בקשה צנועה לכאורה: “אני רוצה גרגר חיטה אחד עבור המשבצת הראשונה בלוח השחמט, שניים עבור השנייה, ארבעה עבור השלישית, ועבור כל משבצת לאחר מכן, כפול מהכמות של הקודמת”. המלך דחה בתחילה את הבקשה, מתוך מחשבה שמדובר ב“קומץ חיטה” בלבד; אולם, כאשר החלו בחישוב, התברר כי לא אוצר הממלכה ולא כל מלאי החיטה בעולם יספיקו כדי לענות על דרישה זו.
תיעוד היסטורי: אבן ח'ליקן (1256)
התיעוד הכתוב הראשון הידוע של סיפור מפורסם זה נכתב בשנת 1256 על ידי הביוגרף וההיסטוריון הנודע אבן ח'ליקן. אבן ח'ליקן שילב אירוע זה ביצירתו לא רק כסיפור, אלא כעדות לכך שהמתמטיקה מרחיבה את גבולות הדמיון.
מציאות מתמטית:
בקשה זו, המתייחסת ל-64 המשבצות בלוח השחמט, היא הדוגמה הטהורה ביותר להתקדמות גיאומטרית (צמיחה אקספוננציאלית). הסכום בכל משבצת מחושב באמצעות הנוסחה 2n-1 . המשוואה המציגה את הכמות הכוללת של החיטה היא כדלקמן:
63
∑
i=0
2i = 264 − 1
הנתון העצום המתקבל מחישוב זה הוא:
18,446,744,073,709,551,615
מדוע זה כל כך חשוב?
לקח אסטרטגי: בעיה זו היא לקח עתיק של חוכמה המלמד מנהיגים ואסטרטגים כיצד שינויים קטנים (“הכפלה”) יכולים להפוך עם הזמן לכוחות בלתי נשלטים.
