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

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

• שאלה

  על המעגל נתונות נקודות כחולות ואדומות. מותר להוסיף נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה או להסיר נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה בעבר (אסור להשאיר פחות מ-2 נקודות על המעגל). הוכח/י כי אי אפשר להעביר רק ע"י הפעולות האלה מעגל עם שתי נקודות אדומות למעגל עם שתי נקודות כחולות.
  ק. קזרנובסקי

  נושאים:

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

• זאב וכבשים

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

  נושאים:

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

• האביר והדרקון

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

  הצגת רמז

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

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

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

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

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

  נושאים:

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

• משחק עם שוקולד

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

  מי משניהם יכול להבטיח לעצמו ניצחון, אם יוסי עושה מהלך ראשון?

  נושאים:

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

• משחק עם ערימות אבנים

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

  למי משני השחקנים יש אסטרטגיה מנצחת, ומהי?

  נושאים:

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

• שאלה

  פרש שח יצא מהמשבצת `a1`, ותוך מספר מהלכים חזר לאותה המשבצת.

  האם יתכן שהפרש ביצע מספר אי-זוגי של מהלכים?

  הצגת רמז

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

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

• שאלה

  פרש שח יצא מהמשבצת `a1` והגיע למשבצת `h8`. האם יתכן שבדרך הוא ביקר בכל משבצות הלוח בדיוק פעם אחת?

  הצגת רמז

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

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

• שאלה

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

  נושאים:

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

• שאלה

  על נייר משבצות אינסופי מסומנות 6 משבצות, כמו בציור. על כמה משבצות נמצאות אבנים. במהלך אחד מותר לקחת אבן אם אין לו אבן שכנה מלמעלה ומימינה אז מותר לזרוק את האבן ולשים 2 אבנים במקומות מעל האבן ומימינה. האם נוכל לזרוק ע"י הפעולה הזו את כל האבנים ממקומות המסומנים אם במצב ההתחלתי האבנים היו: 
  א. (8 נקודות) בכל המשבצות המסומנות. 
  ב. (8 נקודות) רק במשבצת המסומנת הכי תחתונה והכי שמאלית. 

  O 
  O O 
  O O O

  מ. קונצוויץ' 

  נושאים:

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