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

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

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

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

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

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

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

רמז דק

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

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

רמז עבה

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

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

פתרון

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

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

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

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

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

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

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

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