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

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  המורה חילקה (עם שארית) את מספר התלמידים בשכבה ב-2, ב-3, ב-4, ב-5 וב-9. כשסיכמה את השאריות, קיבלה 18. מצא את מספר התלמידים בשכבה, אם ידוע שהמספר קטן מ-300.

  נושאים:

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

• שאלה

  מצא את כל הזוגות x ,y של מספרים שלמים, המקיימים את המשוואה `x + y = x^2 + xy + y^2`

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  נתון לוח בגודל 10×10. איילה רוצה לצבוע את משבצות הלוח בכחול ולבן (כל משבצת בצבע מסוים),
  כך שבכל ריבוע שמורכב מ-4 משבצות יהיו בדיוק שתי משבצות לבנות ושתי משבצות כחולות. בכמה
  דרכים שונות יכולה איילה לצבוע את המשבצות בהתאם לכללים האלה?

  נושאים:

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

• שאלה

  בכמה דרכים שונות ניתן לבחור 6 ספרות a,b,c,d,e,f שכולן שונות מ-0 (ולא בהכרח שונות זו
  מזו), כך שהמספר השש-ספרתי `ab00cd` יתחלק במספר השש-ספרתי `cd00ef`?
  נושאים:

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