בשיעור שאלנו לא רק מהי התשובה, אלא גם כיצד אפשר לשכנע שהתשובה נכונה.
התרגילים
תרגיל 1 - יעד אפשרי
יש 10 נורות בשורה, ובתחילה כולן כבויות. לחיצה על נורה הופכת אותה ואת הנורה שמימינה. לחיצה על הנורה הימנית ביותר אינה משנה דבר.
היעד: להדליק בדיוק את נורות 1, 3, 4, 7, 8 ו־10, ולנסות לעשות זאת ב־7 צעדים לכל היותר.
פתרון: לחצו על נורות 1, 2, 4, 5, 6, 8 ו־9. לאחר שבע הלחיצות דולקות בדיוק נורות היעד. רצף הצעדים הזה הוא הוכחה משכנעת שהיעד אפשרי.
תרגיל 2 - יעד בלתי אפשרי
מתחילים שוב כשכל 10 הנורות כבויות, ופועלים לפי אותו כלל.
היעד: להדליק בדיוק את נורות 1, 3, 4, 7 ו־10.
פתרון: אי אפשר להגיע ליעד. בכל לחיצה מספר הנורות הדולקות משתנה ב־2, ב־0 או ב־−2, ולכן הזוגיות שלו נשמרת. התחלנו עם 0 נורות דולקות, ואילו ביעד דולקות 5 נורות.
תרגיל 3 - בחירת כל זוג נורות
יש 10 נורות. בתחילה רק נורה 5 דולקת. בכל צעד בוחרים שתי נורות שונות כלשהן והופכים את מצב שתיהן.
היעד: לכבות את כל הנורות.
פתרון: אי אפשר. גם כאשר בוחרים נורות שאינן סמוכות, בכל צעד מספר הנורות הדולקות משתנה במספר זוגי. לכן הוא נשאר אי־זוגי, ולא יוכל להגיע ל־0.
תרגיל 4 - מערכת הצירים: יעד אפשרי
מתחילים בנקודה (0,0). בכל צעד זזים יחידה אחת באלכסון, בלי לצאת מהרביע הראשון.
היעד: להגיע לנקודה (13,9).
פתרון: אפשר להגיע. לדוגמה, מבצעים 11 צעדים ימינה ולמעלה ואחריהם 2 צעדים ימינה ולמטה. מתקבלים בסך הכול 13 צעדים ימינה ו־9 צעדים למעלה, ולכן מגיעים לנקודה (13,9).
תרגיל 5 - מערכת הצירים: יעד בלתי אפשרי
מתחילים בנקודה (0,0) ונעים שוב בצעדים אלכסוניים.
היעד: להגיע לנקודה (8,5).
פתרון: אי אפשר. בכל צעד שני השיעורים משנים זוגיות יחד: אם שניהם זוגיים הם נעשים אי־זוגיים, ולהפך. לכן הם תמיד בעלי אותה זוגיות. ביעד 8 זוגי ו־5 אי־זוגי.
שאלון הסיכום וההרחבה
השאלון כולל תשע שאלות. בכל שאלה חשוב להסביר את דרך החשיבה ולא להסתפק בניחוש.
יש 10 נורות, ומתוכן 6 דולקות. בצעד אחד הופכים את מצבן של שתי נורות כלשהן. אילו מספרים של נורות דולקות יכולים להיות לאחר הצעד?
4 · 5 · 6 · 7 · 8
פתרון: 4, 6 או 8. אם הופכים שתי נורות דולקות המספר קטן ב־2; אם הופכים אחת דולקת ואחת כבויה הוא אינו משתנה; ואם הופכים שתי נורות כבויות הוא גדל ב־2.
שאלה 2 - מאה צעדים
יש 10 נורות כבויות. בכל צעד הופכים בדיוק שלוש נורות שונות. לאחר בדיוק 100 צעדים, האם ייתכן שדולקות בדיוק 7 נורות?
פתרון: לא. הפיכת שלוש נורות משנה את מספר הנורות הדולקות במספר אי־זוגי, ולכן מחליפה את הזוגיות בכל צעד. לאחר מספר זוגי של צעדים הזוגיות חוזרת להיות זוגית, ולכן לא ייתכן שידלקו 7 נורות.
שאלה 3 - מספר הצעדים הקטן ביותר
יש 10 נורות כבויות. בכל צעד הופכים שתי נורות כלשהן. מהו מספר הצעדים הקטן ביותר הדרוש כדי להגיע למצב שבו בדיוק 8 נורות דולקות?
2 · 3 · 4 · 8
פתרון: 4. בכל צעד אפשר להדליק לכל היותר שתי נורות, ולכן נדרשים לפחות ארבעה צעדים. ארבעה צעדים מספיקים אם בכל פעם בוחרים זוג חדש של נורות כבויות.
שאלה 4 - שתי שורות
יש שתי שורות של 5 נורות, ובתחילה כולן כבויות. בכל צעד בוחרים שתי נורות באותה שורה והופכים את מצבן. האם אפשר להגיע למצב שבו דולקת בדיוק נורה אחת בכל שורה?
במצב המבוקש דולקות בסך הכול שתי נורות - מספר זוגי. מדוע בדיקת הזוגיות של מספר הנורות הכולל אינה מספיקה?
פתרון: אי אפשר. הזוגיות נשמרת בכל שורה בנפרד. בכל אחת מהשורות התחלנו עם 0 נורות דולקות, ולכן בכל שורה חייב להישאר מספר זוגי של נורות דולקות.
שאלה 5 - חלוקה לשתי קבוצות
יש 10 נורות כבויות בשורה. בכל צעד הופכים נורה ואת הנורה שנמצאת שני מקומות מימינה. האם אפשר להגיע למצב שבו רק נורות 1 ו־2 דולקות?
פתרון: אי אפשר. מחלקים את הנורות למקומות אי־זוגיים ולמקומות זוגיים. בכל פעולה שתי הנורות שייכות לאותה קבוצה, ולכן הזוגיות נשמרת בכל קבוצה בנפרד. ביעד דולקת נורה אחת בכל קבוצה.
שאלה 6 - בדיוק חמישה צעדים
מתחילים בנקודה (0,0) ונעים בצעדים אלכסוניים ברביע הראשון. לאילו נקודות אפשר להגיע לאחר בדיוק 5 צעדים?
(5,3) · (4,2) · (3,1) · (2,5)
פתרון: (5,3) ו־(3,1). לאחר חמישה צעדים שני השיעורים חייבים להיות אי־זוגיים. לשתי הנקודות האלה אכן קיימים מסלולים בני חמישה צעדים שאינם יוצאים מהרביע הראשון.
שאלה 7 - אילו נקודות נגישות?
מתחילים בנקודה (0,0) ונעים בצעדים אלכסוניים ברביע הראשון. לאילו נקודות אפשר להגיע במספר כלשהו של צעדים?
(12,8) · (9,6) · (7,7) · (4,11)
פתרון: (12,8) ו־(7,7). אפשר להגיע מנקודת הראשית בדיוק לנקודות שבהן שני השיעורים בעלי אותה זוגיות.
שאלה 8 - הדרך הקצרה ביותר
ידוע שאפשר להגיע מהנקודה (0,0) לנקודה (x,y) באמצעות צעדים אלכסוניים. מהו מספר הצעדים הקטן ביותר הדרוש?
סכום השיעורים x+y
השיעור הגדול מבין x ו־y
השיעור הקטן מבין x ו־y
ההפרש בין השיעור הגדול לשיעור הקטן
פתרון: השיעור הגדול מבין x ו־y. בכל צעד אפשר להתקדם לכל היותר יחידה אחת בכל כיוון, ולכן אי אפשר להשתמש בפחות צעדים. כאשר הנקודה נגישה, אפשר לשלב את ההתקדמות בשני הכיוונים כך שמספר זה של צעדים מספיק.
שאלה 9 - תנועות חדשות
מתחילים בנקודה (0,0). בכל צעד זזים שתי יחידות ימינה ויחידה אחת למעלה, או יחידה אחת ימינה ושתי יחידות למעלה. האם אפשר להגיע לנקודה (10,10)?
פתרון: אי אפשר. בכל צעד הסכום x+y גדל ב־3. לכן בכל נקודה נגישה הסכום חייב להיות כפולה של 3, ואילו בנקודה (10,10) הסכום הוא 20.
הרעיונות המרכזיים
כדי להוכיח שאפשר: מספיק להציג דוגמה אחת שעובדת - רצף של צעדים חוקיים שמתחיל במצב הנתון ומסתיים ביעד.
כדי להוכיח שאי אפשר: העובדה שניסינו ולא הצלחנו אינה מספיקה. צריך למצוא תכונה שחלה על כל צעד אפשרי ולהראות שהיעד אינו מתאים לה.
תכונה נשמרת: תכונה שאינה משתנה במהלך התהליך נקראת אינווריאנט. זוגיות מספר הנורות הדולקות הייתה התכונה הנשמרת הראשונה שפגשנו.
הפיכת שתי נורות שומרת על זוגיות מספר הנורות הדולקות.
הפיכת שלוש נורות מחליפה את הזוגיות בכל צעד.
לפעמים כדאי לחלק את העצמים לקבוצות ולעקוב אחרי תכונה בכל קבוצה בנפרד.
בצעד אלכסוני שני שיעורי הנקודה משנים זוגיות יחד.
אפשר לחפש גם תכונות אחרות: בתנועות של שאלה 9, הסכום x+y תמיד גדל בכפולה של 3.