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

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

האי-שוויון קובע כי: אם נתונות שתי N-יות סדורות בעלות n איברים, a ו-b, כך שאיברי a מסודרים מהקטן לגדול (נסמן אותם ב- $a_{1},a_{2}...,a_{n}$) ו-b בסדר מסוים (ומסומנים גם הם $b_{1},b_{2},...,b_{n}$), אז הביטוי $a_{1}b_{1}+a_{2}b_{2}+...+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}$. הוכחה: ביטוי שקול הוא

$0<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})$. כיוון שהביטויים בסוגריים הם שליליים, המכפלה שלהם חיובית.

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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