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

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  על הלוח כתובים המספרים: `1, 2, 3, …, 2016, 2017`. תוך מהלך אחד מותר לבחור זוג מספרים שכתובים על הלוח, למחוק אותם ולרשום במקומם את ההפרש שלהם (החיובי). אחרי מספר פעולות כאלו נשאר על הלוח מספר בודד. האם יתכן שזה אפס?

  נושאים:

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

• שאלה

  מישור נצבע בשני צבעים (כלומר, כל נקודת המישור נצבעה באחת משני הצבעים האלה). הוכיחו כי קיימות שתי נקודות במישור במרחק `1` כך ששתיהן באותו צבע.

  נושאים:

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

• שאלה

  האם קיימת סדרה חשבונית אינסופית שמורכבת ממספרים ראשוניים בלבד?

  הערה: לא נתיחס לסדרות חשבוניות "טריוויאליות", שהן קבועות.

  הצגת רמז

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

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

• שאלה

  הוכיחו כי סכום ספרות של ריבוע שלם לא יכול להיות שווה `2019 `.

  הצגת רמז

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

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

• שאלה

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

  ב. אותה השאלה, אבל במקום הכל של 5 ליטרים יש כלי של 4 ליטרים.

  נושאים:

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

• שאלה

  הוכיחו כי לא ניתן לחתוך את הצורה הנתונה לאבני דומינו:

  

  נושאים:

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

• שאלה

  האם קיים ריבוע שלם שמסתיים בספרות `...2017`?

  נושאים:

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

• שאלה

  `19` עצי תפוחים ממוקמים במעגל. הוכיחו כי קיים זוג עצים סמוכים, שמספר התפוחים הכולל שיש עליהם הינו זוגי.

  נושאים:

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