הוכחות בדרך השלילה

מאת: עודד לבנה

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

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

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

דוגמא ראשונה
שאלה: איך יודעים שיש אינסוף מספרים?

התשובה הרגילה היא: כי לכל מספר אפשר להוסיף 1.

התשובה בדרך השלילה תהיה:
נניח בשלילה שאין אינסוף מספרים.
לכן יש רק מספר סופי של מספרים.
לכן יש מספר גדול מכל המספרים האחרים. נקרא לו N.
N+1 הוא מספר.
N+1 גדול מ-N.
זה עומד בסתירה לכך ש-N הוא המספר הגדול ביותר.
הגענו לסתירה, ולכן סתרנו את הנחת השלילה.
מש"ל.

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

אגב, ראשי התיבות מש"ל הם תרגום של QED- Quod Erat Demonstrandum.
אלי בר יהלום סיפר לי שבפעם הראשונה שהשתמשו בהם משמעם היה
"מה שכתבתי למעלה" (למעלה נכתב "טענה:...) ורק במרוצת
הזמן שינו את משמעותם ל- "מה שרצינו להוכיח;".


רקע


ראשוני

מספר ראשוני הוא מספר טבעי (כלומר: שלם חיובי) אשר יש לו בדיוק שני מחלקים טבעיים.

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

עצרת

לפני הדוגמא השניה ניישר קו עם המונח "עצרת" וסימונו-
סימן הקריאה
N עצרת, המסומן !N, היא מכפלת כל המספרים בין 1 ל-N.

הגדרה רקורסיבית:
אפשר להגדיר את N עצרת כך:
0 עצרת זה 1.
עבור כל מספר N גדול מ-0, מגדירים את N עצרת כמכפלה של N ב-1-N עצרת.
לדוגמא:
2! = 2
3! = 6
  4! = 24
   5! = 120
ומכאן ברכת המתמטיקאים ליום הולדת 24:
מזל טוב ל-!4, שיהיה לך עד !5.


דוגמא שניה

זוהי דוגמא קלאסית מימי המתמטיקה היונית.

היא מיוחסת לאחד המתמטיקאים הגדולים, אם היה זה פיתגורס אינני זוכר, אויקלידס,
דיאופנטוס או אחר.

שאלה: איך יודעים שיש אינסוף מספרים ראשוניים?

תשובה בלי דרך השלילה:
(אין לי מושג. אתם מוזמנים לנסות. תשובות בהמשך המאמר לא אנסה יותר להציג
בלי דרך השלילה.)

תשובה בדרך השלילה:
נניח בשלילה שאין אינסוף מספרים ראשוניים.
לכן יש רק מספר סופי של מספרים.
לכן יש מספר ראשוני גדול ביותר. נקרא לו N.
נזכור שכל מספר שאיננו מספר ראשוני, מתחלק במספר ראשוני.
נביט במספר !N (קרי: N עצרת.)
מספר זה מתחלק בכל המספרים הראשוניים. הוא גם הרבה יותר גדול מ-N.
נבחן עתה את המספר N!+1.
מספר זה מתחלק בכל המספרים הראשוניים עם שארית 1.
לכן איננו מתחלק באף מספר ראשוני.
לכן הוא ראשוני.
הוא גם הרבה יותר גדול מ-N.
לכן יש מספר ראשוני גדול מ-N.
זה עומד בסתירה לכך ש-N הוא המספר הראשוני הגדול ביותר.
הגענו לסתירה, ולכן סתרנו את הנחת השלילה.
מש"ל.

נעיר שאין כאן טענה שלכל N ראשוני N!+1 הוא ראשוני.
(לדוגמא: ל-121, 5 אינו ראשוני, כי הוא 11 בריבוע).
הטענה היא שהמספר N!+1 אינו מתחלק לאף ראשוני הקטן מ-N או שווה לו.

נחזור עתה באופן פורמאלי על הטכניקה של הוכחה בדרך השלילה כפי שהודגמה:
קיימת הנחה. נקרא לה A.
במקרה שלנו, A היתה "יש סוף למספרים הראשוניים;"
מניחים ;A" אינו נכון;". במקרה שלנו ההנחה היתה "יש סוף למספרים הראשוניים;".
זוהי "הנחת השלילה;".
בשלב השני מסיקים מסקנות אשר מוליכות לסתירה.
במקרה שלנו הסתירה היתה בין "יש מספר ראשוני גדול ביותר;"
לבין "לכל מספר ראשוני N יש מספר אשר כל מחלקיו גדולים מ-N ;"
המסקנה, שוב, היא שמשהו בטיעון לא היה בסדר.
החלק היחיד בכל הדיון אשר היה מוטל בספק היא הנחת השלילה, A.

הרקע הלוגי הוא שאם הטענה "לא quot;A& מביאה לסתירה, אז A נכונה.


חידות הנפתרות בדרך השלילה


לחיצות ידיים בשישיה (רמזי 3-3)

אומנם זו חידה שאפשר לפתור בלי דרך השלילה, אך היא חידה נחמדה.

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

עיקר הפתרון
נכנה את האנשים א, ב, ג, ד, ה, ו.
נניח בשלילה שאין אף שלישיה שלחצה ידיים ואף שלישיה שלא לחצה ידיים.
נביט באדם א.
נחלק את האנשים לאלה שלחצו איתו ידיים ואלה שלא לחצו איתו ידיים.
חילקנו חמישה אנשים לשתי קבוצות. לכן, לפי עיקרון השובך, יש לפחות קבוצה אחת
אשר יש בה לפחות שלושה אנשים.
(האמת, במקרה הפשוט הזה לא צריך שובך כדי להבין זאת).
נניח שזו הקבוצה של אנשים שלחצו ידיים עם א.
(אם אלו האנשים אשר לא לחצו ידיים עם א, אז ההוכחה דומה,
ויש להחליף בכל מקום את "לחצו" ב-&לא לחצו;" quot; )
נניח שהאנשים האלה הם ב, ג, ו- ד. (אלה רק שמות. אפשר להניח שאלו שמותיהם).
יש לנו האפשרויות הבאות:
1. אם ב לחץ עם ג- אז א-ב-ג זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, שלחצה ידיים לפי הנחת השלילה (שאין שלישיה)- ב לא לחץ יד עם ג.
2. אם ב לחץ עם ד- אז א-ב-ד זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, לפי הנחת השלילה, ב לא לחץ יד עם ד.
3. אם ג לחץ עם ד- אז א-ג-ד זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, לפי הנחת השלילה, ד ג לא לחץ יד עם.

משלוש המסקנות לעיל נובע ש- ב-ג-ד זו שלישיה שלא לחצה ידיים.
זה עומד בסתירה להנחת השלילה שאין שלישיה כזו.
מש"ל.


השורש של 2


חידה קלאסית זו נפתרה על ידי מתמטיקאים יווניים.

המסקנה ממנה נחשבה שערורייתית: קיומם של מספרים לא רציונאליים.
לשנות אקסיומה חשובה זה חייב גיאומטריקנים יוונים.

השאלה: הוכח ששורש 2 איננו מנה של שני מספרים שלמים.
מספר שהוא מנה של שני מספרים שלמים נקרא מספררציונאלי
(רציו = יחס ביוונית. הוא מספר השווה ליחס בין שני מספרים שלמים מספר רציונאלי).

פתרון
נניח בשלילה ששורש 2 הוא מנה של שני מספרים שלמים: m/n.
נניח גם שהשבר m/n מצומצם (אחרת נצמצם). במלים אחרות: נניח ש-n ו-m זרים.
עתה: m/n הוא שורש 2
לכן
   (m*m) / (n*n) = 2
m*m = 2*n*n
צד ימין זוגי
לכן גם צד שמאל זוגי
לכן m מתחלק ב-2.
לכן צד שמאל מתחלק ב-4.
לכן גם צד ימין מתחלק ב-4
לכן n*n זוגי.
לכן n זוגי.
לכן גם m וגם n מתחלקים ב-2.
בסתירה להנחה שהשבר מצומצם עד הסוף.
מש"ל.


התחכמות

נשמע בפקולטה למתמטיקה בטכניון:
שאלה: הוכח שכל המספרים הטבעיים הם מיוחדים.

פתרון
נניח בשלילה שלא כל המספרים הטבעיים הם מיוחדים.
אז יש קבוצה לא ריקה של מספרים טבעיים אשר אינם מיוחדים, A.
לכל קבוצה לא ריקה של מספרים טבעיים יש מספר קטן ביותר.
נסמן N את המספר הקטן ביותר ב-A.
N הוא המספר הקטן ביותר בין כל המספרים הלא מיוחדים.
זה עושה אותו מיוחד.
סתירה לכך ש-N ב-A ולכן אינו מיוחד.
מש"ל.


שאלות לפתרון חברי קהילת החידות


החידה היפה ביותר שאני מכיר בנושא דרך השלילה היא:
נתונות N נקודות (יותר מאחת) במישור, ולא כולן על ישר אחד.
הוכח שיש ישר אשר עובר בדיוק דרך שתי נקודות.
(זו חידה לא קלה)

קל יותר: הוכח שאין סוף למספרים הראשוניים המתחלקים ל-4 עם שארית 3

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


בשולי הדברים


נהניתי מאד מהמאמר המצויין של אלעזר נוימן על אי טרנזיטיביות,
על אי טרנזיטיביות ואני רוצה להוסיף שלושה דברים:

משחק בלי אסטרטגיית נצחון

יצא לי להנחות כמה פעמים את המשחק הבא:
כל משתתף בוחר מספר טבעי.
מנצח המשתתף אשר בחר את המספר הטבעי הקטן ביותר אשר אף אחד אחר לא אמר.
איזה מספר תבחרו?
אם תבחרו 1 וגם מישהו אחר יבחר 1, אז לא תנצחו.
במשחק זה אין אסטרטגיה לנצחון, כי אם האסטרטגיה לנצחון היתה "בחר "N,
אז כולם היו בוחרים את אותו המספר, ולא מנצחים.
לכל אסטרטגיה יש אסטרטגיה אשר תנצח אותה.

קוביות

במאמר הוצגה האפשרות של שלוש קוביות אשר כל אחת מנצחת אחת אחרת
ומפסידה לאחת אחרת.
נדמה לי שראיתי דוגמא למעגל של 4 קוביות כאלו.
מישהו רוצה לנסות למצוא את המעגל?

חנניה רייכמן

היום כבר לא כל כך מכירים את המכתמאי, המתרגם והמשורר חנניה רייכמן.

פעם הוא היה מפורסם.
הוא כתב את היחס הנון-טרנזיטיבי הבא (והשמיט ממנו את החוליה ההופכת אותו
לנון-טרנזיטיבי: התלמידים מפחדים מהמורה:)

מורה בית ספר מתבהל
בשעת ביקור המנהל

המנהל- אימת מורים
פוחד מאד מפני הורים

וההורים מפחדים
מילדיהם התלמידים

ורק הללו לבדם
לא יפחדו משום אדם!


אתר הבית של עודד לבנה



מאמרים נוספים בפינה: כלים לפותרים

חיפוש

חיפוש מתקדם

הצטרף לרשימת התפוצה שלנו