אינווריאנט

[srulikbd]

אינווריאנט

על המעגל נתונות נקודות כחולות ואדומות. מותר להוסיף נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה או להסיר נקודה אדומה ולשנות את הצבעים של הנקודות השכנות שלה בעבר (אסור להשאיר פחות מ-2 נקודות על המעגל). הוכח\י כי אי אפשר להעביר רק ע"י הפעולות האלה מעגל עם שתי נקודות אדומות למעגל עם שתי נקודות כחולות.

 

[עריסטו]

../images/Emo62.gif

נעשה כך: נקודה כחולה = כפל ב - 1- נקודה אדומה = הוספת 1. מחשבים מודולו 3. כ מסמל נקודה כחולה, א מסמל נקודה אדומה. מתקבל: ככ = כפל ב - 1, ואחרי הוספת נקודה מתקבל אאא = הוספת 3 = הוספת 0. אכ = הוספת 1 וכפל ב - 1-, כלומר מ-x מתקבל zzz -x-1 zzz. אחרי הוספת נקודה אדומה מתקבל כאא = כפל ב - 1-, הוספת 1 והוספת 1, כלומר מ-x מתקבל zzz -x+2 zzz. ניתן להמשיך ולבדוק את כל האפשרויות להוספת או מחיקת נקודה אדומה, ומקבלים שבכל מקרה הפונקציה המתקבלת מהרכבת כל הנקודות לפי הסדר אינה משתנה. אבל: מצב התחלתי - אא = הוספת 2 מצב סופי - ככ = כפל ב - 1 ואלה שתי פונקציות שונות. לכן לא ניתן להגיע מ-אא ל-ככ.

 

[srulikbd]

לא הבנתי

זה אינווריאנט? מתחילים מ2 נק' אדומות אא ואז זה שווה 2, אח"כ מוסיפים נק' אדומה זה הופך ל אככ שזה +1*-1*-1=1..זה אמרו להיות שווה 2? והאם זה תחפושת של האינווריאנט http://teramips.com/totsite/Solutions/Ikarit/T1/Autumn/S_1_A_Y_I1.doc

 

[עריסטו]

הסבר

האינווריאנט הוא פונקציה ולא מספר. נקודה אדומה = הוספת 1. לכן אא = הוספת 2, כלומר הערך של אא הוא הפונקציה zzz f(x)=x+2 zzz. אם מוסיפים נקודה אדומה זה הופך ל-כאכ (ולא אככ). כאכ זה: כ זה הפונקציה f(x)=-x א זה הפונקציה g(x)=x+1 עוד כ זה הפונקציה h(x)=-x לכן אככ זה h(g(f(x)))=x-1, ואכן בחישוב מודולו 3 זה זהה לערך של אא.

 

[עריסטו]

בשורה האחרונה - כאכ ולא אככ