בתשובה לראובן, 31/05/04 22:26
 |
|
 |
||
|
||||
 |
הבעייה ידועה בשם The Kissing Problem או The Kissing Number, וגוגל יודע עליה לא מעט. היא גם קשורה, באופן לא מפתיע, לבעיית האריזה של כדורים עליה גם כבר דיברנו קצת (קפלר והיילס וכו'). |  |
 |
 |
|
|
|
||
|
||||
|
אני אבדוק, תודה. זה די מפליא אותי משום שמדובר במספרים שלמים. הרי בטח יש חסם לכל מימד: לא יותר מ M ולפחות N. מכיוון שנשארו M-N ערכים, הייתי מצפה שיהיה אפשר לבדוק כל מקרה לגופו, אפילו אם יש רצף של דרכים לסדר אותם סביב הכדור המרכזי. מצד שני, אני נזכר פתאום שהבעיה של חלוקה אופטימלית של מטענים נקודתיים על כדור היא גם בעיתית. אזהרה: גישה של פיסיקאי [לשעבר] לפניך: אולי יש הרחבה לכיוון של כמה כדורים זהים אבל קטנים מהכדור המרכזי אפשר לשים? בגבול שהכדורים העוטפים ממש קטנים, בטח יש אסיפטוטיקה של קליפה. אולי אפשר לחשב את התיקון הראשון ( והשני וכולי) לגבול הזה? אולי אפשר להשתמש בזה כדי לקבל חסמים? |
|
|
|
|
|
|
||
|
||||
|
יש חסמים, אבל בדיקת כל מקרה לגופו היא קשה מאוד. אם אתה מחפש ומחפש סידור של 24 כדורים במימד 4 ולא מוצא, איך תדע שאין כזה? לא חסרות בעיות פתוחות שהתשובה להן היא מספר שלם וקטן למדי בתחום ידוע. למשל, מספר האנשים הדרושים כדי להבטיח שיהיו או (חמישה שאינם מכירים זה את זה) או (חמישה שכולם מכירים זה את זה) הוא מספר שלם בין 43 ל-49, אבל ככל הידוע לי לא ידוע מהו. ה"גישה של הפיסיקאי" שתיארת היא נאה ואף נדונה בהרחבה, אך אינני יודע אם החסמים ההדוקים ביותר באים ממנה. |
|
|
|
|
|
|
||
|
||||
|
אנקדוטה: מיטשל פייגנבאום ( זה מהקבוע) פעם היה במסיבה ופגש בעל חברת מפות ( ראנד מקנאלי אאל"ט). לאחר שהחליפו דברי נימוסין, וכשהבין האטלסאי שלפניו עומד מדען מהמדרגה הראשונה, אמר לו "אם אתה כל כך חכם ..." וסיפר לו שיש הרבה בעיות בתחום עריכת אטלסים. מה למשל? - איך לכתוב את שם העיר ליד העיר, בלי לפגוע בשמות אחרים. לאחר כמה זמן, בא פייגנבאום עם הרעיון הבא: הוא שרטט אליפסה סביב כל שם של עיר וקיבע את השפה במרכז העיר. אחר כך הוא הדביק לכל אליפסה (במחשב) מטען חשמלי, ונתן להם ( בסימולציה) להסתדר. מכיוון שהאליפסות דחו זה את זה, אבל כל אחת מהם נישקה את העיר הרלוונטית, הוא פתר בצורה אוטומטית בעיה שעד אז היו פותרים ידנית. |
|
|
|
|
|
|
||
|
||||
|
אחת הדרכים החשובות לצייר גרפים1 היא "שיטת הגומייה" המתבססת על משפט של Tutte. כדאי מאוד לנסות את התוכנה שיש כאן: (כן, סליחה, מיקרוסופט. מה לעשות שלאצי לובאס עובד שם). בגדול, קובעים כמה קדקודים בנעצים למישור, ונותנים ליתר לנוע בחופשיות כשהצלעות מתנהגות כמו גומיות. יופי של דבר. 1 במובן הקומבינטורי: אוסף של קדקודים וצלעות. |
|
|
|
|
|
|
||
|
||||
|
באופן דומה, הדרך למצוא את קבוצת הקווים בעלי סך האורך הקצר ביותר המקשרים בין אוסף נקודות ("עץ שטיינר מינימלי"): לייצג את הנקודות כמסמרים נעוצים בעץ, ולכסות בלוח עץ נוסף; לטבול את שני הלוחות עם המסמרים באמבט מי סבון, ולהוציא. בין המסמרים יימתחו "קירות" של מי סבון העונים על הדרישה (בעולם אידיאלי, לפחות; במציאות, בעיות כמו זרמים במים, תזוזה של היד בעת הכנסת/הוצאת הלוח, וכו' פוגעות במושלמות הפתרון). (Dewdney, The Armchair Universe, בפרק "Analog Gadgets".) |
|
|
|
|
|
|
||
|
||||
|
יש המון שיטות לקבל חסמים על מספר הכדורים (בספר Sphere Packing של Conway ו- Sloane, שאלון הפנה אליו למעלה, מתוארות כל השיטות שאפשר להעלות על הדעת, ועוד 17 שאי-אפשר). אחת השיטות היא לחשוב על "כמה כדורים ברדיוס r אפשר למקם סביב כדור ברדיוס 1" כפונקציה (לא רציפה) של r. אבל העובדה שיש מספר קטן של אפשרויות אינה הופכת את השאלה לקלה יותר. במימד 4, כמה כדורים אפשר למקם סביב כדור אחד באותו גודל: 24 או 25? לא יודעים. הנה עוד בעיה, מתחום אחר לחלוטין: ידוע שפרט למספר סופי של יוצאי דופן, אפשר להציג כל מספר שלם כסכום של 7 מעוקבים (מספרים מהצורה n^3). ידוע גם ששלושה מעוקבים לא מספיקים. האם צריך 7, או אולי 6, 5 או 4? לא יודעים. (למגגלים, זה מקרה פרטי של בעיית Waring; המספר הלא ידוע נקרא (G(3). |
|
|
|
|
|
|
||
|
||||
|
לא פיקפקתי שאכן לא יודעים. סתם נהנתי בדפוס רם מהמצב. | |
|
|
|
|
|
||
|
||||
|
בעייה פתוחה מפתיעה למדי (אם כי לא במיוחד חשובה), שנזכרתי בה כי החסמים בה דומים מאוד לאלו של (G(3 שהזכיר עוזי. רוצים לצבוע את המישור, ואסור שתהיינה שתי נקודות במרחק 1 ס"מ באותו צבע. כמה צבעים צריך? ("לצבוע את המישור" פירושו, פשוט, להעניק לכל נקודה במישור איזשהו צבע). קל לראות שעם שני צבעים אי-אפשר: חישבו על משולש שווה צלעות עם צלע של 1 ס"מ. לשניים מהקדקודים חייב להיות אותו הצבע, ונכשלנו. חידה חמודה: להראות שעם שלושה צבעים, גם אי אפשר. חידה קצת פחות אלגנטית: להראות שעם שבעה צבעים, כן אפשר. המצב ל-4, 5 ו-6 צבעים אינו ידוע. |
|
|
|
|
|
|
||
|
||||
|
אז כנראה שיודעים כבר: 24. (הקישור השני בתגובה 248751) | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |