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

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

• שאלה

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

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

  האם יובל בהכרח צודק?

  הצגת רמז

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

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

• באובב

  בתרגיל הבא ספרות זהות הוחלפו באותיות זהות, וספרות שונות הוחלפו באותיות שונות. שחזרו את התרגיל.

  `BAOxxBAxxB = 2002`

   

   

   

   

  נושאים:

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

• חתול לסבתא

  לסבתא חנה יש מספר חתולים. יום אחד הגיעו אליה שלושה נכדים שלה, אבי, בני וגילי, וניסו לנחש כמה חתולים יש לה.

  אבי אמר: "לסבתא יש לפחות 7 חתולים",

  בני אמר: "אבל פחות מ-10, לדעתי",

  ואז גילי אמרה: "לסבתא חנה יש או 9, או 10, או 11 חתולים".

  "כולכם צדקתם!" ענתה הסבתא

   אז כמה חתולים יש לה?
   

  הצגת רמז

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

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

• מספר פלינדרומי

  מצאו מספר ארבע ספרתי פלינדרומי, שמתחלק ב-25 ולא מתחלק ב-3

  הערה: מספר פלינדרומי הינו מספר שלא ישתנה אם נקרא את הספרות שלו בסדר הפוך. למשל, המספר 5775 הינו מספר פלינדרומי, והמספר 5778 אינו מספר פלינדרומי.

  הצגת רמז

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

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

• מה יש בכל כלי?

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

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

  איזה נוזל נמצא באיזה כלי?

   

  הצגת רמז

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

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

• שאלה

  לסבתא חנה יש הרבה עציצים עם פרחים בבית. יום אחד הגיעו אליה שלושת הנכדים שלה, אבי, בני וגילי, וניסו לנחש כמה עציצים יש לה.
  אבי אמר: "לסבתא יש יותר מ-8 עציצים",
  בני אמר: "יותר מ-10, לדעתי",
  ואז גילי אמרה: "לסבתא חנה יש לפחות 12 עציצים".
  "שניים מכם צדקו, ומישהו אחד טעה"–ענתה הסבתא. אז כמה עציצים יש לה בבית?

  נושאים:

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

• תמנוני הקסם

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

  
  אבי: אני תמנון ירוק
  בני: אני לא ירוק
  גידי: כל התמנונים הירוקים שקרנים
  דני: רק תמנון ירוק יכול להיות שקרן

  
  ידוע שרק אחד מארבעה אלה שקרן, והשאר דוברי אמת.
  א. מי הוא השקרן מבין ארבעה החברים? נמקו!
  ב. האם ניתן לדעת מה הצבע שלו?

  נושאים:

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

• פומבה והסוכריות

  לפומבה יש 11 סוכריות שוקולד ו-13 סוכריות טופי. בכל פעם הוא יכול לאכול או שתי סוכריות מסוגים שונים,
  או שלוש סוכריות מאותו הסוג. מה הוא המספר הגדול ביותר של סוכריות שפומבה יוכל לאכול לפי הכללים האלה?

  נושאים:

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

• צריחים מוכפלים

  נתון לוח `n times n` שבכל משבצת שלו רשום 1 או -1.

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

  האם סכום הערכים של כל הסידורים בהכרח מתחלק ב 4?

  נתון גם `n >= 4`

  (פתרון לבדיקה: כן או לא)

  הצגת רמז

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

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

• סכום ספרות - 9

  לכמה מספרים בטווח מ-1 עד 500 יש סכום ספרות 9?

  נושאים:

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