שלום קוראים,
אני אמשיך את הקו הקומבינטורי-אלגברי של הפוסט הקודם, אבל עם משהו אלמנטרי יותר.
הפעם נעסוק בבעיית ספירה עם ניחוח של תורת המספרים. בחלק זה מתוך סדרה של 2 פוסטים נפתור את בעית הספירה ב-3 דרכים, נכליל אותה ונפתור שוב, ואז נפרוש איש איש לענייניו.
בפוסט הבא נעסוק במשפט קשור (קונגרואנציה יפה שמוסברת באמת רק מתוך אנליזה -אדית), ועל הכללה מסוימת שלו שהוכחתי לבקשת זוכה מדליית פילדס. בחיי שאני לא משקר. חכו לפוסט הבא…
0. הבעיה
הבעיה שאעסוק בה היא הבעיה השישית והאחרונה (כלומר, הקשה ביותר) בתחרות המתמטיקה הבינלאומית (International Mathematical Olympiad, או בקיצור: IMO) ה-36. היא התקיימה בטורונטו, קנדה ב-1996. מתוך 412 משתתפים, 34 פתרו את הבעיה (לשם השוואה, הבעיה השנייה ברמת הקושי שלה, שהייתה באותה שנה הבעיה השנייה מבחינה כרונולוגית, נפתרה ע"י 90 מתמודדים).
למי שלא מכיר, ה-IMO היא תחרות יוקרתית במתמטיקה המיועדת לנוער (יש הגבלת גיל) ומתקיימת מדי שנה. כל מדינה רשאית לשלוח עד 6 נציגים, שמתחרים במשך יומיים באופן אישי בפיתרון 6 שאלות: 3 שאלות ביום הראשון, ו-3 שאלות ביום השני, כאשר הזמן המוקצב בכל יום הוא 4.5 שעות. השאלות בכל יום מסודרות בסדר קושי עולה (או כך לפחות אמור להיות; בפועל לא תמיד קורה). כל משתתף מקבל ציון על פתרונותיו, כאשר הציון המקסימלי האפשרי הוא 42: כל שאלה שווה עד 7 נקודות. על אף הקושי הרב של הבעיות, הן הניסוח והן הפיתרון משתמשים בידע תיכוני בלבד – למרות שידע על-תיכוני לא יכול להזיק, בלשון המעטה.
(למקרה שאתם תוהים, אני כמובן לא השתתפתי באותו IMO; הייתי בן 4.5. מבינים? הייתי כ"כ צעיר שעוד ספרתי את הגיל שלי בחצאים.)
ניגש לבעיה:
יהי ראשוני אי-זוגי. כמה תתי-קבוצות של יש, כך שמספר האיברים בקבוצה הוא וסכום האיברים בקבוצה מתחלק ב-?
בעית ספירה, מאוד קונקרטית, מאוד אלגנטית. אילולא הנתון על הראשוניות של , לא היה ברור שיש בכלל קשר חזק לתורת המספרים – אבל יש. אפריורי גם לא ברור למה רלוונטי הנתון? מה קורה אם מנסים לפתור את השאלה הכללית? ובכן, "אספיילר" ואגיד שהחשיבות היחידה של הנתון היא פישוט השאלה. ללא נתון זה, השאלה קשה יותר. כאשר נפתור את המקרה הכללי נראה מדוע המקרה של ראשוני הוא הפשוט ביותר.
להמשיך לקרוא