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

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

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

האי-שוויון קובע כי: אם נתונות שתי 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 מסודרים מהגדול לקטן מתקבל ערך מינימלי אנלוגית לחלוטין.