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

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

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

• שחיתות בפרלמנט

  הפרלמנט של המדינה הקסומה מורכב מ-`20` אנשים. ידוע כי בין `20` חברי הפרלמנט יש לפחות אחד שהוא לא מושחת. הנוסף, ידוע כי לכל שני חברי פרלמנט שלא ניקח, אחד בהכרח מושחת. כמה מחברי הפרלמנט של המדינה הקסומה הינם מושחתים?

  נושאים:

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

• משחק עם שוקולד

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

  מי משניהם יכול להבטיח לעצמו ניצחון, אם יוסי עושה מהלך ראשון?

  נושאים:

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

• משחק עם ערימות אבנים

  שניים משחקים במשחק הבא. על השולחן נמצאות שלוש ערימות של אבנים. בערימה ראשונה יש `10` אבנים, בשנייה – `15`, בשלישית – `20`. כל אחד בתורו בוחר אחת הערימות שיש כרגע על השולחן ומחלק אותה לשתי ערימות קטנות יותר. מפסיד מי שלא מצליח לעשות מהלך.

  למי משני השחקנים יש אסטרטגיה מנצחת, ומהי?

  נושאים:

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

• שאלה

  מצאו מספר דו-ספרתי שהוא פי שתיים גדול יותר ממכפלת ספרותיו.

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  פתרו את המשוואה:

  `(x + 2010)(x + 2011)(x + 2012) = (x + 2011)(x + 2012)(x + 2013) `

  נושאים:

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

• שאלה

  פרש שח יצא מהמשבצת `a1`, ותוך מספר מהלכים חזר לאותה המשבצת.

  האם יתכן שהפרש ביצע מספר אי-זוגי של מהלכים?

  הצגת רמז

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

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

• שאלה

  פרש שח יצא מהמשבצת `a1` והגיע למשבצת `h8`. האם יתכן שבדרך הוא ביקר בכל משבצות הלוח בדיוק פעם אחת?

  הצגת רמז

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

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

• שאלה

  נתון לוח בגודל `M times N`, ובכל משבצות הלוח כתובים מספרים ממשיים. ידוע כי הסכומים בכל שורה ובכל עמודה של הלוח שווים ל-`1`.

  הוכיחו כי `M = N`.

  נושאים:

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

• שאלה

  בהינתן מספר שלם חיובי N, נתבונן בתהליך הבא: נסמן ב-`S(N)` את סכום הספרות של N ניקח את סכום הספרות של `S(N)`  נחזור על הפעולה שוב ושוב עד שנקבל מספר חד ספרתי נקרא למספר הפעמים שביצענו את התהליך הנ"ל עד שקיבלנו מספר חד-ספרתי: "העומק" של N. לדוגמה, העומק של 49 הוא `S(49)=13 -> S(13)=4)2` , הפעולה בוצעה פעמיים( והעומק של 45 הוא 1.

  א) הוכיחו כי לכל מספר N אכן יש עומק סופי, כלומר, שתמיד יתקבל מספר חד-ספרתי בשלב כלשהו של התהליך.

  ב) נסמן ב-`x(n)` את המספר המינימלי (שערכו הקטן ביותר) בעל עומק N. מצאו את השארית של `x(5776)` בחילוק ב-6 .נמקו את תשובתכם!

  ג) מצאו את השארית של המספר `x(5776) - x(5708)` בחילוק ב-2016 .נמקו את תשובתכם!

  הצגת רמז

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

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