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

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

• שאלה

  האם תוכלו למצוא שני מספרים, שגם סכום, גם מכפלה שלהם אי זוגיים? נמקו או הביאו דוגמה!

  נושאים:

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

• שאלה

  האם תוכלו לחלק `44` כדורים ל-`9` ערימות אם כמות שונה של כדורים?

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  המספרים `1`, `2`, `3`, ..., `9` מחלוקים ל-`3` קבוצות. הוכיחו כי ישנה קבוצה בה מכפלת המספרים גדולה או שווה ל-`72`.

  הצגת רמז

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

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

• שאלה

  נתונים `50` מספרים טבעיים שונים בין `1` ל-`100`. ידוע כי אין בינם שני מספרים שסכומם שווה ל-`100`. האם נכון שאחד מהמספרים האלה חייב להיות ריבוע שלם?

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  נתונים מספרים טבעיים m,n כך ש`m/n <= sqrt 23` הוכיחו כי `m/n+3/{mn} <= sqrt 23`

  הצגת רמז

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

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

• שאלה

  האם יש פתרון בטבעיים למשוואה `x^2 + 12 = y^3` כך ש

  א. x זוגי (קל יותר)

  ב. x אי זוגי

  הצגת רמז

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

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

• צעצועים

  ליונתן יש אוסף של צעצועי עץ. חלקם קוביות וחלקם כדורים, חלקם אדומים וחלקם כחולים.

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

  הוכיחו כי יש ליונתן כדור כחול.

  נושאים:

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

• בוחן

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

  1. יש ילד שפתר מספר אי זוגי של שאלות
  2. יש שאלה שפתרו אותה מספר זוגי של ילדים
  נושאים:

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