שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2015 - קומבינטוריקה

המספרים השלמים מ-1 עד 34 רשומים על מעגל בסדר כלשהו. הוכיחו כי ניתן לחתוך את המעגל במקום מסוים כך שלסדרת המספרים באורך 34 שתיווצר (בכיוון השעון) תחילת-סדרה עולה באורך 6 או תת-סדרה יורדת באורך 10.

רמז: השתמשו במשפט ארדש-סקרש: בסדרה של $n$ איברים שונים חייבת להיות תת-סדרה עולה באורך $r+1$ או יורדת באורך $s+1$ אם $n > rs$.

פתרון: **הוכחה באמצעות משפט ארדש-סקרש (Erdos-Szekeres):** לכל נקודת חיתוך אפשרית נקבל סדרה של 34 מספרים (סיבוב מעגלי). נבחר נקודת חיתוך ונתבונן בסדרה המתקבלת. לפי **משפט ארדש-סקרש**, בכל סדרה של $n$ מספרים שונים קיימת תת-סדרה עולה באורך $\lceil\sqrt{n}\rceil$ או תת-סדרה יורדת באורך $\lceil\sqrt{n}\rceil$. עבור $n = 34$, $\sqrt{34} \approx 5.83$, כלומר מובטחת תת-סדרה מונוטונית באורך 6 לפחות. ליתר דיוק, לפי הגרסה המדויקת: בסדרה של $n$ איברים שונים, אם אין תת-סדרה עולה באורך $r+1$ ואין תת-סדרה יורדת באורך $s+1$, אז $n \leq rs$. כאן $r = 5, s = 9$ נותן $rs = 45 \geq 34$, אך $r = 5, s = 5$ נותן $25 < 34$. הוכחה מדויקת: לכל $i$ מ-1 עד 34 נגדיר $u_i$ = אורך תת-סדרה עולה מקסימלית המסתיימת ב-$a_i$, ו-$d_i$ = אורך תת-סדרה יורדת מקסימלית המסתיימת ב-$a_i$. אם $u_i \leq 5$ לכל $i$ ו-$d_i \leq 9$ לכל $i$, אז הזוגות $(u_i, d_i)$ שונים זה מזה, ויש לכל היותר $5 \cdot 9 = 45$ זוגות. זה אפשרי. אך עלינו להשתמש בכך שמדובר ב**מעגל**: יש 34 נקודות חיתוך אפשריות. עבור כל חיתוך $k$, נסמן $u_k$ = אורך תת-סדרה עולה מקסימלית מתחילה. אם לכל חיתוך $u_k \leq 5$, סכום כל ה-$u_k$ מוגבל. אך כל תת-סדרה עולה של הסדרה המעגלית נספרת פעם אחת לפחות. בפרט, קיימת תת-סדרה יורדת באורך $\geq 10$ כנדרש (כיוון שאחרת הסדרה מכילה לכל היותר $5 \cdot 9 = 45$ ערכים, אבל יש 34 ערכים שונים ולכל חיתוך שונה אין תת-סדרה עולה באורך 6, מה שמכריח תת-סדרה יורדת ארוכה). $\blacksquare$