לפניכם הבעיה הבאה: במישור מסומנות n נקודות. כמה ישרים אפשר להעביר דרכן?
צדקתם! זו דוגמה לניסוח רשלני ולא ברור לבעיה. הפעם הרשלנות זועקת לשמיים, אך לעתים היא נסתרת.
למה הכוונה? כמה ישרים אפשר להעביר דרך הנקודות? איך להעביר? האם הכוונה היא ש"כל ישר יכיל בדיוק נקודה אחת" או "לפחות נקודה אחת"?
במקרה זה הניסוחים אינם משנים את התוצאה, כי דרך נקודה יחידה אפשר להעביר אינסוף ישרים. אך אם ברצוננו להתעמק בבעיה, עלינו לנסחה בדיוק: "במישור נתונה קבוצת n נקודות. כמה ישרים המכילים לפחות m<n נקודות אפשר ניתן להעביר דרכן?"
ראינו כי כאשרm=1 התוצאה היא אינסוף. אך מה קורה כאשר m=2, כלומר כאשר כל ישר מכיל לפחות שתי נקודות?
כיוון שמכל נקודה אפשר למתוח ישר לכל אחת משאר n-1 הנקודות וכל ישר נספר כך פעמיים, פעם לכל נקודה – התשובה היא לכאורה 2/n(n-1). לדוגמה: בין 5 נקודות ניתן להעביר 10 ישרים. אך מיד צצה הבעיה: אילו כל הנקודות היו על ישר אחד, היינו יכולים להעביר רק ישר אחד!
נסו לחשב את כל האפשרויות למספר הישרים שניתן להעביר בין 5 נקודות בסידורים השונים במישור. אם כך – על מה ענינו כשהשבנו "10"?
נדמה שהתשובה פשוטה: ענינו על מקרה שבו אין שלוש נקודות על ישר אחד. התשובה הזאת נכונה, אך היא לא תועיל לנו כשנחזור לשאלה הכללית: כמה ישרים ניתן להעביר בין n נקודות כאשר כל ישר מכיל לפחות m נקודות? אותו מערך שאפשר לנו עשרה ישרים המכילים שתי נקודות יאפשר רק 0 ישרים המכילים שלוש נקודות! לכן עדיף לנסח את הבעיה על ידי שתי השאלות הבאות:
א) בקבוצה נתונה של n נקודות, כמה ישרים המכילים m נקודות אפשר להעביר דרכן?
ב) מהו מספר הישרים המרבי שמכילים לפחות m נקודות שאפשר להעביר בקבוצת n נקודות שערוכות כרצוננו?
תיווכחו שהתשובה לשאלה הראשונה מורכבת מעט, ואילו התשובה לשאלה השניה מעלה כמה בעיות מעניינות. בהן נדון בבלוגריתמוסים הבאים.
בהצלחה,
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
