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

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

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

• רחוב צבעוני

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

  נושאים:

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

• רחוב צבעוני 2

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

  נושאים:

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

• שברים קסומים

  נקרא לשבר קסום, אם המונה והמכנה שלו קטנים מ-10. למשל, השבר `1/9` נחשב קסום, גם השבר `6/8` קסום, השבר `3/14` לא קסום.
  כמה שברים קסומים יש, שגדולים מחצי וקטנים מ-1?

  הערה: לצורך השאלה `2/3` ו `4/6` נחשבים שברים שונים.

  נושאים:

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

• מגן דוד במעגל

  על מעגל נתונות 8 נקודות. בכמה דרכים שונות אפשר לצייר מגן דוד עם קודקודים בנקודות האלו?

  

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

  נושאים:

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

• ספרת היחידות

  למרים יש שמונה כרטיסים עם מספרים תלת ספרתיים עוקבים. ספרת היחידות של המספר הקטן ביותר היא 1,
  ספרת היחידות של המספר הגדול ביותר היא 8. מרים סדרה את הכרטיסים בשורה כך שהמספר הראשון מתחלק ב-2,
  המספר השני מתחלק ב-3, המספר השלישי מתחלק ב-4, וכן הלאה עד המספר השמיני שמתחלק ב-9.
  מהי ספרת היחידות של המספר שמתחלק ב-7?

  נושאים:

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

• שקילת מטבעות

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

  נושאים:

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

• כנס מתמטי

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

  הצגת רמז

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

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

• חוגי הילדים

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

  הצגת רמז

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

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

• ציור של קשר

  נתון לוח משבצות בגודל 5x5 שמחולק למשבצות 1x1. שתי משבצות נקראות קשורות אם הן נמצאות באותה שורה או באותה עמודה, והמרחק בין מרכזי המשבצות הוא 2 או 3.
  לדוגמה, בציור מסומנות בצבע אפור כל המשבצות הקשורות למשבצת האדומה. סמי מקבל לוח לבן, ורוצה לסמן עליו כמה שיותר משבצות שאף שתיים מהן אינן קשורות זו לזו. מהי הכמות המרבית של משבצות שהוא יכול לסמן?
  

  הצגת רמז

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

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

• שיוויון בשלבים

  על הלוח כתובים המספרים 1,2,3,4,5,6,7,8,9,10 ודוד אמור לשנות אותם בשלבים. בכל שלב מותר לדוד לבחור שני מספריים ולשנות אותם ב 1, כלומר להוסיף לשניהם 1, להחסיר משניהם 1, או להוסיף לאחד 1 ולהחסיר מהשני 1.

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

  הצגת רמז

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

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