הוכחה ודוגמה, הוכחה בשלילה

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

• שאלה

  טבלה `N×N` ממולאת במספרים כך שכל השורות נבדלות (לפחות במקום אחד). הוכח/י כי אפשר למחוק עמודה כלשהי כך שבטבלה שתישאר גם כל השורות יהיו שונות.
  א. אנג'אנס

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> תורת הגרפים הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • תחרות הערים, תש"מ, עיקרית, אביב שאלה 2

• שאלה

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

  נושאים:

  לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה

• שאלה

  יום אחד הארי פוטר מצא מחברת מוזרה בה היו כתובים מאה המשפטים הבאים:

  "במחברת הזאת יש בדיוק משפט אחד שהוא שקר"

  "במחברת הזאת יש בדיוק שני משפטים שהם שקר"

  "במחברת הזאת יש בדיוק שלושה שהם שקר "

  ...

  "במחברת הזאת יש בדיוק מאה משפטים שהם שקר "

  האם יש במחברת הזאת משפטים שהם אמת, ואם כן, אז כמה? נמקו!

  נושאים:

  קומבינטוריקה -> בדיקת מקרים -> תהליכים הוכחה ודוגמה -> הוכחה בשלילה לוגיקה -> דוברי אמת ושקרנים לוגיקה -> הגיון -> פרדוקסים

• שאלה

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

  נושאים:

  גאומטריה -> גאומטריה במישור גאומטריה -> חשבון שטחים אלגברה -> אי שוויונים הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • תחרות הערים, תש"מ, עיקרית, אביב שאלה 6

• שאלה

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

  א. הוכיחו שהקוסם המרושע יכול לעשות את זה.

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

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

  נושאים:

  קומבינטוריקה -> תורת הגרפים קומבינטוריקה -> אינדוקציה הוכחה ודוגמה -> הוכחה בשלילה

• שאלה

  האם תוכלו למלא טבלה בגודל `5xx5` על ידי מספרים ממשיים כך שסכום בכל שורה יהיה חיובי, וסכום בכל עמודה יהיה שלילי?

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

  קומבינטוריקה -> ספירה כפולה לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  האם תוכלו למלא טבלה בגודל `5xx5` על ידי

  א. מספרים שלמים,

  ב. מספרים ממשיים,

   כך שהסכום בכל שורה יהיה זוגי, והסכום בכל עמודה יהיה אי זוגי?

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

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

• שאלה

  האם תוכלו למצוא `35` מספרים שלמים שהממוצע שלהם שווה ל-`6.35`?

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

  אריתמטיקה קומבינטוריקה -> ספירה כפולה אלגברה -> אי שוויונים -> ממוצעים הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  בשתי כיתות בעלות כמויות זהות של תלמידים התקיים בוחן. אחרי בדיקת הבוחן, המורה טען שכמות של ציוני `0 ` הייתה ב-`13` גדולה יותר מכמות של כל הציונים האחרים ביחד. האם יש מצב שהוא טעה?

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

  קומבינטוריקה -> ספירה כפולה לוגיקה -> הגיון תורת המספרים -> חלוקה -> זוגיות הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  האם קיים ריבוע שלם שסכום ספרותיו שווה ל-`2001`?

  נמקו או הביאו דוגמה!

  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-3 וב-9 תורת המספרים -> חלוקה -> זוגיות תורת המספרים -> מספרים ראשוניים -> פרוק לגורמים ראשוניים הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • אתר האינטרנט problems.ru