רמי מציע לדינה את האתגר הבא:
דינה תבחר 8 מספרים טבעיים שונים כלשהם בתחום [10,36] .
רמי ינסה ליצור, תוך שימוש רק במספרים שדינה בחרה או בחלק מהם, שני סכומים שווים.
למשל, במידה ודינה בחרה את המספרים 10,11,12,15,18,25,32,36, אז רמי יכול לרשום את השוויון 11 +25 = 36. לחלופין, הוא יכול לרשום 10+12+15 = 15+25.
כל המספרים צריכים להילקח מהרשימה של דינה, ואין חזרות על אותו מספר.
אם רמי מצליח לרשום שוויון כזה - הוא מנצח. אם הוא לא מצליח - דינה מנצחת.
בהנחה שאחרי שדינה בוחרות יש לרמי די זמן - או מחשב - לבדוק את כל האפשרויות,
הוכיחו כי רמי תמיד ינצח!
אז כרגע הגעתי לכך שיש 255 תתי קבוצות מקבוצת המספרים שדינה בחרה - 2^8, שזה כביכול השובכים? ואז צריך למצוא את מספר הסכומים האפשריים שהם יהיו היונים? אבל כיצד עלי למצוא אותם?
אשמח לעזרה, תודה רבה!
דינה בחרה שמונה מספרים טבעיים שונים בתחום 10\leq n\leq 16. מכאן שמספר תת-הקבוצות של קבוצת המספרים שדינה בחרה, ללא הקבוצה הריקה, הוא 2^8-1=255. הסכום הקטן ביותר שיכול להתקבל הוא 10 שכן זהו האיבר הקטן ביותר שניתן לבחור. הסכום הגדול ביותר שיכול להתקבל הוא סכום שמונת המספרים הגדולים ביותר שניתן לבחור:
\sum_{i=0}^8(29+i)=29+30+31+\ldots+36=260
לכן, מספר הסכומים האפשריים הוא 260-10+1=251.
נשים לב שישנם 251 סכומים אפשריים, אבל 255 תת-קבוצות (דרכים שונות לסכום מספרים). ע"פ עקרון שובך היונים, מכיוון שישנן יותר תת-קבוצות (יונים) מאשר סכומים (שובכים), בהכרח קיימות שתי תת-קבוצות לפחות בעלת אותו סכום איברים.
אם ניקח שתי קבוצות כאלה ונסיר את האיברים המשותפים לשתיהן (במידה ויש כאלה) אז נקבל שתי קבוצות זרות בעלות אותו סכום. זאת הסיבה שרמי תמיד ינצח במשחק.
בהצלחה
