משפט גומורי

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

הרקע למשפט

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

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

הוכחת המשפט

מסלול מעגלי על לוח שחמט

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