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

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

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

• שאלה

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

  א. להרכיב בוודאות זוג גרביים כלשהו,

  ב. להרכיב בוודאות זוג גרביים שחורים?

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  על המעגל נתונות נקודות כחולות ואדומות. מותר להוסיף נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה או להסיר נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה בעבר (אסור להשאיר פחות מ-2 נקודות על המעגל). הוכח/י כי אי אפשר להעביר רק ע"י הפעולות האלה מעגל עם שתי נקודות אדומות למעגל עם שתי נקודות כחולות.
  ק. קזרנובסקי

  נושאים:

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

• שאלה

  טבלה `N×N` ממולאת במספרים כך שכל השורות נבדלות (לפחות במקום אחד). הוכח/י כי אפשר למחוק עמודה כלשהי כך שבטבלה שתישאר גם כל השורות יהיו שונות.
  א. אנג'אנס

  נושאים:

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

• שאלה

  a₁, a₂, ..., a₁₀₁ הם תמורה של 2,3,4, ... ,102 . כך ש a_i מתחלק ב-i לכל i. מצא/י את כל התמורות מסוג זה.

  נושאים:

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

• שאלה

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

  א. מה ניתן להסיק מזה על האיכר?

  ב. מה ניתן להסיק על המדריך?

  נושאים:

  לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים לוגיקה -> דוברי אמת ושקרנים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  ביום הולדתה של אליס שואלים את החברים שלה בת כמה היא. הכובען המטורף אומר כי הגיל של אליס גדול מ-`11`, וחתול צ'שייר אומר כי הגיל שלה גדול מ-`10`. ידוע כי בדיוק אחד מהם טועה. בת כמה אליס עכשיו? נמקו!

  הצגת רמז

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

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

• שאלה

  יום אחד הארי פוטר מצא מחברת מוזרה בה היו כתובים מאה המשפטים הבאים:

  "במחברת הזאת יש בדיוק משפט אחד שהוא שקר"

  "במחברת הזאת יש בדיוק שני משפטים שהם שקר"

  "במחברת הזאת יש בדיוק שלושה שהם שקר "

  ...

  "במחברת הזאת יש בדיוק מאה משפטים שהם שקר "

  האם יש במחברת הזאת משפטים שהם אמת, ואם כן, אז כמה? נמקו!

  נושאים:

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

• שאלה

  לשלושה קיפודים יש שלוש חתיכות גבינה של `5`, `8` ו-`11` גרם. שועל מציע לקיפודים לעזור להם לחלק את הגבינה שווה בשווה. הפעולה שהשועל יכול לעשות זה לנגוס גרם אחד מכל אחת משתי חתיכות גבינה לבחירתו. האם השועל יוכל להגיע בעזרת פעולות אלו למצב בו הוא ישאיר לשלושה הקיפודים חתיכות שוות של גבינה?

  נושאים:

  אריתמטיקה אלגברה -> בעיות מילוליות הוכחה ודוגמה -> בניית דוגמה קומבינטוריקה -> בדיקת מקרים -> תהליכים קומבינטוריקה -> בדיקת מקרים -> תהליכים תורת המספרים -> חלוקה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  בחדר נמצאים `85` בלונים, אדומים וכחולים. ידוע כי:

  - לפחות אחד מהבלונים אדום,

  - בכל זוג בלונים שניקח, לפחות אחד מהבלונים חייב להיות כחול.

  כמה בלונים אדומים יש בחדר?

  נושאים:

  לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  האם ניתן לרצף לוח `5xx5` על ידי אבני דומינו?

  הערה: גודל של משבצת הלוח תואם לגודל המשבצת של דומינו.

  נושאים:

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