Re: שאלה באינדוקציה
Soli Vishkautsan
From: מלי זיתוני <mali.z...@gmail.com>
To: Soli Vishkautsan <wis...@yahoo.com>
Sent: Tuesday, April 28, 2009 3:08:49 PM
Subject: שאלה באינדוקציה
את השאלה באינדוקציה הבנתי מבחינת הרעיון
כל פעם מחלקים לשלוש ושמים שליש בכל צד מהמאזנים ומאתרים את הקבוצה שבה המטבע המזוייף
אח"כ לוקחים את הקבוצה הזאת מחלקים לשלוש שמים שליש בכל צד מהמאזנים עד שנשארים עם 3 מטבעות
ובכל צד יהיה מטבע אחד.
אבל איך אני כותבת באינדוקציה?
מספיק לכתוב שהנחת האינדוקציה היא עבור אן ואז שמוכיחים עבור אן + 1
זה כפול שלוש. אם זה כפול שלוש צריך להוסיף לאן עוד אחד ???
תודה:)
ינון
לבחור את הבסיס 0.(גם יותר קל להסביר למה זה עובד עבור בסיס 0)
שלב ב': הנחה עבור אן. כלומר בעזרת אן שקילות ניתן למצוא את המטבע בערימה
של אן^3 מטבעות
שלב ג': הוכחה עבור אן+1. עלינו להוכיח כי מספיק אן+1 שקילות כדי למצוא
מטבע מזויף בתוך (1+אן)^3 מטבעות.
נחלק את המטבעות ל3 קבוצות של אן^3 מטבעות כל אחת.
נבחר באופן שרירותי שתי קבוצות מתוך ה3 ונשים כל אחת מהן בצד
אחר של המאזניים. אם הן שוות במשקלן,נבחר את הקבוצה השלישית. אחרת, נבחר
את הקלה מבין השתיים.
נשארנו עם קבוצה בעלת אן^3 מטבעות, ולפי הנחת האינדוקציה
מספיקות אן שקילות על מנת למצוא בה את המטבע המזוייף.
סה"כ ביצענו שקילה אחת(כדי למצוא את הקבוצה הנכונה)+אן שקילות
(כדי למצוא את המטבע).1+אן שקילות. מ.ש.ל.
On Apr 28, 9:12 pm, Soli Vishkautsan <wish...@yahoo.com> wrote:
> מעולם לא פתרתי את השאלה, אז אני לא לגמרי בטוח, אבל אני משער שזה יתחיל ככה:
> יש לנו
> n+1
> מטבעות,
> תוציאי מטבע מהקבוצה ואז יש שתי אפשרויות,
> (שאנחנו לא יודעים עדיין איזו אחת נכונה).
> או שהמטבע שבחרת הוא המטבע המזויף
> או שהמטבע המזויף ב
> n
> מטבעות.
> מכאן צריך להמשיך איכשהו.
> אם אנחנו יודעים שקורה המקרה השני, אז אפשר להמשיך באינדוקציה....
>
> ________________________________
> From: מלי זיתוני <mali.zait...@gmail.com>
> To: Soli Vishkautsan <wish...@yahoo.com>
