שורה של מספרים

[עריסטו]

שורה של מספרים

יש מספר כרטיסים מסודרים בשורה. על כל כרטיס כתוב מספר (ממשי

). מושיקו מבצע את הפעולה הבאה: הוא בוחר שני כרטיסים סמוכים כך שהמספר השמאלי גדול מהימני, מוחק כל אחד מהמספרים וכותב במקומו מספר גדול פי 2, ומחליף את הכרטיסים ביניהם. הוכיחו כי מושיקו יכול לבצע רק מספר סופי של פעולות כאלה.

 

[עריסטו]

הבהרה

מושיקו משנה רק את המספרים על שני הכרטיסים שהוא בחר.

 

[ייץ]

נסיון

נראה לי שניתן להוכיח באינדוקציה. עבור 2 מספרים זה טריוויאלי. (לאחר ההחלפה המספר הימני גדול יותר). נניח שזה נכון עבור N ונוכיח עבור N+1. עבור N המספרים השמאליים מספר ההחלפות סופי. במידה ויתבצע חילוף עם המספר הימני ביותר מספר זה יגדל (מהקודם שהיה שם). שוב לפי האינדוקציה עבור N המספרים השמאליים מספר ההחלפות סופי. כל החלפה עם המספר הימני ביותר יציב שם ערך גדול ממה שהיה שם קודם. לאחר ההחלפה מספר ההחלפות ב N המספרים השמאליים הוא סופי. כיוון שיש מספר סופי של מספרים הרי שלכל היותר לאחר מספר סופי של החלפות יופיע בצד הימני המספר הגדול ביותר(אולי מוכפל ב 2 בחזקת מספר החלפות) אך לא ניתן יהיה לבצע שוב החלפה עם מספר זה.

 

[יאיר של תמר]

לא הבנתי משהו...

מי אמר שלא ניתן יהיה להגדיל ללא סוף את המספרים? כלומר, נניח שהיו בשני הימניים המספר 4 ו-5, ועכשיו הם 10 ו -8... זכור, שה-8 הזה יכול לההיפך ל-16... ואז אולי שוב, להתחלף אם ה-10... ואולי ניתן להמשיך את זה עד עולם?

 

[ייץ]

נכון

אבל תבין הימני ביותר חייב לגדול. (כלומר אם הוא היה 10 אם יתבצע חילוף הוא יגדל) לפי הנחת האינדוקציה מספר החילופים בצד שמאל הוא סופי.

 

[ייץ]

הבהרה

כיוון האינדוקציה צריך להיות הפוך. כלומר לאחר מספר סופי של החלפות בצד הימני יהיה המספר הקטן ביותר. כעת הוא כבר לא משתתף בהחלפות. ואז נכנסת הנחת האינדוקציה.

 

[ייץ]

מקווה שהפירוט יהיה יותר ברור

נניח שכל N המספרים הממוקמים במקומות A1..An בשורה הם לא שליליים. טענה: אם Ak קטן מ Ak+1,Ak+2..An אז המספר שהיה במקום ה K לא יוכל להיות במקום גבוה יותר (k+1,..n) גם אם הוא יוכפל כתוצאה מהחלפה. יותר מכך אם הוא הוחלף וכעת הוא ממוקם במקום K-1 הוא כבר לא יוכל לשוב למקום ה K. (המספר במקום ה K לאחר החלפות נוספות יהיה גדול או שווה למספר שהיה במקום k-1.) אם כל N המספרים הם לא חיוביים התנאי הוא הפוך כלומר: אם Ak גדול מ A1..Ak-1 אז המספר שהיה ב Ak לא יוכל להיות במיקום נמוך יותר בשורה. (גם לאחר החלפות). אם קיימים מספרים חיוביים ושליליים. התנאים הקודמים מתקיימים בהחלפות שבין מספרים חיוביים לחיוביים וגם בין שליליים לשליליים. אם בוצעה החלפה בין חיובי לשלילי המספר החיובי תמיד יהיה במיקום גבוה מהמספר השלילי גם לאחר החלפות. עכשיו לנימוק של הטענה שמספר ההחלפות סופי. נניח שעבור N מספרים מספר ההחלפות סופי ונוכיח עבור N+1. אם כל המספרים אי שליליים. נסתכל על N המספרים השמאליים. מספר ההחלפות שם סופי לפי ההנחה. במקרה והוחלף המספר הימני ביותר הרי מרגע זה המספר שהיה במקום ה 1+N יעבור למקום N. המספר שכעת במקום ה1 +N גדול מ המספר שכעת במקום An לכן המספר במקום An יוכל להתקדם רק שמאלה. לאחר מספר סופי של חילופים ב N-1 המספרים השמאליים אם יבוצע שוב חילוף עם המספר שב An הוא כבר לא יוכל לשוב למקום ה N. לכן לאחר מספר סופי של החלפות הוא יוכל להיות ממוקם לכל היותר במקום A1. מרגע זה לפי הנחת האינדוקציה יש מספר סופי של החלפות. אם המספרים אי חיוביים התקדמות המספר ב A1 תהיה רק ימינה ולכן כשיגיע למקום An+1 יהיו רק מספר סופי של החלפות. באותה דרך מוכיחים אם יש גם חיוביים וגם שליליים כי אם יש הפרדה מוחלטת כל אחד מהצדדים יסתדר. ואם אין הפרדה ברגע חילוף של חיובי לשלילי כל אחד ישאר בצד שלו. ההסבר ארוך אך אין לי מספיק כלים מתמטיים לנמק זאת יותר בקיצור.

 

[ןן גיל ןן]

../images/Emo127.gif

לקח לי זמן להבין את ההסבר שלך אבל הוא נכון. אצלך המקום הימני ביותר ממוספר ע"י 1, וזה היה המקור לחוסר ההבנה שלי. ברשותך אחזור על ההסבר: אם כל המספרים חיוביים: יהי t מספר התאים (פרט לימני ביותר) שערכם נמוך מערך התא הימני ביותר. אז בכל צעד של מושיקו, t לא יכול לגדול. כי או שיש החלפה עם התא הימני ביותר, ואז t קטן, או ששני מספרים משמאל לימני ביותר גדלים פי 2 וגם אז t קטן או נשאר קבוע. לכן, אחרי מספר סופי של צעדים, t לא קטן יותר. ולכן, המספר הימני לא יזוז יותר. ואז, ממשיכים את הטיעון (או משתמשים באינדוקציה) לגבי שאר n-1 המספרים. אם כל המספרים שליליים: אותו הטיעון כמו קודם רק בכיוון ההפוך- כלומר מתבוננים בתא השמאלי ביותר, מספר התאים שערכם גדול ממנו הולך וקטן בהתמדה. כשמספר זה מתייצב, ממשיכים עם שאר התאים. במקרה הכללי: יהי k מספר זוגות המקומות i,j כאשר i נמצא מימין ל- j, (לא בהכרח בסמיכות), המספר במקום ה- i חיובי והמספר במקום ה- j שלילי. אז שוב, בכל צעד, k קטן או נשאר אותו הדבר, אך לא יכול לגדול. ולכן אחרי מספר סופי של צעדים, k לא משתנה יותר ולכן אין יותר חילופים בין חיוביים לשליליים. ולכן אפשר להשתמש במה שהוכחנו כבר לגבי החיוביים והשליליים בנפרד. (רצף המספרים מתחלק ל"איים" של מספרים חיוביים ושליליים ובכל "אי" כזה מספר החילופים הוא סופי).

 

[עריסטו]

../images/Emo127.gif הוכחה נכונה