תורת המספרים הקומבינטורית (או: תורת רמזי)

תיאור הקורס (פרומו)

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

1. שאלה ראשונה לתיזה/אתגר
2. שאלה שניה לתיזה/אתגר
3. נמכר!!! שאלה שלישית לתיזה/אתגר : גירסה קודמת נפתרה על ידי מני, שגילה פתרון מאד קל. הגירסה הנוכחית מתבררת כלא טריויאלית בכלל, והיא נפתרה על ידי גילי (התשובה לשאלה היא חיובית).
4. שאלה רביעית לתיזה/אתגר. (תודה לאיתי על איתור מהיר של טעות בגירסה הקודמת של השאלה הראשונה. הטעות תוקנה.) איתי גם פתר את השאלה השניה מבין השתיים שם, הנה פישוט קל של פתרונו: נצבע את האיזוגיים באדום ואת הזוגיים בירוק. לכל תת-סידרה של האיזוגיים, יהיה מספר זוגי שהוא סכום של שניים מהם, ולכן בצבע אחר. איזה יופי. הראשונה עדיין פתוחה.
5. שאלה חמישית לתיזה/אתגר. (הקובץ עודכן עם כמה הערות).
6. שאלה שישית לתיזה/אתגר. שיא ראשון: ניר הס מצא את הצביעה הבאה, בלי שלשת שור מונוכרומטית, למספרים 1 עד 47. זה מוכיח שמספר שור של 5 הוא לפחות 48:

   121312141213125532235224423153215121415141213123

   שיא חדש: אסף רוזין מצא דרך קונסטרוקטיבית למצוא, לכל טבעי n צביעה של 3 בחזקת n פחות 1 חלקי שתיים, בלי שלשת שור. למקרה n=5 זה יוצא 121, שיפור משמעותי! הוא גילה ששור עצמו מצא חסם זה.

   שוברי שיא זה מתבקשים להודיעני.

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

תודה מיוחדת: למיכאל מכורה, שעבר על הספר תוך כדי לימוד עברית (!) והציע תיקונים רבים ומועילים.

תרגילים

כל תרגיל ייבדק בצורה הבאה:

1. שניים מתלמידי הקורס, על פי סבב, יבדקו את התרגיל, יכתבו הערות בדיקה ויתנו ציון:
   1. הציון אינו מתוך 100, אלא מתוך מספר התרגילים שניתנו. (למשל, אם היו שש שאלות, ציון טיפוסי יהיה 4.5/6)
   2. תלמידים שפתרו גם תרגילים שלא נתבקשו, יקבלו סימן "+" ליד ציון התרגיל, לאינדיקציה שאוכל אולי להתחשב בה אם יהיה צורך.
2. כל אחד מהבודקים יבדוק חצי מהשאלות, בצורה רוחבית.
3. לאחר מכן, התלמידים יעבירו את התרגילים לתומר יניב, שיבדוק את בדיקתם בצורה מדגמית, וכן את תרגיליהם שלהם, וייתן להם ציון על תרגיליהם (לפי הכללים לעיל) ועל איכות בדיקתם (ציון נפרד, באחוזים מתוך 100).

בודקי המטלות: גילי גולן ורן כהן (מטלה 1), סרגיי מלב ומוטקה פורת (מטלה 2), ניר הס ונתנאל שטיין (מטלה 3), מני שלוסברג ומשה ליבוביץ' (מטלה 4), גל וישנה ורות מלכא (מטלה 5), אירינה ראיצ'יק ואיתי רביה (מטלה 6), תומר מנקט ואייל קפלן (מטלה 7), נמרוד שנקר וערן ברנשטיין (מטלה 8), ערן אלוף ועוד מישהו (מטלה 9), בועז (מטלה 10).

ספרות מומלצת

1. I .Protasov: Combinatorics of Numbers.
   מכיל את המשפטים המרכזיים שיוכחו בקורס. למעשה, הקורס חופף ברובו לספר זה. אוכל לשלוח קטעים ממנו לתלמידים שברשימת התפוצה של הקורס.
2. R.L. Graham, B.L. Rothschild, J.H. Spencer: Ramsey Theory.
   הספר הקלאסי של התחום.
3. Karen R. Johannson: Variations on a theorem by van der Waerden
   עבודת תיזה למאסטר. הצגה ברורה של המשפטים המרכזיים, ושל נקודת המבט של עלמסננים.
4. K.P. Hart: The Cech-Stone compactification.
   חלק מרשימות של קורס בטופולוגיה, עם יישומים לקומבינטוריקה. דומה למה שנעשה בקורס.
5. אי כריעות של משפטי צביעה מצגת על תוצאה מדהימה. (תודה לערן אלוף.)

(c) כל הזכויות שמורות לבועז צבאן.