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

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

שאלה

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

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

האם ניתן לרצף לוח `5xx5` על ידי אבני דומינו?

הערה: גודל של משבצת הלוח תואם לגודל המשבצת של דומינו.

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

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

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

התחברו כאן לאתר על מנת לקבל את הרמז

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

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

התחברו כאן לאתר על מנת לקבל את הרמז

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

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

התחברו כאן לאתר על מנת לקבל את הרמז

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

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

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

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

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

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

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

הפרשים בלוח הכפל

צובעים את לוח הכפל `10xx10` בצביעת שחמט שחור ולבן, כך שהמשבצת של `1xx1` צבועה בשחור.
מצאו את ההפרש בין סכום כל המספרים במשבצות השחורות לסכום כל המספרים במשבצות הלבנות.

	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	10
2	2	4	6	8	10	12	14	16	18	20
3	3	6	9	12	15	18	21	24	27	30
4	4	8	12	16	20	24	28	32	36	40
5	5	10	15	20	25	30	35	40	45	50
6	6	12	18	24	30	36	42	48	54	60
7	7	14	21	28	35	42	49	56	63	70
8	8	16	24	32	40	48	56	64	72	80
9	9	18	27	36	45	54	63	72	81	90
10	10	20	30	40	50	60	70	80	90	100

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

מקורות:

החרגול

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

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

	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	10
2	2	4	6	8	10	12	14	16	18	20
3	3	6	9	12	15	18	21	24	27	30
4	4	8	12	16	20	24	28	32	36	40
5	5	10	15	20	25	30	35	40	45	50
6	6	12	18	24	30	36	42	48	54	60
7	7	14	21	28	35	42	49	56	63	70
8	8	16	24	32	40	48	56	64	72	80
9	9	18	27	36	45	54	63	72	81	90
10	10	20	30	40	50	60	70	80	90	100

	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	10
2	2	4	6	8	10	12	14	16	18	20
3	3	6	9	12	15	18	21	24	27	30
4	4	8	12	16	20	24	28	32	36	40
5	5	10	15	20	25	30	35	40	45	50
6	6	12	18	24	30	36	42	48	54	60
7	7	14	21	28	35	42	49	56	63	70
8	8	16	24	32	40	48	56	64	72	80
9	9	18	27	36	45	54	63	72	81	90
10	10	20	30	40	50	60	70	80	90	100

	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	10
2	2	4	6	8	10	12	14	16	18	20
3	3	6	9	12	15	18	21	24	27	30
4	4	8	12	16	20	24	28	32	36	40
5	5	10	15	20	25	30	35	40	45	50
6	6	12	18	24	30	36	42	48	54	60
7	7	14	21	28	35	42	49	56	63	70
8	8	16	24	32	40	48	56	64	72	80
9	9	18	27	36	45	54	63	72	81	90
10	10	20	30	40	50	60	70	80	90	100