קומבינטוריקה

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

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

• החרגול

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

  נושאים:

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

• תמנוני הקסם

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

  
  אבי: אני תמנון ירוק
  בני: אני לא ירוק
  גידי: כל התמנונים הירוקים שקרנים
  דני: רק תמנון ירוק יכול להיות שקרן

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

  נושאים:

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

• בול עץ

  ברשותכם בול עץ ארוך מאוד. האם תוכלו למדוד ממנו מטר אחד בדיוק,אם יש לכם לצורך זה
  א. מקל באורך של מטר וחצי ועוד מקל באורך של 40 סנטימטרים,
  ב. מקל באורך של מטר וחצי ועוד מקל באורך של 30 סנטימטרים,

  במידה ואין לכם שום כלי מדידה נוספים? נמקו!

  נושאים:

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

• בוחן

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

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

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

• פומבה והסוכריות

  לפומבה יש 11 סוכריות שוקולד ו-13 סוכריות טופי. בכל פעם הוא יכול לאכול או שתי סוכריות מסוגים שונים,
  או שלוש סוכריות מאותו הסוג. מה הוא המספר הגדול ביותר של סוכריות שפומבה יוכל לאכול לפי הכללים האלה?

  נושאים:

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

• צריחים מוכפלים

  נתון לוח `n times n` שבכל משבצת שלו רשום 1 או -1.

  נגדיר את הערך של סידור של צריחים על הלוח בתור מכפלת המספרים על המשבצות שלהם.

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

  נתון גם `n >= 4`

  (פתרון לבדיקה: כן או לא)

  הצגת רמז

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

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

• גזירה

  מה הוא המספר הגדול ביותר של מלבנים בגודל `2 times 5`  שאפשר לגזור מתוך ריבוע `9 times 9`?

  נושאים:

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

• סכום ספרות - 9

  לכמה מספרים בטווח מ-1 עד 500 יש סכום ספרות 9?

  נושאים:

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

• מעגל ושלוש נקודות

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

  האם יונתן יכול להגיע למצב שבו תיוותרנה על הלוח שלוש נקודות בצבעים הבאים (לפי כיוון השעון): כחול, ירוק, אדום? נמקו את תשובתכם

  הצגת רמז

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

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

• סכום מכפלות ספרות

  נסמן ב `P(n)` את מכפלת הספרות של המספר `n`. לדוגמה, `P(1948) = 1 * 9 * 4 * 8 = 288`.

  א.

  חשבו את `P(1) + P(2) + P(3) + ... + P(2016)`

  ב.

   מצאו את הערך המקסימלי של `{P(n)} /n`, כאשר `2016 <= n <= 5777`.

  (פורמט הפתרון: "x, y/z" כאשר y/z שבר לא מצומצם. למשל "10000, 35/100")

  הצגת רמז

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

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