חידה על לוח משבצות

[yuvalmadar]

חידה על לוח משבצות

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

 

[Abbe Faria]

ניסיון...

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

 

[yuvalmadar]

לא הבנתי בדיוק

איך תכסה לוח של 4x4 עם 3 איקסים?

 

[Abbe Faria]

טעות...

התבלבלתי...