צילום: The Metropolitan Museum of Art, Wikimedia Commons (CC0)

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

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

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

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

השאלה: מהו המספר הקטן ביותר של צבעים שמספיק לכל מפה אפשרית במישור, ולמה כל כך קשה היה להוכיח את התשובה?

רמז דק

החלק הקל הוא להראות שארבעה צבעים לפעמים הכרחיים. החלק הקשה הוא להראות שארבעה תמיד מספיקים - ושלעולם לא תצוץ מפה מפלצתית שתדרוש חמישה.

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

רמז עבה

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

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

פתרון

התשובה: ארבעה צבעים. זהו משפט ארבעת הצבעים.

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

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

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

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

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