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

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

• שאלה

  על הלוח כתוב המספר `458`. בכל מהלך בודד מותר או להכפיל את המספר שכתוב על הלוח פי `2`, או למחוק את הספרה האחרונה שלו.

  האם אפשר בעזרת הפעולות האלו לקבל את המספר `14`?

  נושאים:

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

• שאלה

  כמה יש מספרים דו-ספרתיים שספרת העשרות שלהם גדולה יותר מספרת האחדות?

  נושאים:

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

• עלי באבא וארבעים השודדים

  עלי באבא רשם על הדף מספר `17`. ארבעים השודדים מעבירים את הדף זה לזה וכל אחד או מוסיף `1` למספר הקיים, או מחסיר `1`, עד שכל אחד מהם ביצע זאת פעם אחד, ואז מחזירים את הדף לעלי באבא.

  האם יתכן שעכשיו על הדף רשום מספר `40`?

  נושאים:

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

• שאלה

  מצאו את כל הזוגות של מספרים ראשוניים שההפרש שלהם שווה ל-`17`.

  הצגת רמז

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

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

• שאלה

  במדינה קסומה יש מטבעות של `1`, `2`, `3` ו-`5` לירות. ליוסי יש `25` מטבעות של המדינה הקסומה.

  האם בהכרח יש בין המטבעות האלו `7` מטבעות בעלות ערך זהה?

  נושאים:

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

• שלושה חברים

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

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

  הערה: "שוורצמן" משמעותו "איש שחור", "רוטנברג" משמעותו "סלע אדום" ו"וייס" משמעותו "לבן" (מיידיש).

  נושאים:

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

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

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

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

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

  נושאים:

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

• שאלה

  ל- K חברים סיפרו באותו זמן K חדשות (לכל חבר חדשה אחת). הם מתחילים לטלפן זה לזה ולהתחלף בחדשות. כל שיחה נמשכת שעה אחת. תוך כמה זמן כל החברים יכולים לדעת את כל החדשות? התבונן במקרים: 
  א. (5 נקודות) K=64 
  ב. (10 נקודות) K=55 
  ג. (12 נקודות) K=100 
  א. אנג'אנס 

  נושאים:

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