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

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

ב-1959 היה זה המתמטיקאי הנודע גרהרד רינגל (Gerhard Ringel) שהציף שאלה: מהו מספר הצבעים המינימלי הדרוש לצביעת אוסף נתון של מעגלים, כך ששני מעגלים משיקים יצבעו בצבעים שונים? שאלה זו נותרה פתוחה מעל שישים שנה והעסיקה את מיטב המדענים בתחום, עד שפרופ' שחר סמורודינסקי מאוניברסיטת בן-גוריון בנגב יחד עם מתמטיקאים בינלאומיים, הצליחו לענות על השאלה. מסקנותיהם יפורסמו בכנס הבינלאומי המרכזי בתחום וכבר מעוררים הדים בקהילה המדעית.

פרופ' שחר סמורודינסקי מהמחלקה למתמטיקה באוניברסיטת בן-גוריון בנגב, ביחד עם החוקרים: ד"ר לינדה קלייסט (Linda Kleist) מגרמניה, פרופ' ברטוש וולצ'ק (Bartosz Walczak) מפולין, ד"ר חיה קלר מאוניברסיטת אריאל וג'יימס דייויס (James Davies) מקנדה, לא הכירו זה את זה וחלקם אף לא נפגשו מעולם, אולם דווקא כשהתכנסו בחדר וירטואלי לטובת פתרון בעיות פתוחות בגאומטריה חישובית במסגרת כנס בנושא, הצליחו לפתור תעלומה שנותרה פתוחה מאז 1959, בעיית רינגל.

הקשר למשפט ארבעת הצבעים

לבעיית רינגל קשר הדוק ל'משפט ארבעת הצבעים', שהעסיק את מיטב המתמטיקאים משך 150 שנה ויותר: האם ניתן לצבוע מפה גיאוגרפית כך שכל שתי מדינות בעלות קו גבול משותף יצבעו בצבע שונה, תוך שימוש בארבעה צבעים לכל היותר? השאלה עלתה גם בהקשר של צביעת אוסף מעגלים – האם ניתן לצבוע מעגלים (שאינם חופפים אך יכולים להשיק) בארבעה צבעים כך ששני מעגלים משיקים יקבלו צבע שונה? שאלה זו עלתה באמצע המאה ה-19 ורק בשנת 1977 התקבלה ההוכחה שהתשובה היא כן.

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

הפתרון: תורת הגרפים ותורת רמזי

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

מה שהופך את הפתרון למסתורי עוד יותר הוא הדוגמאות שהציעו החוקרים בהוכחה המתמטית. אלו מצביעות על כך שמספר הצבעים הדרוש אינו חסום. הדוגמאות אינן מפורשות מפאת המספר העצום של המעגלים בדוגמה. "בעוד שהמתמטיקאי רינגל הראה שצריך לפחות 5 צבעים בעזרת דוגמה של 9 מעגלים, על מנת להראות ש-5 צבעים אינם מספיקים יש לצייר בצורה מסוימת 10 בחזקת 10,000 מעגלים" מסביר פרופ' שחר סמורודינסקי, מהמחלקה למתמטיקה באוניברסיטת בן-גוריון בנגב. "זה מספר הגדול בהרבה ממספר האטומים ביקום. מדהים שצריך מספר כל כך גדול ולא סביר בכדי להראות את זה".

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

מאמר המחקר המלא, "A solution to Ringel's circle problem", פורסם ב-2024 בכתב העת Journal of the European Mathematical Society (DOI). לפי תקציר המאמר, החוקרים בנו משפחות של מעגלים שבהן גרף המשיקות אינו מכיל מחזורים קצרים (היקפו גדול כרצוננו), ועם זאת מספר הצבעים הדרוש גדול כרצוננו.

מחקר זה (מס' 1065/20) נתמך על ידי הקרן הלאומית למדע.

הכתבה עודכנה באוקטובר 2026 כדי לשקף את פרסום המאמר המלא ב-2024 בכתב עת שפיט, שאישר את הממצאים.

שאלות ותשובות

מהי בעיית רינגל?

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

מה גילתה קבוצת המחקר?

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

מה הקשר בין בעיית רינגל למשפט ארבעת הצבעים?

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

מדוע החוקרים לא הציגו דוגמה מפורשת?

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

אילו תחומים נוגעים בבעיות צביעה כאלה?

לבעיות צביעה כאלה השלכות על הקצאת תדרים לאנטנות סלולריות, שיבוץ טייסים לטיסות ושיבוץ משימות עבודה למכונה.

למאמר המדעי: A solution to Ringel's circle problem (arXiv)

עוד בנושא באתר הידען

• בינה מלאכותית מסייעת לפתור בעיות מתמטיות פתוחות, בהן בעיית ארדוש בת 60 שנה
• בינה מלאכותית ובעיות המתמטיקה של ארדוש: מה באמת הוכח ב-2026
• ניתוח תשבצי סודוקו בעזרת תורת הגרפים מוביל לבעיות פתוחות במתמטיקה
• פרופ' נוגה אלון מאונ' ת"א ופרינסטון זכה בפרס שאו היוקרתי למתמטיקה
• פרס וולף במתמטיקה לשנת 2024 מוענק במשותף לפרופסורים עדי שמיר ונוגה אלון