קומבינטוריקה, אינדוקציה

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

• 6 על הלוח

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

  נושאים:

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

• בחירות ממשלתיות

  בבחירות לפרלמנט של מדינה מסוימת השתתפו מספר מפלגות (לא ידוע כמה). כל אזרח שהשתתף בבחירות הצביע למפלגה אחת.

  עבור כל מספר שלם חיובי k נסמן על ידי `d_k` את מספר המפלגות שקיבלו k או יותר קולות. הוכיחו שהסכום `d_1+d_2+d_3+...` שווה למספר האזרחים שהצביעו בבחירות.

  הצגת רמז

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

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

• הכובעים הלא נכונים

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

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

  "זה די קל," הסביר מר סטאבס. "כפלו יחד את המספרים, `1, 2, 3, 4, 5, 6, 7`, ו-`8`. תן לי לראות—חצי דקה—כן; יש `40,320` דרכים שונות."

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

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

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

  נושאים:

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