מחבואים

[yoramgat]

מחבואים

ראובן ושמעון משחקים במחבואים בצורה הבאה: ישנם n מקומות מחבוא מסודרים בשורה. ראובן מתחבא באחד מהם. שמעון יכול לבדוק לכל היותר k מקומות מחבוא והמקומות הנבדקים חייבים להיות *סמוכים* זה לזה. שמעון זוכה אם ראובן נמצא באחד מהמקומות הנבדקים, אחרת ראובן זוכה. החידה: מהן האיסטרטגיות האופטימליות עבור ראובן ושמעון? מקור החידה: "Mathematical magic show" by Martin Gardner

 

[יוּני כמו החודש]

../images/Emo62.gif

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

 

[whatmeworry]

בוא נראה...

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

 

[gloom]

../images/Emo66.gif

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

 

[yoramgat]

הבהרה ורמז דק

הבהרה: אופטימליות של אסטרטגיה מוגדרת במובן maximin: לכל אסטרטגיה של ראובן - נכנה אותה A - ישנה אסטרטגית תגובה אופטימלית מצידו של שמעון - ( B(A. האסטרטגיה האופטימלית של ראובן - * A - היא זו שמבטיחה לו את סיכוי הנצחון המקסימלי גם אם שמעון ישחק מולה את התגובה האופטימלית שלו - ( *B(A. ישנו משפט מתורת המשחקים המוכיח כי במשחק סכום אפס (כמו זה שבו עסקינן) האסטרטגיה האופטימלית של ראובן היא גם אופטימלית מול האסטרטגיה האופטימלית של שמעון, כלומר: ( *B* = B(A ו- ( *A* = A(B. רמז דק: האסטרטגיות האופטימליות מכילות רכיב אקראי.

 

[yoramgat]

פתרון:

אסטרגיה אופטימלית עבור ראובן (המתחבא): חלק את n מקומות המחבוא ל-r קבוצות זרות: S1 = 1, ..., k S2 = k + 1, ..., 2k, ... Sr = (r - 1)k + 1, ..., n. מספר הקבוצות r הוא המספר השלם הקטן ביותר שאינו קטן מ- n / k. ראובן בוחר קבוצה אקראית מתוך הקבוצות הללו (עם הסתברות שווה לכל קבוצה) ומתחבא במקום המחבוא הנמוך ביותר בקבוצה. טענה: לכל אסטרטגית חיפוש, ההסתברות למציאתו של ראובן אינה עולה על r^-1. הוכחה: שמעון אינו יכול לחפש ביותר מאשר מקום מחבוא אחד שהוא המקום הנמוך ביותר באחת מהקבוצות Si. לכן, שמעון נאלץ לבחור את אחד מ- r המקומות הללו ולחפש שם. הסיכוי שראובן שם הוא r^-1. אסטרטגיה אופטימלית עבור שמעון (המחפש): בחר את אחת מהקבוצות Si וחפש בכל איבריה. טענה: לכל אסטרטגית מחבוא של ראובן, הסיכוי שלו להימצא הוא בדיוק r^-1. הוכחה: ראובן חייב להמצא באחד ממקומות המחבוא. הסיכוי של כל אחד מהמקומות להיבדק הוא בדיוק r^-1.