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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

האי-שוויון קובע כי: אם נתונות שתי N-יות סדורות בעלות n איברים, a ו-b, כך שאיברי a מסודרים מהקטן לגדול (נסמן אותם ב- a1,a2...,an) ו-b בסדר מסוים (ומסומנים גם הם b1,b2,...,bn), אז הביטוי a1b1+a2b2+...+anbn מקבל ערך מקסימלי כאשר גם איברי b מסודרים מהקטן לגדול. ערך מינימלי מתקבל כאשר הם מסודרים מהגדול לקטן.

הוכחה

טענת עזר: אם a1<a2 ו-b1<b2, אז a1b2+a2b1<a1b1+a2b2. הוכחה: ביטוי שקול הוא

0<a1b1+a2b2a1b2a2b1 או
0<(a1a2)(b1b2). כיוון שהביטויים בסוגריים הם שליליים, המכפלה שלהם חיובית.

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

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

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

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