בעיה- עזרהו
- פותח הנושא tomiitom2
- פורסם בתאריך
המשך עזרה
ראשית תודה רבה לכם על התגובות והרמזים!
לצערי, בבושת פנים ובתסכול למרות שניראה ש״פזרתם״ בפניי רמזים רבים לא הגעתי לטענות שמפרטות את הלוגיקה/אלגוריתם לפתרון הסעיפים.
לגבי הרמז הראשון:״לסעיף א', כדאי לחשוב על סכום כל האיברים בלוח: בהנתן לוח תחילי, האם קיים מספר שסכום כל האיברים בלוח לא יעבור אותו, לא משנה איזה רצף פעולות נעשה. בנוסף, מה פעולה אחת כזו עושה לסכום כל האיברים?״
-אז הסתכלתי על סכום כל האיברים כאשר פיזרתי באקראי מספרים שלמים שונים מאפס. והמסקנה לגבי ה״מספר״ שאף סכום לא יעבור אותו היא שזה סכום הערכים המוחלטים של כל המספרים (כוונה: ערך מוחלט על כל אחד מהמספרים המופיעים בלוח). כאשר ערך של סכום זה גדול או שווה לכל לוח שניצור.
-המבט היה בעיקר על לוחות זוגיים (2*2 , 4*4 וכו׳) ופיזור אקראי של מספרים העונים לדרישה.
-השוואתי בין הסכום לאחר הפעלה אחת (על כל עמודה או שורה) לבין סכום מקסימלי (ערכים מוחלטים) וסכום של לוח נתון. ולא מצאתי דפוס ברור.
- מה שכן הבחנתי שבמקרים לא טריוויאלים (שלא ניתן להפוך את כל הלוח למספרים חיוביים-למשל, לוח שכולו מספרים שליליים או לוח שבו המשבצות בחיוביות ושליליות משובצות כמו שחמט (מצאתי דרך להפוך את כולו לחיובי). במצב זה קיימים מצבים סימטריים בסכומי כל הלוח (סכום אחד חיובי והאחר אותו ערך בסימן שלילי). אך לא הוביל אותי למסקנה מסוימת.
״לסעיף ב', הראה תחילה שסדר הפעולות לא משנה.״
פריוויליגייה שאמרתי שאחשוב עליה לאחר שאוכיח את סעיף א׳.
רמז שני:״אם הופכים שורה\עמודה מסוימת מספר זוגי של פעמים ( גם אם בין כל פעולה יש פעולות על עמודות\שורות אחרות) זה כאילו לא הפכנו אותה בכלל.״
כנראה שלא הבנתי זאת נכון כי מצאתי דוגמא נגדית. אולי הכוונה אם מפעילים את האופרטור על מספר בטבלה מספר זוגי של פעמים?
רמז שלישי:״בהנתן מצב התחלתי, והופכים את כל ה 100 שורות וגם את כל ה 100 עמודות חוזרים למצב ההתחלתי.״
מזה אני מסיק שאולי בהפעלת האופרטור קיימת סדרת מספרים (סכום כולל של הלוח או קומבינציות) בעלות מחזוריות ולכן קיימת הפעלה שבה הסכום בכל שורה או עמודה הוא מקסימלי. אך עדיין להתקדם מפה ואיך לקשר את זה אין לי מושג.
דיי שברתי את הראש על כיוון הרמזים אך ללא הועיל.
אשמח לעוד עזרה או הכוון…
תודה מראש.
ראשית תודה רבה לכם על התגובות והרמזים!
לצערי, בבושת פנים ובתסכול למרות שניראה ש״פזרתם״ בפניי רמזים רבים לא הגעתי לטענות שמפרטות את הלוגיקה/אלגוריתם לפתרון הסעיפים.
לגבי הרמז הראשון:״לסעיף א', כדאי לחשוב על סכום כל האיברים בלוח: בהנתן לוח תחילי, האם קיים מספר שסכום כל האיברים בלוח לא יעבור אותו, לא משנה איזה רצף פעולות נעשה. בנוסף, מה פעולה אחת כזו עושה לסכום כל האיברים?״
-אז הסתכלתי על סכום כל האיברים כאשר פיזרתי באקראי מספרים שלמים שונים מאפס. והמסקנה לגבי ה״מספר״ שאף סכום לא יעבור אותו היא שזה סכום הערכים המוחלטים של כל המספרים (כוונה: ערך מוחלט על כל אחד מהמספרים המופיעים בלוח). כאשר ערך של סכום זה גדול או שווה לכל לוח שניצור.
-המבט היה בעיקר על לוחות זוגיים (2*2 , 4*4 וכו׳) ופיזור אקראי של מספרים העונים לדרישה.
-השוואתי בין הסכום לאחר הפעלה אחת (על כל עמודה או שורה) לבין סכום מקסימלי (ערכים מוחלטים) וסכום של לוח נתון. ולא מצאתי דפוס ברור.
- מה שכן הבחנתי שבמקרים לא טריוויאלים (שלא ניתן להפוך את כל הלוח למספרים חיוביים-למשל, לוח שכולו מספרים שליליים או לוח שבו המשבצות בחיוביות ושליליות משובצות כמו שחמט (מצאתי דרך להפוך את כולו לחיובי). במצב זה קיימים מצבים סימטריים בסכומי כל הלוח (סכום אחד חיובי והאחר אותו ערך בסימן שלילי). אך לא הוביל אותי למסקנה מסוימת.
״לסעיף ב', הראה תחילה שסדר הפעולות לא משנה.״
פריוויליגייה שאמרתי שאחשוב עליה לאחר שאוכיח את סעיף א׳.
רמז שני:״אם הופכים שורה\עמודה מסוימת מספר זוגי של פעמים ( גם אם בין כל פעולה יש פעולות על עמודות\שורות אחרות) זה כאילו לא הפכנו אותה בכלל.״
כנראה שלא הבנתי זאת נכון כי מצאתי דוגמא נגדית. אולי הכוונה אם מפעילים את האופרטור על מספר בטבלה מספר זוגי של פעמים?
רמז שלישי:״בהנתן מצב התחלתי, והופכים את כל ה 100 שורות וגם את כל ה 100 עמודות חוזרים למצב ההתחלתי.״
מזה אני מסיק שאולי בהפעלת האופרטור קיימת סדרת מספרים (סכום כולל של הלוח או קומבינציות) בעלות מחזוריות ולכן קיימת הפעלה שבה הסכום בכל שורה או עמודה הוא מקסימלי. אך עדיין להתקדם מפה ואיך לקשר את זה אין לי מושג.
דיי שברתי את הראש על כיוון הרמזים אך ללא הועיל.
אשמח לעוד עזרה או הכוון…
תודה מראש.
לגבי סעיף א
נתון מצב התחלתי .
אם בכל צעד אתה בוחר שורה או עמודה כלשהיא שסכומה שלילי והופך אותה, מה יקרה לסכום כל המספרים על הלוח ?
האם יתכן שלאחר סידרה כזו של צעדים תחזור למצב לוח שכבר היה ?
----------------
ברמז השני ( שמכוון לסעיף ב ) התכוונתי שאם אתה הופך את אותה שורה (או עמודה) מספר זוגי של פעמים אז כאילו שהפכתה אותה 0 פעמים , ואם הפכתה אותה מספר אי זוגי של פעמים אז כאילו שהפכתה אותה רק פעם אחת בלבד.
במילים אחרות אם הפכתה שורה מסוימת ( או עמודה ) N פעמים אז זה שקול לכך שהפכתה אותה רק N מוד 2 פעמים
נתון מצב התחלתי .
אם בכל צעד אתה בוחר שורה או עמודה כלשהיא שסכומה שלילי והופך אותה, מה יקרה לסכום כל המספרים על הלוח ?
האם יתכן שלאחר סידרה כזו של צעדים תחזור למצב לוח שכבר היה ?
----------------
ברמז השני ( שמכוון לסעיף ב ) התכוונתי שאם אתה הופך את אותה שורה (או עמודה) מספר זוגי של פעמים אז כאילו שהפכתה אותה 0 פעמים , ואם הפכתה אותה מספר אי זוגי של פעמים אז כאילו שהפכתה אותה רק פעם אחת בלבד.
במילים אחרות אם הפכתה שורה מסוימת ( או עמודה ) N פעמים אז זה שקול לכך שהפכתה אותה רק N מוד 2 פעמים
המשך
באמת תודה על ההכוונים והעזרה!
עדיין לא הגעתי לניסוח של טענות משכנעות בנכונות לכל מצב תחילי.
-אם אני הופך כל שורה או עמודה שסכומה שלילי, סכום הלוח הכולל גדול או שווה לסכום הלוח הכולל הקודם.(מסקנה: מכיוון שיש סכום שלא ניתן לעברו אז ישנה מגבלה לתהליך).
-אפשר לחזור למצב לוח שכבר היה (בפרט להתחלה) אם מפעילים את האופרטור שוב על עמודה שסכומה חיובי (שכבר שונתה פעם אחת). הכוונה הפיכה של כל השורות ולאחר מכן את כל העמודות (או להיפך). אך לדעתי לא ניתן לחזור לאותו המצב אם התהליך הוא כפי שתיארת- הפיכת כל שורה או עמודה שבה הסכום שלילי. לדעתי, התהליך מסתיים בכך ש״המשימה״ מבוצעת (כל שורה או עמודה סכמה גדול או שווה לאפס) אך אני לא מצליח לנסח זאת כטיעון משכנע.
*ברור שאפשר להפוך את כל השורות לסכום אי-שלילי לאחר הפעלה על כל שורה שסכומה שלילי. כעת, נותר לשנות את כל העמודות (אם קיימות) שסכומן שלילי ואז לאחר שינוי שלהן ייתכן שינינו חלק מהשורות שכבר דאגנו שיהיו אי-שליליות ואז שוב להפעיל כך עד שנגיע לכך שגם העמודות וגם השורות יהיו עם סכום אי שלילי... ..לפי אנטואיצייה לאחר מספר פעולות כאלה תתקבל התוצאה הרצויה אבל אני לא מצליח לגבש מסקנה מדוע זה קורה?? אשמח מאוד להבין זאת..
אינטואטיבית שיכנעת אותי, וגם כל הדוגמאות שעשיתי חיזקו את האינטואיציה.
תודה רבה !
באמת תודה על ההכוונים והעזרה!
עדיין לא הגעתי לניסוח של טענות משכנעות בנכונות לכל מצב תחילי.
-אם אני הופך כל שורה או עמודה שסכומה שלילי, סכום הלוח הכולל גדול או שווה לסכום הלוח הכולל הקודם.(מסקנה: מכיוון שיש סכום שלא ניתן לעברו אז ישנה מגבלה לתהליך).
-אפשר לחזור למצב לוח שכבר היה (בפרט להתחלה) אם מפעילים את האופרטור שוב על עמודה שסכומה חיובי (שכבר שונתה פעם אחת). הכוונה הפיכה של כל השורות ולאחר מכן את כל העמודות (או להיפך). אך לדעתי לא ניתן לחזור לאותו המצב אם התהליך הוא כפי שתיארת- הפיכת כל שורה או עמודה שבה הסכום שלילי. לדעתי, התהליך מסתיים בכך ש״המשימה״ מבוצעת (כל שורה או עמודה סכמה גדול או שווה לאפס) אך אני לא מצליח לנסח זאת כטיעון משכנע.
*ברור שאפשר להפוך את כל השורות לסכום אי-שלילי לאחר הפעלה על כל שורה שסכומה שלילי. כעת, נותר לשנות את כל העמודות (אם קיימות) שסכומן שלילי ואז לאחר שינוי שלהן ייתכן שינינו חלק מהשורות שכבר דאגנו שיהיו אי-שליליות ואז שוב להפעיל כך עד שנגיע לכך שגם העמודות וגם השורות יהיו עם סכום אי שלילי... ..לפי אנטואיצייה לאחר מספר פעולות כאלה תתקבל התוצאה הרצויה אבל אני לא מצליח לגבש מסקנה מדוע זה קורה?? אשמח מאוד להבין זאת..
אינטואטיבית שיכנעת אותי, וגם כל הדוגמאות שעשיתי חיזקו את האינטואיציה.
תודה רבה !
אם אתה הופך כל שורה או עמודה שסכומה שלילי
אז סכום הלוח הכולל יהיה גדול ממש ( ולא שווה כמו שאמרתה ) לסכום הלוח הכולל הקודם. (ויש חסם תחתון חיובי לתוספת זאת )
האלגוריתם הוא כזה:
1) בדוק סכום כל שורה וכל עמודה, אם אין אף סכום שלילי אז סיימנו.
2) בחר עמודה או שורה כלשהיא שסכומה שלילי והפוך אותה.
3) חזור ל 1.
טענה:
אלגוריתם זה יביא אותנו אחרי מספר סופי של צעדים למצב שסכום כל אחד מהשורות וכל אחד מהעמודות הוא אי שלילי ( לכל מצב התחלתי של הלוח).
הוכחה:
נניח בשלילה שלא נקבל אף פעם מצב שכל אחד מהשורות והעמודות סכומו שלילי, אז האלגוריתם לא יגמר ויהיו אין סוף צעדים. בכל צעד כזה סכום הלוח הכולל גדל ממש ( ובגלל המספר הסופי של משבצות אז התוספת בכל צעד לסכום הכולל גדולה שווה למספר חיובי נתון עבור לוח מסוים ),
ולכן אחרי מספר סופי של צעדים נעבור את הסכום המכסימלי האפשרי ( שזה סכום כל הערכים המוחלטים ) שזה לא יתכן.
אז סכום הלוח הכולל יהיה גדול ממש ( ולא שווה כמו שאמרתה ) לסכום הלוח הכולל הקודם. (ויש חסם תחתון חיובי לתוספת זאת )
האלגוריתם הוא כזה:
1) בדוק סכום כל שורה וכל עמודה, אם אין אף סכום שלילי אז סיימנו.
2) בחר עמודה או שורה כלשהיא שסכומה שלילי והפוך אותה.
3) חזור ל 1.
טענה:
אלגוריתם זה יביא אותנו אחרי מספר סופי של צעדים למצב שסכום כל אחד מהשורות וכל אחד מהעמודות הוא אי שלילי ( לכל מצב התחלתי של הלוח).
הוכחה:
נניח בשלילה שלא נקבל אף פעם מצב שכל אחד מהשורות והעמודות סכומו שלילי, אז האלגוריתם לא יגמר ויהיו אין סוף צעדים. בכל צעד כזה סכום הלוח הכולל גדל ממש ( ובגלל המספר הסופי של משבצות אז התוספת בכל צעד לסכום הכולל גדולה שווה למספר חיובי נתון עבור לוח מסוים ),
ולכן אחרי מספר סופי של צעדים נעבור את הסכום המכסימלי האפשרי ( שזה סכום כל הערכים המוחלטים ) שזה לא יתכן.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.