בעיית הצפרדע הקופצת על עלה הלוטוס

הצפרדע יושבת על עלה הלוטוס השמאלי ביותר. כל צעד יכול לקפוץ לעלה הבא, או עלה אחד קדימה, אך לא לקפוץ אחורה. כמה דרכים יש לקפוץ לעלה האחרון, בידיעה שיש 10 עלי לוטוס ברצף?

רצף פיבונאצ'י הוא רצף של מספרים טבעיים המתחיל מ-0 ו-1, לאחר מכן המספר הבא ברצף יהיה סכום שני המספרים הקודמים: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... רצף זה נקרא על שם המתמטיקאי האיטלקי לאונרדו פיבונאצ'י, הידוע גם כלאונרדו דה פיזה (1170 - 1240). הוא נחשב לאחד מגדולי המתמטיקאים של ימי הביניים.

סדרת פיבונאצ'י הופיעה בספרו "ליבר אבאצ'י" בשנת 1202. בו הוא הציג את הסדרה באמצעות שתי בעיות קלאסיות: בעיית הארנב ובעיית מספר ה"אב הקדמון" של דבורה זכרית.

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

לא ניכנס לרצף הזה בפירוט. אם אתם מעוניינים, חפשו בגוגל "רצף פיבונאצ'י" או "Fibonacci Sequence" ותמצאו הרבה דברים מעניינים עליו.

כאן יש לנו בעיה מעניינת הקשורה לרצף הזה כדלקמן:

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

בכל צעד, הצפרדע תקפוץ לעלה הסמוך לעלה עליו היא עומדת או תדלג מעל העלה הזה לעלה הבא. הצפרדע לעולם לא תקפוץ אחורה. בכמה דרכים הצפרדע יכולה לקפוץ לעלה הימני ביותר?

>>>תשובה

וו קוק בה קאן

מורה למתמטיקה, אקדמיית אכירמדס, האנוי

קישור למקור: https://vnexpress.net/bai-toan-con-ech-nhay-tren-la-hoa-sung-4614992.html