2 חידות

[e p s i l o n]

2 חידות ../images/Emo124.gif

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

 

[טלמון סילבר]

הערה לא מחייבת לחידה מספר 1.

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

 

[e p s i l o n]

הערה נכונה ../images/Emo127.gif

זה למעשה גם רמז לפתרון..

 

[טלמון סילבר]

נכון, זה ../images/Emo101.gif למי שלא מכיר.

 

[שץ מקשת]

../images/Emo62.gif

כדאי לשים מטבע מסוים בנקודה המרכזית ומאז והלאה לשים כל פעם מטבע בצד השני של ציר סמטריה שעובר דרך נקודת המרכז

 

[שץ מקשת]

הוספה

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

 

[טלמון סילבר]

../images/Emo127.gif נכון ../images/Emo45.gif

 

[טלמון סילבר]

אם הבנתי נכון את 2, אז לא

תמיד הראשון מנצח. למשל: 1 9 1 והראשון מפסיד. או: 3 3 3 3 ותיקו בטוח. אולי השאלה היא איך לקחת מקסימום?

 

[e p s i l o n]

../images/Emo45.gif תיקון קל..

אני חושב שבתור הראשון אתה בוחר האם להתחיל או לתת לשני להתחיל.

 

[haunter]

ואם

ואם השני מתחיל ברשימה עם ה 3 3 3 3 ?

 

[Berbale]

טוב ..

אז על תפסיד!

 

[טלמון סילבר]

../images/Emo62.gif פתרון חלקי בלבד ל-2, למקרה

שכמות המספרים זוגית:

n(1) n(2) . . . n(2k)​

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

 

[שץ מקשת]

נראה לי שזה הפתרון

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

 

[טלמון סילבר]

החלק האחרון לא עובר.

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

 

[שץ מקשת]

נכון, טעות שלי

 

[טלמון סילבר]

הערה למקרה של כמות זוגית.

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

 

[avivRT]

בעיקרון

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