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

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

• מעגל שקרנים - טענת האמת

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

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

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

  כל אחד מהאנשים אומר שהאיש שיושב שני מקומות לשמאלו (זאת אומרת ליד האיש שיושב לידו), הוא דובר אמת.

  ידוע שבמעגל יש לפחות שקרן אחד, ולפחות דובר אמת אחד.

  א. האם ייתכן ש-2017 = n?

  ב. האם ייתכן ש-5778 = n?

  (פורמט פתרון: "מילה, מילה" למשל "חתול, כלבלב")

  הצגת רמז

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

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

• מקיפים בעיגולים

  נתונים שני משולשים ACE, BDF
  שנחתכים ב-6 נקודות: G,H,I,J,K,L
  כמתואר בציור. נתון כי בכל אחד מהמרובעים
  EFGI ,DELH ,CDKG ,BCJL ,ABIK ניתן לחסום מעגל.
  האם ייתכן שגם במרובע FAHJ ניתן לחסום מעגל?
  

  הצגת רמז

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

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

• פירוק ושימוש בנוסחה

  נוסחה מענינת היא `x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)`.

  א: היעזרו בה ופרקו לגורמים את הביטוי `a^n-b^n`.

  ב: פרקו לגורמים את הביטוי `a^n+b^n` ל n אי זוגי כלשהו.

  ג: הוכיחו שאם `2^n-1` ראשוני אז גם n ראשוני.

  ד: הוכיחו שאם `2^n+1` ראשוני אז n בהכרח חזקה של 2 שזה שקול ל `n=2^m`

  הצגת רמז

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

  אלגברה -> טכניקה אלגברית תורת המספרים -> מספרים ראשוניים -> פרוק לגורמים ראשוניים הוכחה ודוגמה -> הוכחה בשלילה
  מקורות:
  • תרגילי הנבחרת הצעירה למדעים, 2024-2025, מטלה 1 שאלה 4

• חילוק סופי

  מצאו את כל ה x,y,z,w השלמים שמקיימים `x^2+y^2=3z^2+3w^2 `.

  הצגת רמז

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

  תורת המספרים -> חשבון השאריות הוכחה ודוגמה -> הוכחה בשלילה אלגברה -> משוואות -> משוואות דיופנטיות
  מקורות:
  • תרגילי הנבחרת הצעירה למדעים, 2024-2025, מטלה 1 שאלה 5

• קבוצות במישור

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

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

  נושאים:

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

• ריצוף משושה

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

  נושאים:

  לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה גאומטריה -> גאומטריה במישור -> חשבון זוויות
  מקורות:
  • תחרות גרוסמן, 2006 שאלה 4

• אורכי צלעות משולש

  יהי `n > 2` מספר שלם, ויהיו ` t_1,t_2,...,t_n` מספרים ממשיים חיוביים כך ש

  `(t_1+t_2+...+t_n)(1/t_1 + 1/t_2 + ... + 1/t_n) < n^2+1`

  הוכח כי לכל i,j,k כך ש- `1<=i<j<k<=n`, שלשת המספרים `t_i,t_j,t_k` הם אורכי הצלעות של משולש.

  נושאים:

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