שלום לכם,

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

אלו הוראות המשחק:

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

סיום המשחק: כשכל המטבעות מונחים על השולחן.

המנצח: השחקן שעשה את הצעד האחרון.

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

אילוסטרציה: Shutterstock

סקובידו


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

18 תגובות

  • אנונימי

    אני רוצה לתקן אתכם שוב; כתבתם

    אני רוצה לתקן אתכם שוב; כתבתם למעלה גם "מונחות" על "מטבע" וגם "אחד" על "מטבע". תחליטו כבר!

  • יעל בן משה

    מה האסטרטגיה לנצח?

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

  • אלעד

    תשובה (שונה)

    להיות הראשון.
    מסכים עם האסטרגיה להשלים ל-10 אבל היתרון של הראשון הוא בסעיף הזה "ולא יותר ממספר המטבעות שכבר נמצאים על השולחן באותו שלב".
    נשים 4 מטבעות ואז אחרי מה שהיריב יעשה (1-4 כלומר 5-8 מטבעות) נשלים ל-10 וכך בכל צעד עד שנסיים 100.

    הפיתרון השני הוא לשים 1 ואז הוא צריך 1 ואז אנחנו 2 והגענו לאותו פיתרון בדרך אחרת.

    לדעתי אין פתרונות אחרים כיוון ש:
    1) אם נשים 5 ומעלה - אז השני ישלים ל-10 וינצח.
    2) אם נשים 2-3 הוא ישלים ל-4 ואז ישלים ל-10 וינצח.

  • יעל

    מאיפה

    מאיפה עליי להביא מאה מטבעות ומי בידיוק ישחק איתי את זה זה לא ממש מישחק משחקים פו על כסף אמיתי

  • אחיה

    תשובה

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

  • עטרה

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

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

    נסמן:
    K = מספר המטבעות.
    i = אינדקס המהלך של שחקן א.
    f(K,i) = 2^i-1
    ((g(K,i) = floor((K+1-2^floor(log2(K+1)))/2^(floor(log2(K+1))-i
    (h(K,i) = f(K,i)+g(K,i

    האסטרטגיה:
    בסיום מהלך i של שחקן א, מספר המטבעות על השולחן הוא (h(K,i.

    דוגמאות:
    K=7: 0+0, 1+0, 3+0, 7+0
    K=8: 0+0, 1+0, 3+0, 7+1
    K=9: 0+0, 1+0, 3+1, 7+2
    K=10: 0+0, 1+0, 3+1, 7+3
    K=11: 0+0, 1+1, 3+2, 7+4
    K=12: 0+0, 1+1, 3+2, 7+5
    K=13: 0+0, 1+1, 3+3, 7+6
    K=14: 0+0, 1+1, 3+3, 7+7

  • עטרה

    ניסוח יותר קצר

    נסמן:
    K = מספר המטבעות.
    i = אינדקס המהלך של שחקן א.
    h(K,i) = floor((K+1)/2^(floor(log2(K+1))-i))-1

    האסטרטגיה:
    בסיום מהלך i של שחקן א, מספר המטבעות על השולחן הוא (h(K,i.

  • עטרה

    ייצוג "בינארי מוכלל"

    נגדיר ייצוג "בינארי מוכלל" באופן הבא: בייצוג הבינארי המוכלל, כל ספרה מייצגת את כפולה של חזקה מתאימה של 2, כמו בייצוג הבינארי הרגיל, אבל, שלא כמו בייצוג הבינארי הרגיל, מותר להשתמש בספרות נוספות, מלבד 0 ו-1. למשל: המחרוזת 1201 מייצגת את המספר n=8*1+4*2+2*0+1*1=17.

    מספר המטבעות על השולחן לאחר ביצוע מהלכים על ידי שחקן א:
    K=7 : 000, 001, 011, 111=7
    K=8 : 000, 001, 011, 112=8
    K=9 : 000, 001, 012, 121=9
    K=10: 000, 001, 012, 122=10
    K=11: 000, 002, 021, 211=11
    K=12: 000, 002, 021, 212=12
    K=13: 000, 002, 022, 221=13
    K=14: 000, 002, 022, 222=14

  • רמי

    הכללת המשחק

    הוראות המשחק המוכלל:

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

    האם יש תהליך לניצחון?
    אם יש, מהו התהליך?

  • עטרה

    אסטרטגיה מנצחת עבור המקרה הכללי (M>=3)

    מספר המהלכים שהשחקן הראשון מבצע הוא
    floor(log2((K+2)/3))+1
    לכל i, בסיום המהלך i, מספר המטבעות שמונחים על השולחן הוא
    (((min(K,ceiling(((3+K)/(2^(floor(log2((2+K)/3))+1-i))-3.

  • עטרה

    פונקציה רקורסיבית פשוטה שמתאימה לנוסחא שלעיל

    K(1) = K

    for i = 2 to floor(log2((K+2)/3))+1

    K(i) = floor(K(i-1)/2)-1

  • רמי

    הערה לתשובה

    חישוב מספר המהלכים שלי ומספר המטבעות לכל i, שונה משלך.
    האסטרטגיה כאן טובה לדעתי עבור M>=2 .

    להלן תשובתי בהקשר לתשובתך:

    מספר המהלכים שהשחקן הראשון מבצע הוא : ((FLOOR(LOG2(K+1

    פונקציה רקורסיבית לחישוב מספר המטבעות שצריך הראשון להשאיר על השולחן בתורו:
    נסמן, (למען הנוחות באתר זה), i-1=j
    K0=K (*)
    4/(Ki=(Kj-3-(-1)^Kj

    (*) הראשון כאן הוא למעשה האחרון במשחק.
    (**)יש לחשב מהראשון ועד האחרון שאינו 0

    למשל אם יש 210 מטבעות, נקבל את הסדרה :
    210 104 51 25 12 5 2
    וניתן לאמת שמספר המהלכים הוא 7

  • עטרה

    קיבלתי רק חלק מהסדרה

    FLOOR(210-3-(-1)^210)/4 = 51
    FLOOR(51-3-(-1)^51)/4 = 12
    FLOOR(12-3-(-1)^12)/4 = 2

  • רמי

    טעות קולמוס

    במקום : 4/(Ki=(Kj-3-(-1)^Kj
    צ"ל :
    4/(Ki=(2*Kj-3-(-1)^Kj

  • עטרה

    אולי הפונקציה הרקורסיבית היא כך

    oddK(1) = K

    evenK(2) = floor(K/2)-1

    (oddK(i) = floor((oddK(i-2)-3-(-1)^oddK(i-2))/4

    (evenK(i) = floor((evenK(i-2)-3-(-1)^evenK(i-2))/4

  • עטרה

    M<=2

    עבור M=1, אם ((Floor(2*Log2(K+1 זוגי, אז לשחקן הראשון יש אסטרטגיה מנצחת. אחרת, לשני יש אסטרטגיה מנצחת.
    עבור M=2, לכל K, לשחקן הראשון יש אסטרטגיה מנצחת.

  • רמי

    M=1

    עבור M=1 :
    - לשחקן הראשון אסטרטגיה מנצחת בתחומים הבאים בלבד :
    בין וכולל 1- ( K=power(2,i לבין וכולל 2- ( K=3*power(2,i-1 לכל שלם i >= 0
    - לשחקן השני אסטרטגיה מנצחת בשאר המקרים.
    - חלוקת ה K ים לאסטרטגיה מנצחת היא 50% לכל שחקן.

  • רמי

    פתרון

    כדי לנצח יש להיות השחקן הראשון.
    מספר המטבעות שעל השולחן שיגרמו להפסד לשחקן שתורו לשחק הן : 2,5,11,24,49
    השחקן הראשון יוציא 2 או 5 מטבעות בשלב הראשון של המשחק.
    בכל שלב יש לגרום שלשחקן השני יהיו מספר מטבעות כנ"ל.
    אם למשל תורנו ויש 20 מטבעות על השולחן, יש להוציא 4 מטבעות מהתיבה , כך שלשחקן השני יהיו 24 מטבעות בתורו.