בבלוגריתמוס 12 העלינו את נושא מספר הישרים שאפשר להעביר דרך נקודות של קבוצה. להלן כל האפשרויות להעביר ישרים המכילים לפחות שתי נקודות בקבוצה של חמש נקודות:
 |
חמש נקודות – עשרה ישרים
ראינו כי יש חמש אפשרויות: 1, 5, 6, 8 ו-10. ככל שנגדיל את n כך יגדל מספר האפשרויות השונות, אך המספר המקסימלי יהיה תמיד n(n-1)/2, ונוכל תמיד ליצור מערך נקודות שיתן לנו את התוצאה הזאת בכך שנימנע מבחירה בשלוש נקודות שנמצאות על אותו ישר.
ועתה לשאלה א' מבלוגריתמוס 12. ראשית נדון במקרה קל יחסית: נתבונן בריבוע של תשע נקודות. כמה ישרים המכילים לפחות שתי נקודות אפשר להעביר בו?
|
|
במקרה המקסימלי, שבו כל שתי נקודות קובעות ישר שונה – נקבל 9x8/2=36. אולם בריבוע קיימים שמונה ישרים שמכילים שלוש נקודות, כשכל ישר כזה נספר שלוש פעמים במקום פעם אחת ויחידה! לכן מספר הישרים הנכון הוא 20=36-24+8.
נכליל את התוצאה למקרה של כלn לגבי ישרים שמכילים שתי נקודות לפחות:
נתבונן בכל התת-קבוצות המקסימליות, שכל נקודותיהן מצויות על ישר יחיד ומספרן לפחות 3. קבוצה כזו, שמכילה למשל חמש נקודות, מכילה גם קבוצות חלקיות של 3 ו-4 שמצויות על אותו ישר, אך הן אינן מקסימליות. ברור שלשתי קבוצות כאלה יש לכל היותר נקודה משותפת יחידה, כי אילו היו שתיים כאלה היו הקבוצות זהות!
לדוגמה, יש לנו עשר נקודות ושלוש קבוצות מקסימליות של 3, 3 ו-4 3,4 נקודות. אזי מספר הישרים הזהים בכל קבוצה של 3 הוא 3, ובקבוצה של 4 הוא 4x3/2=6. מספר הישרים המקסימלי לעשר נקודות הוא10x9/2=45 . לכן מספר הישרים בקבוצה יהיה: 45-3-3-6+3=36, ובאופן כללי: מספר הישרים שווה למספר המקסימלי פחות כל הישרים הכלולים בתת-הקבוצות המקסימליות ועוד מספר הקבוצות המקסימליות (כי כל קבוצה מקסימלית תורמת ישר יחיד).
לכאורה, ההגדרה הזו צריכה להתאים לכל m נקודות, לאו דווקא ל-2 – אך עבור מספר גדול מ-2 מתעוררת בעיה: מהו המספר המקסימלי? האם יש נוסחה דומה ל-nx(n-1)/2 עבור m>2?
בכך נדון בבלוגריתמוס הבא.
בהצלחה,
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
