שירשור החידות הגדול

osherov · שליחה #3341 20/03/2008 14:06

חשבתי על זה לא מעט ולא מצאתי פתרון

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

moco · שליחה #3342 20/03/2008 14:48

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

amirbd · שליחה #3343 20/03/2008 14:55

אריה - הנה רמז שעדיין לא רוצח את החידה לדעתי.

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

מטרת החידה היא להראות שקיימת לאריה אסטרטגיה מנצחת (אך כאמור אין צורך לתאר את האסטרטגיה הזאת, רק להוכיח את קיומה.).

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

לכן, כדי להוכיח שלאריה יש אסטרטגיה מנצחת, די להראות שלא יתכן שיש לעומר אסטרטגיה מנצחת. עכשיו בוא תניח (בשלילה) שיש לעומר אסטרטגיה מנצחת (תסתכל שוב במה שהדגשתי למעלה), תגיע לסתירה, וכך תוכיח את הנדרש.

אריה, זה לא רמז גדול, אבל הרמז הבא כבר די קרוב לפתרון המלא.

osherov · שליחה #3344 20/03/2008 15:01

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

טוב בגלל שאני היחיד שמנסה לפתור את זה אני יעלה את מחשבותיי לשרשור

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

moco · שליחה #3345 20/03/2008 15:12

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

תתרכז במה שאתה יכול לעשות מול היריב, לא מה הוא יכול לעשות.

osherov · שליחה #3346 20/03/2008 15:20

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

moco · שליחה #3347 20/03/2008 16:02

יש לך טעות טכנית.
לא בהכרח תוכל להגיע שוב למלבן. ייתכן ואני אחליט להשאיר מלבן ואז אתה כבר לא תוכל להשאיר מלבן.

בגדול, צורת המחשבה שלך היא בכיוון הנכון.

moco · שליחה #3348 20/03/2008 16:03

אני מוכן כבר לקבל רמזים בעיניין המספרים 1 עד 100.
ניסיתי לעבוד עם שיקולי ספירה (כמה אפשרויות יש מול הסכומים האפשריים) אך לא צלח לי.

osherov · שליחה #3349 20/03/2008 16:06

moco כתב:יש לך טעות טכנית.
לא בהכרח תוכל להגיע שוב למלבן. ייתכן ואני אחליט להשאיר מלבן ואז אתה כבר לא תוכל להשאיר מלבן.
...

הרי גם אם תשאיר מלבן אני עדיין יכול שוב ליצור מלבן מחדש
לא נכון ?!

moco · שליחה #3350 20/03/2008 16:20

אופס, אתה צודק בעצם.
אולי בעצם פתרת את זה?

בוא נחכה לאמיר שיחווה דיעה.

osherov · שליחה #3351 20/03/2008 16:23

moco כתב:אופס, אתה צודק בעצם.
אולי בעצם פתרת את זה?

בוא נחכה לאמיר שיחווה דיעה.
...

ניתן לאמיר לומר את דברו
אבל במידה וזה הפתרון הנכון
עדיין משהו לא מתיישב לי בסדר עם הפתרון הזה

moco · שליחה #3352 20/03/2008 16:25

הוא קצת מבלבל (בהנחה שהוא נכון).
הפתרון שלי יותר ישיר ופחות מבלבל.

moco · שליחה #3353 20/03/2008 16:32

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

osherov · שליחה #3354 20/03/2008 16:52

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

הבעייה שלי עם הפתרון הזה שנראה לי שהוא לא סוגר את כל המצבים לדוגמה:
סתאם נניח שיש אלגוריתם לניצחון במצב שהלוח הוא 5X5 לזה שעושה את המהלך הבא !!
במקרה כזה יכול להיווצר מצב שאני כאילו הופך את האסטרטגיה שלך אבל אתה תצליח להכריח אותי להגיע למצב שהלוח הוא 5x5 והתור הוא שלך ואז אתה בטוח מנצח את המשחק ?!

moco · שליחה #3355 20/03/2008 17:09

איך אני אצליח להגיע ל5X5 והתור שלי? אתה תוכל למנוע זאת ממני.

שים לב להקבלה המוזרה בין הדיון פה בינינו והחידה

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

amirbd · שליחה #3356 20/03/2008 17:09

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

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

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

amirbd · שליחה #3357 20/03/2008 17:13

moco כתב:אני מוכן כבר לקבל רמזים בעיניין המספרים 1 עד 100.
ניסיתי לעבוד עם שיקולי ספירה (כמה אפשרויות יש מול הסכומים האפשריים) אך לא צלח לי.
...

יש מישהו שמתנגד לרמז לחידה המספרים ?

osherov · שליחה #3358 20/03/2008 17:14

רק משה מתנגד לרמזים

osherov · שליחה #3359 20/03/2008 17:16

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

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

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

נשברתי,
פרסם את הוכחת בית הספר

moco · שליחה #3360 20/03/2008 17:39

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

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