מחיקת נקודות

[עריסטו]

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

 

[הפרבולה1]

נתחיל מהשורה הראשונה שיש שם נקודה אחת. ישר אחד צריך לעבור שם ( נקרא לו ישר A1 ), A1 חותך את הישר האופקי שמכיל את השורה השניה ( שיש שם 2 נקודות) לכול היותר בנקודה אחת ולכן חייבים עוד ישר אחד כדי למחק את 2 הנקודות שבשורה השניה ( נקרא לו ישר A2 ).
הישרים A1 A2 חותכים את הישר האופקי המכיל את הנקודות בשורה השלישית ב 2 נקודות לכל היותר, ולכן צריך להיות עוד ישר ( נקרא לו ישר A3 ) כדי למחוק גם את 3 הנקודות של השורה השלישית.

ובצורה דומה רואים שכדי למחוק כל שורה נוספת n חייבים להוסיף עוד ישר An, ולכן כדי למחוק את 10 השורות צריך לפחות 10 ישרים, (9 לא מספיק).

 

[עריסטו]

זו בעצם הוכחה באינדוקציה, אבל לא מספיק מדוייקת (הוכחת רק שאם אנחנו חמדנים ובכל שלב משתמשים במספר הקווים המינימלי, נצטרך קו נוסף לשלב הבא. אבל אולי אפשר לבזבז קווים בשורות הראשונות ולחסוך קווים אחר כך?)
הנה ניסוח מדויק יותר: אם מחקנו את n השורות הראשונות על ידי n קוים, הם מחקו לכל היותר n נקודות מהשורה הבאה, ולכן כדי למחוק אותה צריך קו נוסף. מצד שני אם מחקנו את n השורות הראשונות על ידי יותר מ-n קוים, שוב השתמשנו ב-n+1 קוים לפחות למחיקת n+1 שורות.
הנה הוכחה שונה מעט באינדוקציה:
אם במשולש יש נקודה אחת צריך ישר אחד. אם במשולש יש n שורות נסתכל על השורה שיש בה n נקודות:
1. אם יש ישר שמכיל יותר מנקודה אחת בשורה הזו, אז הוא לא מכיל אף נקודה בשורות האחרות. לפי הנחת האינדוקציה כדי למחוק את הנקודות האחרות צריך n-1 ישרים ובסך הכל n ישרים.
2. אם אין ישר שמכיל יותר מנקודה אחת בשורה הזו, אז כל נקודה בשורה הזו נמחקת על ידי ישר שונה, ושוב צריך n ישרים.