טוב, אז הנה משהו מעניין

[Javali]

טוב, אז הנה משהו מעניין

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

 

[guysoffer]

אז ככה

במשחק רנדומלי שני השחקנים יחברו נקודות, כל עוד נשארו שתי נקודות לא מחוברות (כי ברגע שאחד מהם יחבר את אחת הנקודות, השני מחבר את השנייה ומנצח). כמובן שהנקודות הם פשוט השתיים האחרונות שיחוברו - אני מניח כאן שאין הגבלה - כל נקודה יכולה תיאורטית להתחבר לכל נקודה אחרת.. נותר רק לספור את כמות החיבורים האפשרית ב n-2 נקודות, תחת המגבלות שהזכרת (נקודה לא מקושרת לעצמה, או יותר מפעם אחת לנקודה כלשהי) בשתי נקודות - קו 1 בשלוש נקודות - 3 קווים (2+1) בארבע נקודות -6 קווים (3+2+1) החישוב די פשוט - מנקודה כלשהי (ראשונה) יוצאים קווים לכל האחרות, מהשניה יוצאים קווים לכל נקודה פרט לראשונה.. וכו - סכום של סדרה חשבונית פשוטה. השחקן הראשון מתחיל: אם הסכום זוגי, יאלץ השחקן הראשון לחבר קו לאחת משתי הנקודות ה"אסורות" ראשון, והשחקן השני מנצח. אם הסכום אי-זוגי - השחקן הראשון מנצח. אני הנחתי משחק טוב ביותר של שני בשחקנים, כמובן.

 

[Javali]

הכל טוב, ונשאלת השאלה

זה ברור למה השחקן שהולך לנצח בשיטה הזו יעשה את זה. זה לא כל לך ברור למה זה שהולך להפסיד יעשה את זה, ולכן למה לדעתך זה המשחק הטוב ביותר עבור המפסיד... בפרט - במשחק של 5 נקודות יש 3=n-2 נקודות מלבד השתיים האחרונות. ביניהן יש 3 קווים שזה מספר אי זוגי. לשיטתך השחקן הראשון מנצח. אבל, לשחקן השני יש אסטרטגיה מנצחת: הראשון מחבר שתי נקודות, השני מחבר שתיים אחרות, כל מה שעושה הראשון עכשיו מוביל להפסד.

 

[guysoffer]

צודק.. הממ..

 

[Javali]

ושכחתי: ../images/Emo128.gif

 

[guysoffer]

יש לי כיוון - אבל אני לא מצליח להתקדם עם זה

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

 

[Javali]

ההתחלה נכונה

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

 

[guysoffer]

למה שלושה רכיבי רשירות ?

עם 1000 נרודות, לדוגמא - יהיו הרבה יותר רכיבי קשירות.. יכולים להיות יותר מ400, למשל. פה בדיוק אני מפספס משהו - אני לא מצליח לראות מתי להוסיף רכיב קשירות, ומתי להרחיב - מה נותן כל אחד.

 

[Javali]

מונחים

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

 

[guysoffer]

הבנתי מה שאתה אומר.. מעניין.

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

 

[guysoffer]

ועכשיו לשאר:

זה כנראה פתרון רגרסיבי.. בא נסתכל על המצב כשיש 4 קטעי קשירות - בכל שלב ניתן להוריד קטע קשירות (על ידי צירוף נקודה פנויה, למשל) כלומר - אני אוריד לשלושה קטעי קשירות רק אם אצור מספר אי זוגי של קשתות (אחרת אני מפסיד) נניח מספר הקשתות בכל אחד מהארבע a,b,c,d כל מספר יכול גם להיות 0, כמובן צירוף של שני קטעי קישור. נניח, ללא הגבלת הכלליות: a+b נa יש n קשתות (n>0) ובb יש m קשתות (m>0) לn הקשתות בa יהיו כעת m-1 חיבורים אפשריים חדשים. לm הקשתות בb יהיו כעת n-1 חיבורים אפשריים חדשים. כמות החיבורים החדשה: a+b+m+n-2 ,כלומר צירוף שני תתי קשירות לא משנה את הזוגיות מספר הקשרים.. מעניין. כלומר - אם כמות החיבורים בארבע אי-זוגית - אני מוריד מייד לשלוש (לא משנה איך), ומנצח. אם כמות החיבורים זוגית - אני בוכה ומפסיד.. (כי אני חייב ליצור קשת כלשהי - או שתוריד לשלוש ואפסיד - או שתוריד 1 ממספר הקשתות (כלומר מספר אי זוגי) - ואז יריבי יהפוך לשלוש. כלומר - כדי לנצח - אני רוצה להוריד ל4 קטעי קשירות עם מספר זוגי של קשתות.. ואז - 5 אי-זוגי, 6 זוגי, וכו. כלומר - עם n נקודות התחלתיות (n>4) יש (לפי סכום הסדרה החשבונית): n*(1+n)/2 קשתות. בכל מקרה מספר זוגי של קשתות (n זוגי או n+1 זוגי). ואז - אם n אי-זוגי - ניצחתי כי אני מוריד קטע קישור בכל מקרה. אם n זוגי - אני מפסיד.. אמת ?

 

[Javali]

מעניין - אולי. נכון - גם אולי...

> כמות החיבורים החדשה: a+b+m+n-2 ,כלומר צירוף שני תתי קשירות לא משנה את הזוגיות מספר הקשרים.. מעניין. שים לב שזה יהיה נכון רק אם ל-m ול-n אותה זוגיות. אחרת הזוגיות מתחלפת. > יש (לפי סכום הסדרה החשבונית): n*(1+n)/2 קשתות. > בכל מקרה מספר זוגי של קשתות (n זוגי או n+1 זוגי). n*(1+n) באמת זוגי. חצי מזה לא בהכרח > ואז - אם n אי-זוגי - ניצחתי כי אני מוריד קטע קישור בכל מקרה. > אם n זוגי - אני מפסיד.. גם ב-5 וגם ב-6 נקודות השחקן הראשון מפסיד.

 

[guysoffer]

נכון חלקית

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

 

[Javali]

באמת?

n=6 n*(n-1)/2 = 6*5/2=15

 

[guysoffer]

ouch

אני צריך דחוף לחזור לבית הספר.

 

[guysoffer]

אתה צודק לגבי M וN..

וזה משנה את הפתרון. פיספסתי את זה.

 

[Javali]

אז הנה רמז נוסף

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