חזור לתיקייה: תרגול

4+5 - שובך היונים, רקורסיה ואינדוקציה

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • כללי
  • עקרון שובך היונים
  • רקורסיה
  • רקורסיה רב מימדית

4+5 - שובך היונים, רקורסיה ואינדוקציה

02340141

קומבינטוריקה למדעי המחשב

רשימות תרגול לקריאה בשבת

4+5 - שובך היונים, רקורסיה ואינדוקציה

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

תרגיל

הוכיחו קומבינטורית:

∑i=2n(i−1)2n−i=2n−n−1\sum_{i=2}^n (i-1)2^{n-i}=2^n-n-1i=2∑n​(i−1)2n−i=2n−n−1
הערה (ענן המחשבות)

הסכום הזה מעיד שיש חיבור. כלומר, חלוקה למקרים זרים.

ככל הנראה נשתמש בעקרון המשלים שכן יש חיסור.
נשים לב כי יש 2n2^n2n. זה מזכיר לנו את מספר המילים הבינאריות באורך nnn.
1 יכול לייצג ווקטור אפסים או ווקטור אחדים.
ה-nnn יכול לייצג וקטור עם 000 אחד או וקטור עם 111 אחד.
לכן נוכל להגיד כי 2n−n−12^n-n-12n−n−1 היא מספר הוקטורים הבינאריים עם לפחות שני אחדים(אם 1 מייצג וקטור אפסים ו-nnn מייצג ווקטור עם 1 אחד)
כעת, נוכל לכתוב את הבעיה שלנו.

כעת, לאחר שכתבנו את הבעיה לצד ימין, נרצה להסתכל על צד שמאל.
יש לנו iii אינדקסים שאיתם נעשה משהו ויש לנו השלמה באורך של n−in-in−i ללא מגבלות.(שכן יש 2n−i2^{n-i}2n−i)
יש i−1i-1i−1 אפשרויות אם מתוך ה-iii מקומות אנו יכולים לבצע בחירה של מיקום משהו ב-i−1i-1i−1 מקומות. כלומר, נשים 1 במקום ה-iii ואז נבחר מקום של 111 שני ב-i−1i-1i−1 המקומות שנותרו.
לכן, בכל מילה יש יותר מ-222 אחדים.

הוכחה:
בעיה: מספר הוקטורים הבינאריים מאורך nnn עם לפחות שני אחדים.
צד ימין: מספר הוקטורים הבינאריים מאורך nnn הינו 2n2^n2n. מספר הוקטורים עם 111 יחיד הוא nnn כאשר זה מספר האפשרויות לבחור את המקום של 111 במילה באורך nnn. בנוסף, וקטור האפסים הוא וקטור אחד בלבד. לכן, לפי עקרון המשלים, מספר הוקטורים … הינו:

2n−n−12^n-n-12n−n−1

צד שמאל: נפריד למקרים זרים לפי מיקום ה-111 השני בוקטור. נסמן ב-iii את המיקום של 2≤i≤n2\leq i \leq n2≤i≤n.
וקטורים עם לפחות שני אחדים שהאחד השני באינדקס iii. נבחר את מיקום ה-111 הראשון מ-i−1i-1i−1 אופציות. כל השאר יהיו 000.
נמלא את n−in-in−i האינדקסים באיזו דרך שנרצה ולכן זה 2n−i2^{n-i}2n−i.
בסה"כ נקבל:

∑i=2n(i−1)2n−i\sum_{i=2}^n (i-1)2^{n-i}i=2∑n​(i−1)2n−i

∎

עקרון שובך היונים

אם מכניסים n+1n+1n+1 יונים ל-nnn שובכים, אז קיים שובך עם לפחות שתי יונים.

העקרון המוכלל: אם מכניסים nnn יונים ל-kkk שובכים, אזי קיים שובך עם לפחות ⌈nk⌉\left\lceil \frac{n}{k} \right\rceil⌈kn​⌉ יונים.

תרגיל

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

הערה (ענן המחשבות)

יונים = מושבים ריקים
המושבים הריקים נכנסים בכל כל סטודנט. לכן אלו יהיו החורים שלנו.
סטודנטים - 170
מושבים ריקים - 520−170=350520-170=350520−170=350
מספר רווחים - 171171171 שכן יש רווח גם לפני הראשון ואחרי האחרון
כעת נוכל להתחיל לפתור

הוכחה:
נניח כי כל הסטודנטים יושבים ונחלק את המקומות הריקים בין הסטודנטים ובקצוות.
יש לנו 520−170=350520-170=350520−170=350 מושבים ריקים לחלק ב-171171171 מקומות.
לפי עקרון שובך היונים המוכלל, קיים מרווח בין סטודנטים שבו יש ⌈350171⌉=3\left\lceil \frac{350}{171} \right\rceil=3⌈171350​⌉=3 מושבים ריקים.
לכן, קיים רצף של שלושה מושבים ריקים.
∎

רקורסיה

נוסחת נסיגה היא נוסחה אשר מגדירה את עצמה.
מה המטרה של זה?

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

מצאו את נוסחת הנסיגה למספר הוקטורים הבינאריים באורך nnn אשר לא מכילים את הרצף 001001001.

נגדיר f(n)f(n)f(n) הוא מספר הוקטורים באורך nnn שלא מכילים 001001001 כאשר n≥0n\geq 0n≥0.

הערה (השיטה לרוב)

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

נפריד למקרים לפי הרישא של הוקטור.

  • אם וקטור מתחיל ב-111 ניתן להשלים את הוקטור עם כל וקטור חוקי מאורך n−1n-1n−1.
  • אם וקטור מתחיל ב-010101 ניתן להשלים את הוקטור עם כל וקטור חוקי מאורך n−2n-2n−2.
  • אם וקטור מתחיל ב-000000 אז בהכרח כל הוקטור חייב להיות אפסים שכן אם יש אחד איפשהו בהכרח יש לפניו לפחות 222 אפסים ולכן רק וקטור האפס כביל פה. (ניתן להוכיח באינדוקציה)

סה"כ מספר האפשרויות הינו:

∀n≥2:    f(n)=f(n−1)+f(n−2)+1\forall n\geq 2:\;\; f(n)=f(n-1)+f(n-2)+1∀n≥2:f(n)=f(n−1)+f(n−2)+1

עם תנאי ההתחלה:

f(0)=1,f(1)=2f(0)=1, \quad f(1)=2f(0)=1,f(1)=2
תרגיל

בכמה דרכים ניתן לסדר nnn אנשים במעגל עם חשיבות לסדר בתוך המעגלים בלי חשיבות לסדר בין המעגלים.

נגדיר פונקציה: g(n)g(n)g(n) היא מספר הדרכים לסדר nnn אנשים במעגלים בלי חשיבות לסדר בין המעגלים המעגלים ועם חשיבות לסדר בתוך כל מעגל. כאשר n≥1n\geq 1n≥1.

הערה (ענן המחשבות)

נפריד למקרים לפי האדם nnn:

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

במידה והאדם לבד במעגל, נותר לסדר את n−1n-1n−1 האנשים שזה בדיוק g(n−1)g(n-1)g(n−1) כי האחד החדש לא משפיע.
אחרת, נסדר את 1,…,n−11,\dots,n-11,…,n−1 במעגלים ולזה יש g(n−1)g(n-1)g(n−1) אופציות. אחר כך, נבחר אחרי מי נשים את nnn עם כיוון השעון. יש n−1n-1n−1 אנשים ולכן יש n−1n-1n−1 אפשרויות לכך.
לכן, נוסחת הנסיגה שלנו תהא:

g(n)=g(n−1)+(n−1)g(n−1)=ng(n−1)g(n)=g(n-1)+(n-1)g(n-1)=ng(n-1)g(n)=g(n−1)+(n−1)g(n−1)=ng(n−1)

לכל n>1n>1n>1 כאשר g(1)=1g(1)=1g(1)=1.

הערה (למה אנו לא רוצים את 000?)

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

תרגיל

חשבו את מספר הוקטורים הטרינריים(0,1,20,1,20,1,2) בהם מספר זוגי של 111-ים.

נחשב זאת באמצעות נוסחאות נסיגה.
נגדיר T(n)T(n)T(n) הוא מספר הוקטורים הטרינאריים באורך nnn עם מספר זוגי של 111-ים לכל n≥0n\geq 0n≥0.
נפריד למקרים זרים לפי התו הראשון:

  1. אם התו הראשון הוא 0 או 2 אז ניתן להשלים עם כל וקטור חוקי מאורך n−1n-1n−1. זה בדיוק 2T(n−1)2T(n-1)2T(n−1) כאשר ה-222 הוא הבחירה בין 000 ל-222.
  2. אם התו הראשון הוא 111 אז ניתן להשלים עם כל וקטור באורך n−1n-1n−1 בו יש מספר אי זוגי של אחדים.
    נוכל לחשב זאת באמצעות המשלים: כל הוקטורים באורך n−1n-1n−1 פחות כל הוקטורים עם מספר זוגי של אחדים.
    3n−1−T(n−1)3^{n-1}-T(n-1)3n−1−T(n−1)

כעת נוכל להרכיב את הנוסחה שלנו:

T(n)=2T(n−1)+3n−1−T(n−1)=T(n−1)+3n−1T(n)=2T(n-1)+3^{n-1}-T(n-1)=T(n-1)+3^{n-1}T(n)=2T(n−1)+3n−1−T(n−1)=T(n−1)+3n−1

לכל n>0n>0n>0 כאשר T(0)=1T(0)=1T(0)=1.

הערה

נשים לב שכאשר n=1n=1n=1 יש לנו שלוש אפשרויות לוקטורים חוקיים: ווקטור עם 0,20,20,2.

האם נוכל להגיד למה שווה T(n)T(n)T(n) בתצורה מפורשת?

T(n)=3n+12T(n)=\frac{3^n+1}{2}T(n)=23n+1​

נוכיח זאת באינדוקציה:
בסיס: ברור(עבור כל תנאי התחלה ידנית)
צעד: נניח עבור T(n−1)T(n-1)T(n−1) ונוכיח עבור T(n)T(n)T(n).

T(n)=T(n−1)+3n−1=3n−1+12+3n−1=3⋅3n−1+12=3n+12T(n)=T(n-1)+3^{n-1}=\frac{3^{n-1}+1}{2}+3^{n-1}=\frac{3\cdot 3^{n-1}+1}{2}=\frac{3^n+1}{2}T(n)=T(n−1)+3n−1=23n−1+1​+3n−1=23⋅3n−1+1​=23n+1​

כנדרש.

רקורסיה רב מימדית

תרגיל

נתון ספספל באורך m≥1m\geq 1m≥1. רוצים להושיב על הספסל n≥0n\geq 0n≥0 סטודנטים.
בין כל שני סטודנטים צריכים להיות לפחות r≥0r\geq 0r≥0 מקומות ריקים כאשר rrr קבוע נתון.
חשבו את נוסחת הנסיגה f(n,m)f(n,m)f(n,m) של מספר ההושבות החוקיות.

נפריד למקרים לפי המושב הראשון:

  1. יהי סידור חוקי כך שהמושב הראשון הוא ריק. ואז אורך המושב שנותר הוא m−1m-1m−1 ומספר הסטודנטים שנותר הוא nnn.
    יש f(n,m−1)f(n,m-1)f(n,m−1) הושבות חוקיות.
  2. יהי סידור חוקי כך שבמושב הראשון יושב סטודנט. אז יש אורך m−1m-1m−1 עם n−1n-1n−1 סטודנטים. זה לא יהיה בדיוק אותו הדבר שכן הפונקציה לא על ולכן עוצמת הקבוצות לא שווה. נדרש למשהו מעט שונה פה והיא להוסיף את rrr הרווחים בהתחלה. לכן, נדרש לסדר m−r−1m-r-1m−r−1 מקומות עם n−1n-1n−1 סטודנטים שכעת לא משנה מה נמצא איפה ולכן זה בדיוק f(n−1,m−r−1)f(n-1,m-r-1)f(n−1,m−r−1). כעת נשאר לנו לבחור את הסטודנט במקום הראשון וזה nf(n−1,m−r−1)nf(n-1,m-r-1)nf(n−1,m−r−1).

לכן, מתקיים:

∀n≥1,m≥r+2:      f(n,m)=f(n,m−1)+nf(n−1,m−r−1)\forall n\geq 1,m\geq r+2:\;\;\; f(n,m)=f(n,m-1)+nf(n-1,m-r-1)∀n≥1,m≥r+2:f(n,m)=f(n,m−1)+nf(n−1,m−r−1)

כאשר f(n≥2,m≤r+1)=0f(n\geq 2,m \leq r+1)=0f(n≥2,m≤r+1)=0 ו-f(1,m≤r+1)=mf(1,m\leq r+1)=mf(1,m≤r+1)=m ו-f(0,m)=1f(0,m)=1f(0,m)=1.