משפט גומורי

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

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

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

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

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

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