קומבינטוריקה, צביעות

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

• שאלה

  הארץ הקסומה מורכבת מ-`25` מחוזות. האם יתכן שכל מחוז גובל במספר אי זוגי של מחוזות אחרים?

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  .המישור חולק על ידי n ישרים ומעגלים,

  הוכיחו כי את המפה שהתקבלה ניתן לצבוע בשני צבעים כך ששני חלקים שכנים (נפרדים על ידי קטע או קשת) נצבעים בצבעים שונים.

  הצגת רמז

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

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

• שאלה

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

  הצגת רמז

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

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

• מעגל ושלוש נקודות

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

  האם יונתן יכול להגיע למצב שבו תיוותרנה על הלוח שלוש נקודות בצבעים הבאים (לפי כיוון השעון): כחול, ירוק, אדום? נמקו את תשובתכם

  הצגת רמז

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

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

• הבונה והחפרפרת

  ישנה חלקת אדמה שצורתה ריבוע `4 times 4` המחולקת למשבצות של `1 times 1`.הבונה רוצה לבנות עליה בית שתופס 4 משבצות, שממבט על יראה כך:

  

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

   

  נושאים:

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

• עוד קוביות משחק

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

  נושאים:

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

• לוח ציור

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

  נושאים:

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

• שאלה

  במעגל נמצאות 5778 נורות כבויות במרחקים קבועים. מתחת לכל נורה יש כפתור. כאשר לוחצים על הכפתור, זה משנה מצב של 4 נורות: הנורה שליד הכפתור, שתי נורות הבאות במעגל עם כיוון השעון, ואת הנורה הנגדית לכפתור (נורה כבויה נדלקת כאשר משנים את מצבה, ונורה דולקת נכבית). מהי הכמות המרבית של נורות שיכולות להיות דלוקות בו-זמנית?
  

  נושאים:

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

• שאלה

  נתון לוח בגודל 10×10. איילה רוצה לצבוע את משבצות הלוח בכחול ולבן (כל משבצת בצבע מסוים),
  כך שבכל ריבוע שמורכב מ-4 משבצות יהיו בדיוק שתי משבצות לבנות ושתי משבצות כחולות. בכמה
  דרכים שונות יכולה איילה לצבוע את המשבצות בהתאם לכללים האלה?

  נושאים:

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