אינדוקציות

[loresin1]

אינדוקציות

שאלה 8 בתמונה- בעיקרון פתרתי את התרגיל באינדוקציה, אבל יש דבר אחד שלא ברור לי- איך אני מראה בהכרח שזה מספר צעדים מינימלי?
זאת אומרת, הבסיס הוא n=0 ואז זה יוצא 0 שזה אכן מינימלי.
מניחים עבור k (מספר מינימלי להעברת k טבעות הוא הנוסחה שרשומה שם), ומוכיחים את נכונות הנוסחה עבור k+1 בדרך הבאה: משתמשים בהנחת האינדוקציה כדי להעביר k טבעות מהעמוד הימני לעמוד השמאלי, מעבירים את הדיסקית שנותרה על המוט הימני למוט האמצעי, ולבסוך משתמשים שוב בהנחת האינדוקציה כדי להעביר k טבעות מהעמוד השמאלי לאמצעי.
אם נחבר את מספר המהלכים שעשינו כאן (פעמיים הנחת האינדוקציה+1) נקבל בדיוק את הנוסחה שרשומה שם עבור n=k+1.
האם עצם כך שהוכחתי שהנוסחה מתקיימת בדרך שרשמתי כאן- זה מספיק כדי להראות שזהו מספר הצעדים המינימלי? משהו פשוט לא מסתדר לי. כאילו, אני חושב שלא שללתי את זה שיכולה להיות דרך מהירה יותר להעביר k+1 טבעות, אבל אני לא יודע אם זה באמת נדרש בהתחשב בכך שהוכחתי את נכונות הנוסחה.

שאלה 9- אין לי ממש מושג איך לגשת אליה. אני לא בטוח אפילו שזה באינדוקציה אבל נראה לי שכן. יש לכם רעיונות?

פורים שמח!

 

[עעעערררר]

אכן לא הוכחת מינימליות

בעצם, אם נסמן ב-Tzzz את מספר הצעדים (המינימלי) הדרושים להעברת מגדל בן n דסקיות, אז הוכחת את אי השוויון T(n+1)<=2T+1. מאי השוויון הזה, אפשר להראות מאינדוקציה כי T<=2^n-1.
&nbsp
כדי לחשב במדויק את Tzz, צריך להראות גם את אי-השוויון ההפוך, כלומר T(n+1)>=2T+1. כדי להראות אותו, אפשר לשים לב לעובדות הבאות:
א. כשמזיזים מגדל, לפחות באחד השלבים, מזיזים את הדסקית הגדולה ביותר.
ב. כאשר מזיזים את הדסקית הגדולה ביותר בין שני עמודים, כל שאר הדסקיות צריכות להימצא (לפי הסדר, כמובן) על העמוד השלישי.
ג. לפני הפעם הראשונה שמזיזים את הדסקית הגדולה ביותר, יש להעביר את המגדל שכולל את כל שאר הדסקיות.
ד. לאחר הפעם האחרונה שמזיזים את הדסקית הגדולה ביותר, יש להעביר את המגדל שכולל את כל שאר הדסקיות.
&nbsp
בשאלה 9, אין קשר למגדלי האנוי, וגם לא לאינדוקציה. אני מציע לקחת דירוג, שבו כל מגדל נבחר פעם אחת למקום הראשון, פעם אחת לשני ופעם אחת לשלישי.

 

[loresin1]

אמממ

כמה דברים שלא ברורים לי:
1. כתבת שהוכחתי רק את אי השוויון קטן שווה- אבל למה בעצם?
אם אני מבין נכון, אתה בעצם כותב לי שהוכחתי כאן שמספר הצעדים הוא לכל היותר הנוסחה שרשומה, אך לא מצליח להבין מבחינה לוגית למה. מה שכן אני יכול להבין לוגית- שבהוכחה שלי הראיתי שאכן ניתן להעביר דסקיות במספר הצעדים הנתון לפי הנוסחה, מבלי לפרט ממש האם זה מספר מינימלי או מקסימלי (עושה רושם שלא שמתי את הדגשים איפה שצריך).
2. האלגוריתם שרשמת בסעיפים א'-ד' מזכיר את מה שאני רשמתי, אבל באמת לא הדגשתי שם את המינימליות כמו שאתה הדגשת בסעיפים האלה. אבל למה בעצם צריך לראות אי שיוויון משני הצדדים ולא רק את האי-שיווין שרשמת (הרי אנחנו רוצים להוכיח שזה לכל הפחות מספר הצעדים מהשאלה, ולא שזה מספר הצעדים המדויק)? עושה רושם שהאלגוריתם הזה מספיק בהחלט, לפחות לדעתי. לא ככה?
&nbsp
ותודה על העזרה כמובן!

 

[עעעערררר]

תשובות

1. ההגדרה של מספר הצעדים המינימלי, הוא מספר הצעדים שבו אפשר להעביר, אבל בפחות ממנו אי אפשר להעביר. לכן, אם אנחנו מראים שאפשר להעביר ב-k צעדים, זה אומר ש-T(n+1)<=k. (יהיה שוויון אם k הוא פתרון אופטימלי, ואי-שוויון חזק אם לא)

2. לא רשמתי אלגוריתם להעברה. רשמתי תכונות שכל אלגוריתם חייב לקיים. מהתכונות האלה, קל להסיק שאי אפשר להעביר בפחות מ-2T+1 צעדים. מכיוון שאפשר (לפי ההגדרה) להעביר ב-T(n+1)zz צעדים, ברור כי T(n+1)>=2T+1.

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

 

[loresin1]

אוקיי אז

האלגוריתם שרשמת בסעיפים א'-ד' הוא רק כיוון אחד, וצריך להראות גם את הכיוון השני?
פשוט הסתדר לי רק להשתמש בו בניסוח שרשמת (כמובן בהוכחת אינדוקציה מלאה), בלי להראות את הכיוון האחר כדי לפתור את השאלה

 

[עעעערררר]

שוב: לא רשמתי אלגוריתם

התכונות שרשמתי מסייעות בהוכחת כיוון אחד. מה שרשמת בהודעה הפותחת הוא הכיוון השני.