חידה

[1אברהם]

../images/Emo35.gifחידה../images/Emo35.gif

בכמה אופנים ניתן להושיב אנשים בשורה של n כיסאות , כך שלא יהיו 2 אנשים שישבו אחד ליד השני ?

 

[neozigi]

פתרון

א. אם נסמן (T(n את מספר האופנים בו ניתן לסדר אנשים ב-n כסאות. וב-(Z(n את מספר האפשרויות בהן הכסא האחרון הוא ריק. אזי , T=T(n-1) +Z(n-1) a Z=T(n-1) b מכיון שבסידור הבא ניתן להושיב ליד כל כסא ריק בקצה, אדם אחד או להשאירו ריק. ב. מכאן באינדוקציה מקבלים כי T=2*F +F(n-1) a b כאשר F הינו מספר פיבונאצי. ועבור 0 נשים 0

 

[1אברהם]

../images/Emo127.gif

אני מניח ש F מוגדרת כ

F(n=0,1,2...) = 0 1 1 2 3 5 8 13 21 34 ....​