בבלוגים 12 ו-13 העלינו את הבעיה הבאה: במישור קיימות n נקודות. כמה ישרים שונים ניתן להעביר כך שכל ישר יעבור לפחות ב-m נקודות?
פתרנו את הבעיה עבורm=2 בעזרת חישוב המספר המקסימלי האפשרי nx(n-1)/2, ומושג ה"קבוצה מקסימלית". אך מרגע שנבחר ב-m>2, הדברים מסתבכים. איך נחשב מהו המספר המקסימלי האפשרי?
נניח שיש לנו תשע נקודות ואנו רוצים לחשב את המספר המרבי של ישרים העוברים בשלוש נקודות לפחות. נצליח לקבל אותו רק אם נערוך את תשע הנקודות כך שמכל נקודה יצאו ארבעה ישרים, שכל אחד מהם מכיל זוג נקודות נוסף מתוך השמונה הנותרות.
 |
כך, לכאורה, בזוכרנו שכל ישר נספר שלוש פעמים, נקבל 12=9/3*4 ישרים במספר המקסימלי. אך האם אכן אפשר תמיד לערוך את הנקודות במישור במערך מקסימלי?
נבחן דוגמה פשוטה של חמש נקודות: ערך מקסימלי יתקבל אם מכל נקודה יצאו 2 ישרים. כל אחד יכיל זוג נוסף מתוך הארבעה הנותרים, ולפי חישוב נקבל (2*5)/3=3 1/3.
כבר הופעת השליש רומזת שקיימת פה בעיה – הרי אין משמעות לשליש של ישר. לכן יש לכל היותר שלושה ישרים, כלומר המערך המקסימלי התיאורטי אינו אפשרי! אך המצב בשטח גרוע אף יותר: כמה שלא תנסו – לא תמצאו מערך שמכיל יותר משני ישרים!
 |
האם פירוש הדבר הוא שבכל n אין אפשרות להשיג את המקסימום התיאורטי? לא ולא! לדוגמה: חשבו אותו עבור n=6 ,m=3, ונסו לצייר מערך שמקיים אותו.
מכאן אנו מסיקים שלפעמים יש מערך ממשי שמקיים את המספר המקסימלי התיאורטי – ולעתים אין. אם כך, איך נתייחס אליו? האם יש לו חשיבות?
ודאי שכן. נדגים זאת בשאלה: כמה ישרים ייתכנו עבורn=1,000 ,m=10 . האם מיליון? האם מאה? קשה מאוד לדמיין איך ייראה מערך של אלף נקודות – אך מאחר שאם כל נקודה תהיה מקושרת ל-111 תשיעיות, נקבל 111x1,000/10=11,100, כמספר התיאורטי המקסימלי. איננו יודעים אם קיים מערך כזה או אפילו מערך המתקרב למספר הזה, אך לא ייתכן מספר ישרים גדול יותר מזה.
לערך כזה קוראים "חסם עליון", והוא נותן לנו מושג מסוים על גבולות הערך הממשי.
נסו לצייר מערכים מקסימליים עבור m=3 ,n=6-10 והשוו את המספר שקבלתם לחסם העליון.
בבלוג הבא נעסוק בכך.
בהצלחה,
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
