משפט ארדש-סקרש

במתמטיקה דיסקרטית, משפט ארדש-סקרש הוא משפט הקובע כי בכל סדרה באורך $\ ab + 1$ של מספרים ממשיים שונים יש תת-סדרה עולה באורך $\ a+1$ או תת-סדרה יורדת באורך $\ b+1$. המשפט הוא משפט טיפוסי בתורת רמזי - בתוך כל מבנה גדול דיו יופיעו תבניות מסוימות.

את המשפט הוכיחו פאול ארדש וגאורגה סקרש, במאמר שפרסמו בשנת 1935.

ניסוח פורמלי

תהי $\ x_1,x_2,...,x_{ab+1}$ סדרה של מספרים ממשיים שונים. אזי קיימת תת-סדרה מונטונית עולה ממש באורך $\ a+1$, או שקיימת תת-סדרה מונוטונית יורדת ממש באורך $\ b+1$. המשפט נכון גם אם לא דורשים שהמספרים יהיו שונים, כאשר בניסוחו מחליפים את "יורדת ממש" ב- "יורדת" (כלומר לא עולה), ואת "עולה ממש" ב- "עולה" (כלומר לא יורדת).

נוסף על כך, המשפט הדוק, כלומר הטענה אינה נכונה עבור סדרה כללית באורך $\ ab$.

הוכחת המשפט

הוכחה ראשונה

תהי סדרה $\ x_1,x_2,...,x_{ab+1}$ של מספרים ממשיים שונים. נגדיר לכל $\ i$ את $\ u_i$ להיות אורך תת-הסדרה העולה הארוכה ביותר המתחילה ב$\ x_i$, ובאופן דומה את $\ d_i$ להיות אורך תת-הסדרה היורדת הארוכה ביותר המתחילה ב$\ x_i$.

למה: יהיו $\ i < j$ כך ש $\ u_i = u_j$ אזי $\ x_i > x_j$. באופן דומה יהיו $\ i < j$ כך ש $\ d_i = d_j$ אזי $\ x_i < x_j$.
הוכחה: נניח בשלילה $\ u_i = u_j$ ו$\ x_i < x_j$. אזי לכל תת-סדרה עולה שמתחילה ב$\ x_j$ ניתן לצרף בתחילתה את $\ x_i$ ולקבל תת-סדרה עולה ארוכה יותר. מכאן $\ u_i > u_j$, בסתירה לנתון. באופן דומה ניתן לקבל את הלמה על $d_i$ ו- $\ d_j$.

כעת נעבור להוכחת המשפט עצמו. נניח בשלילה כי אין תת-סדרה עולה ממש של $\ x_n$ באורך $\ a + 1$ ואין תת-סדרה יורדת ממש של $\ x_n$ באורך $\ b + 1$. לכן לכל $\ i$ מתקיים $\ u_i \le a$. כמו כן $\ d_i \le b$, ולכן יש רק $\ ab$ אפשרויות לערכי הזוג הסדור $\ (u_i,d_i)$. לעומת זאת יש $\ ab + 1$ זוגות כנ"ל: $\ (u_1,d_1) , (u_2,d_2) , ... ,(u_{ab+1},d_{ab+1})$.

מעקרון דיריכלה קיימים $\ 1 \le i < j \le ab +1$ כך ש $\ (u_i,d_i) = (u_j,d_j)$. כלומר $\ u_i = u_j$ וגם $\ d_i = d_j$. לכן מהלמה $\ x_i > x_j$ וגם $\ x_i < x_j$. סתירה.

הוכחה שנייה

תהי סדרה $\ x_1,x_2,...,x_{ab+1}$ של מספרים ממשיים שונים.

ניקח את x₁, ואחריו את המספר הקרוב לו ביותר מימינו שגדול ממנו, וכן הלאה, עד שאי אפשר יותר. קיבלנו סדרה עולה. לאחר מכן, ניקח את המספר השמאלי ביותר שעוד לא לקחנו ונבצע עליו את אותה הפעולה. קיבלנו שוב סדרה עולה. נחזור על הפעולה שוב ושוב עד שהסדרה מתרוקנת. אם אחת מהסדרות שקיבלנו באורך ארוך יותר מ-a, מצאנו. אם לא, על פי עקרון דיריכלה יש לפחות b+1 סדרות כאלה. נשים לב שהמספר האחרון (הימני ביותר) בסדרה השנייה בהכרח קטן יותר מהאיבר האחרון בסדרה הראשונה (אחרת הוא בהכרח היה מופיע בסדרה הראשונה). אותו נימוק תקף לכל b+1 הסדרות, לכן אם ניקח את האיברים האחרונים שלהן, נקבל סדרה יורדת כמבוקש.

יתרונה של ההוכחה השנייה היא שהיא קונסרוקטיבית, כלומר מספקת אלגוריתם למציאת הסדרה ולא רק מוכיחה את קיומה.

הוכחה כי המשפט הדוק

נסתכל על הסדרה הבאה:

$b,b-1,\dots,1,2b,2b-1,\dots,b+1,\dots,ab,ab-1,\dots,ab-b+1$.

נשים לב שהסדרה מכילה את כל המספרים מ- 1 ועד $ab$, ולכן יש בה בדיוק $ab$ איברים. כמו כן, נשים לב שאחרי כל איבר יש לכל היותר $b-1$ איברים קטנים ממנו, ובפרט סדרה יורדת מקסימלית היא באורך $b$ לכל היותר. בנוסף, אם נחלק את הסדרה ל- $a$ תתי סדרות באורך $b$ - אז עבור כל איבר, האיבר הבא אחריו שגדול ממנו חייב להימצא בתת-הסדרה הבאה. לכן, תת-סדרה עולה מקסימלית היא באורך $a$. לכן, אין לסדרה זו תת-סדרה יורדת באורך $b+1$, וכן אין לה תת-סדרה עולה באורך $a+1$. לפיכך, אין משפט ארדש-סקרש מתקיים עבור סדרות באורך $ab$.

ראו גם

• תורת רמזי

קישורים חיצוניים

• Erdős, Paul; Szekeres, George (1935). "A combinatorial problem in geometry", Compositio Mathematica 2: 463–470.