מתמטיקה שמחברת לאן אנחנו הולכים למקום שהיינו | מגזין קוונטה

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

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

פתרון אחד הולך ככה: התחל עם כל אדם לוחץ את היד של כל אדם אחר. עשרה אנשים, עם תשע לחיצות ידיים כל אחד, מייצרים 9 × 10 = 90 לחיצות ידיים בסך הכל. אבל זה סופר כל לחיצת יד פעמיים - פעם אחת מנקודת המבט של כל לוחץ - כך שמספר לחיצות היד בפועל הוא $latex frac{90}{2} = 45$. טיעון ספירה פשוט ומקסים לזכייה!

יש גם דרך אחרת לגמרי לפתור את הבעיה. תארו לעצמכם שהאורחים מגיעים אחד בכל פעם, וכשהם מגיעים לשם הם לוחצים ידיים לכל הנוכחים. לאדם הראשון אין ידיים ללחוץ, אז במסיבה של אדם אחד יש אפס לחיצות ידיים. כעת מגיע האדם השני ולוחץ יד לאדם הראשון. זה מוסיף לחיצת יד אחת לסך הכל, כך שבמסיבה של שני אנשים, יש 0 + 1 = 1 לחיצות יד בסך הכל. כאשר האדם השלישי מגיע ולוחץ ידיים לשני האורחים הראשונים, זה מוסיף שתי לחיצות ידיים לסך הכל. הגעתו של האדם הרביעי מוסיפה שלוש לחיצות ידיים לסך הכל, וכן הלאה.

אסטרטגיה זו מדגמנת את רצף לחיצות הידיים באופן רקורסיבי, כלומר כל מונח ברצף מוגדר ביחס לאלו שבאים לפניו. אתה בוודאי מכיר את רצף פיבונאצ'י, הרצף הרקורסי המפורסם מכולם. זה מתחיל ב-1, 1, 2, 3, 5, 8, 13, 21, וממשיך עם כל איבר שלאחר מכן שווה לסכום של השניים הקודמים.

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

בואו נראה איך חשיבה רקורסיבית עוזרת לבעיית לחיצת היד. אם נניח ל-$latex a_n$ שווה למספר לחיצות הידיים ב-an nצד-אדם, נוכל לייצג את היחסים הרקורסיביים עם הנוסחה הבאה:

$latex a_n = a_{n-1} + n–1$

זה אומר לנו שמספר לחיצות הידיים ב-an nמסיבת -אדם ($latex a_n$) שווה למספר לחיצות הידיים ב-(n − צד אחד ($latex a_{n-1}$) פלוס n − לחיצת יד אחת נוספת, תופסת את הרעיון שכאשר אדם חדש מגיע הוא מוסיף מספר מסוים של לחיצות יד חדשות לאלו שכבר התרחשו.

בגרסה הספציפית שלנו לבעיית לחיצת היד, אנו רוצים לדעת את $latex a_{10}$, מספר לחיצות הידיים במסיבה של 10 אנשים, כדי לגלות שאנו משתמשים ביחסים רקורסיביים

$latex a_{10} = a_9 + 9$

כדי למצוא את הערך של $latex a_{10}$, אנחנו רק צריכים לדעת את הערך של $latex a_9$ ולהוסיף לו 9. כיצד אנו מוצאים את הערך של $latex a_9$? על ידי שימוש ברקורסיה, כמובן!

$latex a_9 = a_8 + 8$

כעת, כדי למצוא את הערך של $latex a_8$, עלינו למצוא את הערך של $latex a_7$, מה שדורש להכיר את $latex a_6$ וכן הלאה. בשלב זה, אתה עשוי לדאוג שזה יימשך לנצח במין ירידה אינסופית, אבל ברגע שנגיע ל$latex a_1$ סיימנו, כי אנחנו יודעים שיש אפס לחיצות ידיים במסיבה של אדם אחד.

$latex a_1 = 0$

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

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$latex cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

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

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

במיוחד, הרקורסיה שימושית מכיוון שהיא נמצאת בכל מקום במתמטיקה. היא מתעוררת, למשל, ביחסים הליניאריים שכולם לומדים עליהם בשיעור מתמטיקה - אלה המאופיינים בקצב קבוע של שינוי ומיוצגים על ידי קווים במישור. ניתן לחשוב על פונקציה לינארית כמו $latex f(x) = 3x + 5$ כנוסחה רקורסיבית:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

למרות שהדרך הברורה יותר לחשוב על $latex f(2)$ עשויה להיות ש-$latex f(2) = 3 כפול 2 + 5 = 11$, דרך אחרת היא ש-$latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. מודל רקורסיבי של המאפיין הבסיסי של פונקציות ליניאריות - קצב השינוי הקבוע - נותן לנו דרך נוספת לחשוב על הקשר הזה. ניתן לעשות את אותו הדבר עם פונקציות אקספוננציאליות המאופיינות בשינוי כפל מתמיד.

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

$latex 2x + y = 10$

$latex 3x – y = 5$

אתה יכול תחילה להוסיף את שתי המשוואות יחד כדי לבטל את y משתנה, מה שמביא למשוואה $latex 5x = 15$. פתור את זה כדי לקבל $latex x =$ 3, החלף כדי למצוא $latex y = 4$, וסיימת. גישה זו משתמשת באלגוריתם רקורסיבי, שבו הפתרון למערכת נבנה מהפתרון למערכות קטנות יותר הקשורות. לדוגמה, כדי לפתור מערכת של 3 × 3, אתה מבטל משתנה אחד כדי להפוך אותו למערכת של 2 × 2, ואז שוב כדי להפוך אותו למערכת של 1 × 1. המשוואה הבודדת הקלה לפתרון היא כמו ערך המקור של תהליך רקורסיבי זה. זה מסמן את סוף החזרה לאחור, ומשם אתה עובד בחזרה במעלה שרשרת המשוואות, ממש כמו ברצף רקורסיבי.

יש אפילו טכניקות הוכחה רקורסיבית. לדוגמה, נוסחה מפורסמת בגיאומטריה היא נוסחת סכום זווית המצולע, האומרת שסכום המידות של הזוויות הפנימיות של nמצולע צדדי הוא $latex (n-2) כפול 180^{circ}$. אחת הדרכים להוכיח תוצאה זו היא להתחיל עם an n-תדמיין מה יקרה אם תסיר משולש.

הסרת משולש הופכת את n-הולכת לתוך (n − 1)-gon, והוא גם מסיר 180 מעלות של מדידת זווית פנימית. זהו קשר רקורסיבי: סכום הזווית הפנימית עבור an n-גון הוא 180 מעלות יותר מסכום הזווית הפנימית עבור (n − 1)-גון. כדי לקבוע את התוצאה הכללית, המשיכו להסיר משולשים עד שתגיעו לערך המקור, מה שבמצב זה קורה כאשר הסרת את כל פרט לשלושה n-הקודקודים של גון. בשלב זה המצולע הראשוני הצטמצם למשולש, שסכום הזווית הפנימית שלו ידוע כ-180 מעלות. כעת עבדו בחזרה למעלה, הוסיפו 180 מעלות בכל שלב ותקבלו את הנוסחה.

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

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

מתגלה דפוס נחמד:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$latex cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

כעת יש לנו דרך חדשה, וכללית, לחשוב על הבעיה: מספר לחיצות הידיים ב-an nמפלגת אדם שווה לסכום הראשון n − 1 מספרים שלמים חיוביים.

חשבו על הגישה המקורית שלנו. ב nמסיבת אדם, כל אדם ילחץ יד לשני n - 1 אנשים. המוצר $latex n (n-1)$ סופר כל לחיצת יד פעמיים, כך שהמספר הכולל של לחיצות היד הוא $latex frac{n(n-1)}{2}$. אבל מכיוון שהשיטות השונות שלנו סופרות את אותו הדבר, הן צריכות להניב את אותה תוצאה. בפרט, המשמעות היא:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

על ידי חיבור גישות שונות לבעיית לחיצת היד, נקבל נוסחה סגורה לסכום הראשון n − 1 מספרים שלמים חיוביים. אבל אנחנו מקבלים אפילו יותר: הביטוי $latex frac{n(n-1)}{2}$ כולל שבר, אבל מכיוון שהוא שווה לסכום של מספרים שלמים, גם הוא חייב להיות מספר שלם. זה מוכיח עובדה פשוטה בתורת המספרים: לכל מספר שלם n, $latex frac{n(n-1)}{2}$ הוא מספר שלם.

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

תרגילים

1. מצא נוסחה סגורה לרצף המוגדר באופן רקורסיבי
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. בסוף העמודה, הביטוי $latex frac{n(n-1)}{2}$ הוצג כמספר שלם למרות שהביטוי כולל שבר, מכיוון ש-$latex frac{n(n-1 )}{2}$ הוא תוצאה של ספירת משהו. יש גם טיעון של תורת המספרים שמראה שהביטוי הזה חייב להיות מספר שלם. מה זה?

3. מצא את האיברים הראשונים של הרצף הרקורסי
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. מצא את האיברים הראשונים של הרצף הרקורסי
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$