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

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

• שאלה

  כמה משולשים יש בתמונה:

  

  נושאים:

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

• שאלה

  על הלוח כתובים המספרים: `1, 2, 3, …, 2016, 2017`. תוך מהלך אחד מותר לבחור זוג מספרים שכתובים על הלוח, למחוק אותם ולרשום במקומם את ההפרש שלהם (החיובי). אחרי מספר פעולות כאלו נשאר על הלוח מספר בודד. האם יתכן שזה אפס?

  נושאים:

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

• 26 מטבעות

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

  הצגת רמז

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

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

• מסגרת

  על דף משבצות נתון ריבוע בגודל `NxxN`. נתבנן במסגרת שלו בעובי של משבצת אחת. היא מורכבת מ-`4*(N-1)` משבצות.

  האם תוכלו לרשום במשבצות של המסגרת `4*(N-1)` מספרים שלמים עוקבים (לא בהכרח חיוביים), כך שיתקיים התנאי הבא:

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

  עבור:

  א. `N=3`

  ב. `N=4`

  ג. `N=5`

  

  נושאים:

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

• שאלה

  א. ברשותכם קנקן גדול של שמן זית של 12 ליטרים ושני ריקים כלים קטנים יותר, של 5 ושל 8 ליטרים. האם תוכלו לחלק את השמן שברשותכם לשני חלקים שווים, אם יש לכם רק את הכלים האלה ואין שום כלי מדידה נוספים?

  ב. אותה השאלה, אבל במקום הכל של 5 ליטרים יש כלי של 4 ליטרים.

  נושאים:

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

• שאלה

  זר מורכב מ-`7` שושנים, לבנות ואדומות (שני הצבעים נוכחים). ידוע כי מתוך כל שתי שושנים, אחת בהכרח לבנה. כמה שושנים לבנות וכמה שושנים אדומות יש בזר?

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים

• שאלה

  האם קיים ריבוע שלם שמסתיים בספרות `...2017`?

  נושאים:

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

• שאלה

  מהו המספר המקסימלי של מלכי שח שניתן להציב על לוח `8xx8`, כך שהם לא יאיימו אחד על שני?

  נושאים:

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

• שאלה

  בתרגיל חשבון הבא ספרות שונות הוחלפו על ידי אותיות שונות, וספרות זהות – על די אותיות זהות. שחזרו את התרגיל:

  `BAOxxBAxxB=2002`

  נושאים:

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

• שאלה

  נתונים `50` מספרים טבעיים שונים בין `1` ל-`100`. ידוע כי אין בינם שני מספרים שסכומם שווה ל-`100`. האם נכון שאחד מהמספרים האלה חייב להיות ריבוע שלם?

  נושאים:

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