מי יגיד 100?

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

מי יגיד 100?

מי מכיר את משחק הילדים "מי יגיד 100"? משחקים שניים. הראשון אומר מספר טבעי כל שהוא לא גדול מ-10. למשל 8. השני מוסיף מספר טבעי כל שהוא לא גדול מ-10 ואומר את התוצאה, למשל הוא הוסיף 5, אז הוא ישר אומר 13. מנצח זה שאומר 100.

 

[Shiberia]

די פשוט לא ?

מי שמתחיל מנצח השלם תמיד ל 12 23 34 וכן הלאה עד ל 100

 

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

יפה! מי אמר שתמיד חייב להיות מסובך?

באמת הראשון אומר 1, ואח"כ מוסיף 11 לְמה שהוא עצמו אמר בפעם הקודמת, ואין אפשרות להפריע לו. ברור גם המקרה הכללי: מקסימום מותר להוסיף K, מנצח מי שאומר N. מחלקים N ל-(K+1) ואם יש שארית, אז הראשון אומר בהתחלה את השארית, ואח"כ מוסיף כל פעם לעצמו (K+1) בלי שהשני יוכל להפריע לו. ואם השארית היתה 0, הראשון מפסיד. אבל יש המשך! נחזור למשחק נים. הפעם נאמר, שלכל אחת מהערימות קיים מספר גפרורים מקסימלי שאפשר להוציא ממנה במהלך אחד (המספר הזה אינו משתנה במהלך המשחק עבור כל ערימה). איך זה משפיע על אלגוריתם נים?

 

[Shiberia]

מה זה משחק נים?

 

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

נכון לרגע זה, בסוף דף 7, בסוף

השרשור "ממשיך להפציץ אולימפיאדה", כתבתי 3 הודעות: 1. המשחק נים. 2. האלגוריתם (כלומר פתרון החידה). 3. הוכחת הפתרון.