קומבינטוריקה, אינווריאנטים

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

• שאלה

  מלוח שחמט גוזרים שתי פינות מנוגדות (השדות `a1` ו-`h8`, למשל). האם תוכלו לרצף את הלוח שנשאר על ידי אבני דומינו?

  הצגת רמז

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

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

• נמלים על המקל

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

  

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

  ב. כמה התנגשויות יתקיימו בין הנמלים?

  נושאים:

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

• חלב וקפה

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

  ב. אותה השאלה, אבל הפעם חנה מוסיפה חלב לתוך הקפה ללא ערבוב.

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

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

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

  נושאים:

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

• שאלה

  הוכיחו כי לא ניתן לחתוך את הצורה הנתונה לאבני דומינו:

  

  נושאים:

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

• שאלה

  האם תוכלו לחתוך את הצורה שבצד שמאל לשש צורות כמו הצורה בצד ימין?

  

  נושאים:

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

• שאלה

  לאורך הרחוב ממוקמים `6` עצים. יום אחד הגיעו `6` תוכים והתיישבו על העצים, תוכי אחד על כל עץ. מידי פעם שני תוכים עוברים כל אחד לעץ סמוך לבחירתו. האם יוכלו התוכים להתכנס כולם על אותו עץ?

  נושאים:

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

• החרגול

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

  נושאים:

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

• בול עץ

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

  במידה ואין לכם שום כלי מדידה נוספים? נמקו!

  נושאים:

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