חידה

[הפרבולה]

חידה

נתון לוח משבצות ריבועי N*N משבצות. בכל משבצת רשום מספר ממשי.
בכל צעד יש לבחור שורה או עמודה ולהפוך את סימני כל N המספרים באותה שורה \עמודה ( כל מספר חיובי יהפוך לשלילי להיפך ).
המטרה: להגיע למצב שלא ישאר אף עמודה או שורה שסכום המספרים בה שלילי.
1) האם זה אפשר תמיד ?
2) בכמה צעדים מכסימום אפשר להגיע לזה?

 

[עריסטו]

נסיון

1. זה אפשרי תמיד. יש מספר סופי של מצבים שניתן להגיע אליהם על ידי פעולות היפוך כנ"ל. מבין כל המצבים האלה נתבונן במצב בו סכום המספרים מקסימלי. במצב הזה אין שורה או עמודה שליליים - אחרת היה ניתן להפוך את השורה/עמודה וזה מגדיל את סכום המספרים, בניגוד לנתון שהסכום מקסימלי.
2. מצאתי רק שמכל מטריצה אפשר לקבל לכל היותר 2 בחזקת 2N-1 מטריצות על ידי היפוך, לפי זה תמיד יש פתרון בן zzz 2^(2N-1)-1 zzz צעדים או פחות, אבל אני לא יודע מה המקסימום האמיתי.

 

[הפרבולה]

לגבי 1 נכון

לגבי 2 אולי לא ניסחתי את השאלה היטב, מבקשים מאיתנו להגיע למטרה ( שהסכום של כל שורה ושל כל עמודה יהיה לא שלילי ) במינימום צעדים ( צעד = הפיכת שורה או עמודה ) , מהו המינימום במקרה הגרוע .

ואכן יש 2 בחזקת 2N-1 מטריצות שונות שאפשר להגיע אליהם

 

[עעעערררר]

לגבי 2

ברור שסדר הצעדים לא משנה, וכן שהצעדים הם אינבולוציות (כלומר, אין טעם להפוך את אותה שורה או עמודה פעמיים). לכן, כל מסלול הוא באורך לכל היותר 2N.
נשים לב שכל אוסף צעדים נותן אותה תוצאה כמו המשלים שלו (הופכים את השורות והעמודות שלא הפכנו במסלול המקורי), ולכן, אפשר להסתפק ב-N צעדים.
(דוגמא למקרה הגרוע: מטריצה אלכסונית עם איברים שליליים על האלכסון)

 

[הפרבולה]

נכון

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

אז אם עשינו מסלול מסוים והגענו מ A למצב B. כעת נהפוך את כל השורות והעמודות ושוב נגיע ל B, אבל פעולה זו שקולה כאילו התחלנו מ A ועשינו את המשלים של המסלול המסוים.

 

[עריסטו]

חידות המשך (אני לא יודע מה הפתרון)

בשתי חידות ההמשך נניח שבכל צעד הופכים שורה/עמודה שבה סכום המספרים שלילי. כמו שרואים מהפתרון לסעיף 1 התהליך הזה חייב להסתיים.
3. רוצים לסיים במספר צעדים מינימלי, כמה צעדים נדרשים במקרה הגרוע?
4. אם לא מנסים לסיים במספר צעדים מינימלי, כמה צעדים יבוצעו במקרה הגרוע?

 

[עריסטו]

עוד

גם בשתי חידות ההמשך הבאות נניח שבכל צעד הופכים שורה/עמודה שבה סכום המספרים שלילי. כמו שרואים מהפתרון לסעיף 1 התהליך הזה חייב להסתיים.
5. האם קיים אלגוריתם יעיל שמוצא פתרון?
6. האם קיים אלגוריתם יעיל שמוצא פתרון מינימלי?
בחידות הבאות נניח שבכל צעד הופכים שורה/עמודה כלשהי.
7. האם קיים אלגוריתם יעיל שמוצא פתרון?
8. האם קיים אלגוריתם יעיל שמוצא פתרון מינימלי?

 

[הפרבולה]

השערה

אולי האלגוריתם היעיל הוא אלגוריתם "החמדן":
בכל צעד בוחרים את אותה שורה \עמודה שסכומה הוא הכי שלילי ואותו הופכים.....