אי-שוויון התמורות

אי-שוויון התמורות הוא אי-שוויון שימושי המאפשר למצוא תמורות שנותנות ערך מקסימלי.

אם נתונות שתי N-יות סדורות $a, b$ בעלות $n$ איברים, כך שאיברי $a$ מסודרים מהקטן לגדול (נסמן אותם $a_{1}, a_{2}, \dots, a_{n}$ ) ו- $b$ בסדר מסוים (נסמן אותם $b_{1}, b_{2}, \dots, b_{n}$ ), אז הביטוי $a_{1} b_{1} + a_{2} b_{2} + \dots + a_{n} b_{n}$ מקבל ערך מקסימלי כאשר גם איברי $b$ מסודרים מהקטן לגדול. ערך מינימלי מתקבל כאשר הם מסודרים מהגדול לקטן.

הוכחה

טענת עזר: אם $a_{1} < a_{2}, b_{1} < b_{2}$ , אז $a_{1} b_{2} + a_{2} b_{1} < a_{1} b_{1} + a_{2} b_{2}$ .
הוכחה: ביטוי שקול הוא $a_{1} b_{1} + a_{2} b_{2} - a_{1} b_{2} - a_{2} b_{1} > 0$ או $(a_{1} - a_{2}) (b_{1} - b_{2}) > 0$ . כיוון שהביטויים בסוגריים הם שליליים, המכפלה שלהם חיובית.

הוכחת האי-שוויון: ניקח תמורה כלשהי על $b$ ונחשב את הביטוי. נשים לב שאם קיימים שני מספרים $i > j$ עבורם $b_{i} < b_{j}$ , אז נוכל להחליף ביניהם ולהגדיל את ערך הביטוי (על פי טענת העזר). נמשיך בתהליך עד שנגיע למצב שאיברי $b$ מסודרים לפי הסדר. כיוון שבכל שלב הגדלנו את ערך הביטוי, הרי שבסיכומו של דבר הגדלנו אותו ולכן בתמורה שבה איברי $b$ מסודרים לפי הסדר הערך גדול יותר מאשר זאת שבחרנו. כיוון שהסבר זה לא תלוי מאיזה תמורה התחלנו, הוא נכון לכל תמורה, ולכן התמורה בה איברי $b$ מסודרים לפי הסדר היא זאת שנותנת את הערך המקסימלי.

ההוכחה שכאשר איברי $b$ מסודרים מהגדול לקטן מתקבל ערך מינימלי אנלוגית לחלוטין.

אי-שוויון התמורות

הוכחה

תפריט ניווט

חיפוש