על לוח שחמט מלבני מוקטן, בן 12 משבצות בלבד, מניחים 6 פרשים.

משבצות הלוח ממוספרות מ–1 עד 12, כמתואר בתרשים. הפרשים מונחים על משבצות 1,2,7,8,9,10.

עליכם להעביר את כל הפרשים מהמשבצות עליהן הונחו בתחילה - אל המשבצות הריקות (פרש אחד על כל משבצת. כלומר, אל המשבצות 3,4,5,6,11,12).

שימו❤️!! גם בחידה שלנו, פרש נע באותו האופן שבו הוא נע במשחק שחמט רגיל.

מה הוא מספר הצעדים הנמוך ביותר שבו ניתן לבצע את המשימה?

יעל, תלמידת קבוצת ו' מתל אביב, ציינה את ההתאמה לתורת הגרפים:

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

ליה, תלמידת קבוצת ו' בכפר הירוק הסבירה במילים אחרות:

"הפכנו את הלוח הדו מימדי לגרף, וגילינו שהדרך היחידה להגיע למשבצות הלא מאויישות היא דרך 10 ו-2. סימנו על כל אחת מהמשבצות הלא מאויישות, את המרחק או העומק מהמשבצת המאויישת הכי קרובה (10, 12).

גילינו ש-6 היא המשבצת הרחוקה ביותר, שלוקח שלושה צעדים לפחות להגיע אליה. הגענו למסקנה שקודם צריך לאייש את 6 (רחוקה 3 צעדים) אח"כ את 4, 12 ו-5 שרחוקות 2 צעדים, ואח"כ את 3 ו-11 שרחוקות צעד אחד בלבד. כדי לאמת את תשובתנו, הנחנו מטבעות כל המשבצות וראינו שאי אפשר להגיע בפחות מ 16 צעדים."

סביאטיק, תלמיד קבוצת ז' בקריות, הסיק את התשובה מניתוח של הלוח:

"כדי להגיע ל-5 המינימום הוא 2 צעדים. 2-11-5, כדי להגיע ל-6 המינימום הוא 3 צעדים. 10-3-12-6.
כדי להגיע מ-9 למשבצת כלשהי מן הנתונות נדרשים מינימום 2 צעדים אך זה יפריע ל-8 לעבור ל-11, לכן המינימום הוא 3 צעדים 9-2-11-4.
כדי להגיע מ-1 למשבצת כלשהי מן הנתונות נדרשים מינימום 2 צעדים אך זה יפריע ל-7 לעבור ל-3, לכן המינימום הוא 3 צעדים. 1-10-3-12
כדי להגיע מ-8 למשבצת כלשהי מן הנתונות נדרשים מינימום 2 צעדים. 8-2-11.
כדי להגיע מ-7 למשבצת כלשהי מן הנתונות נדרשים מינימום 3 צעדים. 7-1-10-3.

אם נסכום את כל המספרים המינימליים נקבל 16."

תורת הגרפים - תחום מתמטי 'חדש'

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

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

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

אם תורת הגרפים מוצאת חן בעיניכם

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

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