בפורום זה תוצג בתחילת כל שבוע חידה מתמטית חדשה.
הציעו חידות
שלום לכם,
מקווה שהחג עבר עליכם בנעימים. אני רוצה הפעם לבקש שתעזרו לי למצוא טקטיקה שבעזרתה אוכל לנצח במשחק הבא שלימד אותי חברי הטוב רועיקי.
אלו הוראות המשחק:
המשחק מיועד לשני שחקנים. בתחילת המשחק מונחות בתיבה מאה מטבעות. השחקן הראשון מוציא מהשקית בין מטבע אחד לתשעה ומניח אותם על השולחן.
מכאן ואילך כל שחקן בתורו מוציא מהשקית לפחות מטבע אחד, ולא יותר ממספר המטבעות שכבר נמצאים על השולחן באותו שלב, ומניח גם אותם על השולחן.
סיום המשחק: כשכל המטבעות מונחים על השולחן.
המנצח: השחקן שעשה את הצעד האחרון.
האם תוכלו למצוא דרך שתבטיח את ניצחוני? האם לשם כך עלי להיות השחקן הפותח או השחקן השני? איך עלי לתכנן את מהלכיי?
אילוסטרציה: Shutterstock
סקובידו
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום ואנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
להיות הראשון.
מסכים עם האסטרגיה להשלים ל-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 ומניח אותם על השולחן.
מכאן ואילך כל שחקן בתורו מוציא מהשקית לפחות מטבע אחד, ולא יותר ממספר המטבעות שכבר נמצאים על השולחן באותו שלב, ומניח גם אותם על השולחן.
סיום המשחק: כשכל המטבעות מונחים על השולחן.
המנצח: השחקן שעשה את הצעד האחרון.
האם יש תהליך לניצחון?
אם יש, מהו התהליך?
מספר המהלכים שהשחקן הראשון מבצע הוא
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=1, אם ((Floor(2*Log2(K+1 זוגי, אז לשחקן הראשון יש אסטרטגיה מנצחת. אחרת, לשני יש אסטרטגיה מנצחת.
עבור M=2, לכל K, לשחקן הראשון יש אסטרטגיה מנצחת.
כדי לנצח יש להיות השחקן הראשון.
מספר המטבעות שעל השולחן שיגרמו להפסד לשחקן שתורו לשחק הן : 2,5,11,24,49
השחקן הראשון יוציא 2 או 5 מטבעות בשלב הראשון של המשחק.
בכל שלב יש לגרום שלשחקן השני יהיו מספר מטבעות כנ"ל.
אם למשל תורנו ויש 20 מטבעות על השולחן, יש להוציא 4 מטבעות מהתיבה , כך שלשחקן השני יהיו 24 מטבעות בתורו.
תגובות