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

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

• שאלה

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

  נושאים:

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

• שאלה

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

  הצגת רמז

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

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

• שאלה

  `101` נקודות ממוקמות על מעגל. אילו מצולעים בעלי קודקודים בנקודות האלו יש יותר – מצולעים עם `51` צלעות או מצולעים עם `50` צלעות?

  נושאים:

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

• שאלה

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

  

  נושאים:

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

• שאלה

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

  

  נושאים:

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

• שאלה

  נתבונן במספרים שלמים מ-`1` עד `700`.

  א. כמה מהמספרים האלה זוגיים?

  ב. כמה מהמספרים האלה מתחלקים ב-`7`?

  ג. כמה מהמספרים האלה לא מתחלקים לא ב-`2`, לא ב-`7`?

  ענו את התשובה לסעיף ג

  נושאים:

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

• שאלה

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

  נושאים:

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