עוד חידת טבלה

[עריסטו]

עוד חידת טבלה

נתונה טבלה ריבועית של מספרים (מספר השורות שווה למספר העמודות). ידוע שאין בטבלה שתי שורות זהות. הוכיחו כי ניתן למחוק מהטבלה טור אחד, כך שעדיין לא יהיו בטבלה שתי שורות זהות.

 

[ייץ]

נסיון

הוכחה באינדוקציה בדיקה עבור תבנית 2X2 היא טריוויאלית. (או A1!=B1 או A2!=B2 או שניהם). נמחוק את הטור כך שישאר הטור השונה. נניח שהטענה נכונה עבור תבנית NXN ונוכיח לתבנית (N+1)X(N+1) בתבנית (N+1)X(N+1) נסתכל על N השורות העליונות ועל N העמודות הימניות. 1) אם לא קיימת בתבנית NXN הזאת שתי שורות זהות אז לפי הנחת האינדוקציה אפשר להוריד טור כך שעדיין לא יהיו שתי שורות זהות. נסתכל על השורה (N+1) התחתונה ביותר. אם בהורדת הטור שהזכרתי קודם שורה זאת תהיה שונה מכל השורות האחרות נוריד את הטור הזה, אחרת נוריד את הטור האחרון. כך יתקיים התנאי שכל השורות שונות. (כיוון שהשוני בין השורה התחתונה לזאת השווה לה היא באיבר שנמצא בעמודה השמאלית ביותר). 2) אם בתבנים שהזכרתי ב 1) NXN קימות שתי שורות זהות אז נבחר את התבנית NXN של N השורות העליונות ו N העמודות השמאליות. ההוכחה בדיוק כמו שהסברתי ב 1). מקווה שלא טעיתי.

 

[ייץ]

תיקון

לגבי מצב 2) בתבנית (N+1)X(N+1) יש (N+1) בריבוע תבניות ריבועיות NXN. (נוצרות על ידי הורדת שורה אחת ועמודה אחת). אם בכל אחת מהתבניות יש לפחות שתי שורות זהות נקבל שגם בתבנית הגדולה (N+1)X(N+1) יש שתי שורות זהות. (זה נכון מטעמי ספירה של האפשרויות). נבחר את התבנית בה אין 2 שורות זהות.

 

[עריסטו]

../images/Emo127.gif