חזור לתיקייה: שיעורי בית

גליון 1

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • תרגיל 1
  • תרגיל 2
  • תרגיל 3
  • תרגיל 4
  • תרגיל 5
  • תרגיל 6

גליון 1

02340141

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

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

גליון 1

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

uni-folder.vercel.app

תרגיל 1

תרגיל (1 [א])

יהיו 1≤m≤n1\leq m\leq n1≤m≤n טבעיים.
מהו מספר הפונקציות f:{1,2,…,m}→{1,2,…,n}f:\left\{ 1,2,\dots,m \right\}\to \left\{ 1,2,\dots,n \right\}f:{1,2,…,m}→{1,2,…,n} שהינן מונוטוניות לא יורדות?

תשובה: Cnm=(n+m−1m)\mathbb{C}_{n}^m=\begin{pmatrix}n+m-1\\ m\end{pmatrix}Cnm​=(n+m−1m​)
הוכחה:
לפי משפט מההרצאה, מספר הסדרות המונוטוניות לא יורדות באורך mmm מעל {1,2,…,n}\left\{ 1,2,\dots,n \right\}{1,2,…,n} הינו Cnm\mathbb{C}_{n}^mCnm​.
פונקציה מעל {1,2,…,m}\left\{ 1,2,\dots,m \right\}{1,2,…,m} הינה שקולה לסדרה באורך mmm כאשר כל איבר aia_{i}ai​ מייצג את f(i)f(i)f(i) בפונקציה.
∎

תרגיל (1 [ב])

יהיו 1≤m≤n1\leq m\leq n1≤m≤n טבעיים.
מהו מספר הפונקציות f:{1,2,…,m}→{1,2,…,n}f:\left\{ 1,2,\dots,m \right\}\to \left\{ 1,2,\dots,n \right\}f:{1,2,…,m}→{1,2,…,n} שהינן על?

תשובה: m<n:0m=n:n!\begin{matrix}m<n:& 0\\m=n:& n!\end{matrix}m<n:m=n:​0n!​
הוכחה:
נתון כי m≤nm\leq nm≤n. על מנת שפונקציה תהא על, נדרש שלכל i∈{1,2,…,n}i \in \left\{ 1,2,\dots,n \right\}i∈{1,2,…,n} יהיה קיים k∈{1,2,…,m}k \in \left\{ 1,2,\dots,m \right\}k∈{1,2,…,m} כך ש-f(k)=if(k)=if(k)=i. על מנת שזה יתרחש נדרש כי m≥nm\geq nm≥n. לכן, האופציה היחידה שמתאימה לבעיה שלנו היא m=nm=nm=n.
סידור nnn האיברים בפונקציה הינה כמו סידור nnn איברים בקבוצה, שזוהי בדיוק תמורה. גודל קבוצת כל התמורות הינו Pnn=(nn)n!=n!P_n^n=\begin{pmatrix}n\\ n\end{pmatrix}n!=n!Pnn​=(nn​)n!=n! ולכן, זהו מספר הפונקציות המתאימות לבעיה שהינן על.
∎

תרגיל (1 [ג])

יהיו 1≤m≤n1\leq m\leq n1≤m≤n טבעיים.
מהו מספר הפונקציות f:{1,2,…,m}→{1,2,…,n}f:\left\{ 1,2,\dots,m \right\}\to \left\{ 1,2,\dots,n \right\}f:{1,2,…,m}→{1,2,…,n} שהינן חח"ע?

תשובה: (nm)m!\begin{pmatrix}n\\ m\end{pmatrix}m!(nm​)m!
הוכחה:
פונקציה היא חח"ע אם לכל i≠ji \neq ji=j כך ש-i,j∈{1,2,…,m}i,j \in \left\{ 1,2,\dots,m \right\}i,j∈{1,2,…,m} מתקיים f(i)≠f(j)f(i)\neq f(j)f(i)=f(j). לכן, כל פונקציה על היא בחירה של mmm איברים ללא חזרות מתוך nnn. זה קורה עם חשיבות לסדר.
זה בדיוק PnmP_{n}^mPnm​. ולפי משפט מההרצאה מתקיים:

Pnm=(nm)m!P_{n}^m =\begin{pmatrix} n \\ m \end{pmatrix} m!Pnm​=(nm​)m!

∎

תרגיל (1 [ד])

יהיו 1≤m≤n1\leq m\leq n1≤m≤n טבעיים.
מהו מספר הפונקציות f:{1,2,…,m}→{1,2,…,n}f:\left\{ 1,2,\dots,m \right\}\to \left\{ 1,2,\dots,n \right\}f:{1,2,…,m}→{1,2,…,n} שלכל i∈{1,2,…,m}i \in \left\{ 1,2,\dots,m \right\}i∈{1,2,…,m} מתקיים f(i)≥if(i)\geq if(i)≥i?

תשובה: n!(n−m)!\frac{n!}{(n-m)!}(n−m)!n!​
הוכחה:
נשים לב כי לכל i∈{1,2,…,m}i \in \left\{ 1,2,\dots,m \right\}i∈{1,2,…,m} נוכל לבחור f(i)∈{i,i+1,…,n}f(i)\in \left\{ i,i+1,\dots,n \right\}f(i)∈{i,i+1,…,n}.
לכן, ל-mmm נוכל לבחור מתוך n−mn-mn−m אפשרויות. ל-m−1m-1m−1 נוכל לבחור מתוך n−m+1n-m+1n−m+1 אפשרויות וכך הלאה.
באמצעות עקרון הכפל נקבל:

∏i=1mn−i+1=n(n−1)(n−2)…(n−m+1)=n!(n−m)!\prod_{i=1}^m n-i+1=n(n-1)(n-2)\dots(n-m+1)=\frac{n!}{(n-m)!}i=1∏m​n−i+1=n(n−1)(n−2)…(n−m+1)=(n−m)!n!​

∎

תרגיל 2

תרגיל (2 [א])

בכמה אפשרויות ניתן לסדר 171717 סטודנטים, 404040 מרצים ו-606060 תלמידים בשורה ללא מגבלות?

תשובה: 114!114!114!
הוכחה:
זהו סידור של 14+40+6014+40+6014+40+60 אנשים בשורה, כלומר, זה תמורה של 114114114 ולכן, לפי נוסחה, זה (114)!(114)!(114)!.
∎

תרגיל (2 [ב])

בכמה אפשרויות ניתן לסדר 171717 סטודנטים, 404040 מרצים ו-606060 תלמידים בשורה כך שיהיה רצף של 171717 סטודנטים, 404040 מרצים ו-606060 תלמידים

תשובה: 3!⋅(17!⋅40!⋅60!)3!\cdot (17!\cdot 40!\cdot 60!)3!⋅(17!⋅40!⋅60!)
הוכחה:
נדרשנו שיהיה רצף של 171717 סטודנטים, רצף של 404040 מרצים ורצף של 606060 תלמידים. כלומר, מכיוון שזהו בדיוק המספר של אנשים בכל קבוצה, קבוצות הסטודנטים, המרצים והתלמידים מופרדות.
יש לנו 3!3!3! דרכים לסדר את שלושת הקבוצות(סטודנטים, מרצים ותלמידים) בשורה, כעת נדרש גם לסדר בתוך הקבוצות.
בתוך כל קבוצה הסידור הינו ללא מגבלות, ולכן הוא תמורה של מספר האנשים בקבוצה. לכן נקבל:

3!⋅(17!⋅40!⋅60!)3!\cdot (17!\cdot 40!\cdot 60!)3!⋅(17!⋅40!⋅60!)

∎

תרגיל (2 [ג])

בכמה אפשרויות ניתן לסדר 171717 סטודנטים, 404040 מרצים ו-606060 תלמידים בשורה כך שיש רצף של 121212 סטודנטים בדיוק.
כלומר, אין 131313 סטודנטים היושבים ברצף.

תשובה:
הוכחה:
נתחיל בלסדר את המרצים והתלמידים. הם לא מחולקים לקבוצות ולכן, מספר האפשרויות הוא כמספר התמורות של 40+6040+6040+60. כלומר, 100!100!100!.
כעת, נרצה להכניס בין הסידור שלנו את הסטודנטים.
נסתכל על שורת האנשים שסידרנו כשורה של 100100100 אנשים כאשר ביניהם 101101101 מקומות להכנסת סטודנטים. לכל "חור" שכזה נוכל להכניס 0 עד 12 סטודנטים.
נסמן כל חור ב-iii ואת מספר הסטודנטים בכל חור ב-xix_{i}xi​. אזי מתקיים:

∀1≤i≤101:  0≤xi≤12∧∑i=1101xi=17\forall 1\leq i\leq 101:\; 0\leq x_{i}\leq 12\quad \land \quad \sum_{i=1}^{101} x_{i}=17∀1≤i≤101:0≤xi​≤12∧i=1∑101​xi​=17 ??????????????????

∎

תרגיל 3

תרגיל (3 [א])

בחנות ממתקים יש 4n4n4n סוכריות לבנות ו-2n2n2n סוכריות שחורות. הסוכריות זהות.
את הסוכריות ניתן לארוז בשקית בצבע זהב או שקית שקופה.

בכמה דרכים ניתן לחלק את הסוכריות ל-2n2n2n שקיות כך שבכל שקית 333 סוכריות ויש לפחות אחת לבנה ואחת שחורה?

תשובה: 2n+12n+12n+1.
הוכחה:
כל שקית יכולה להיות שקופה או בצבע זהב, זה 222 אפשרויות לכל אחת מ-2n2n2n השקיות. נבחר שקית שקופה כאפשרות הרגילה ואז, לכל שקית נוכל לבחור להחליף את השקית השקופה בשקית זהובה. לכן, יש לנו מחרוזת בינארית של 000 כל פעם שיש שקית שקופה ו-111 בכל פעם שיש שקית זהובה. נשים את כל האחדים בהתחלה ואז יש לנו 2n2n2n אפשרויות למספר האחדים ועוד אפשרות אחת שבה יש רק אפסים. לכן, יש 2n+12n+12n+1 אפשרויות.
בכל שקית נכניס סוכריה אחת לבנה ואחת שחורה, זו אפשרות אחת בלבד.
כעת, לכל שקית יש 2 אפשרויות, הראשונה סוכריה לבנה והשניה שחורה. אך נשים לב כי יש לנו רק 2n2n2n סוכריות שחורות, לכן, מכיוון שבכל שקית יש סוכריה אחת שחורה אחת לפחות, בכל שקית יש בדיוק סוכריה אחת שחורה לפי עקרון שובך היונים.
לכן, יש לנו רק אפשרות אחת: 2 סוכריות לבנות וסוכריה אחת שחורה בכל שקית.
לכן, סה"כ, לפי עקרון הכפל, יש לנו 2n+12n+12n+1 אפשרויות.
∎

תרגיל (3 [ב])

בחנות ממתקים יש 4n4n4n סוכריות לבנות ו-2n2n2n סוכריות שחורות. הסוכריות זהות.
את הסוכריות ניתן לארוז בשקית בצבע זהב או שקית שקופה.

בכמה דרכים ניתן לחלק את הסוכריות ל-2n2n2n שקיות כך שבכל שקית 333 סוכריות ויש לפחות אחת לבנה ואחת שחורה ויש לפחות שקית אחת מכל צבע?

תשובה: 2n−12n-12n−1
הוכחה:
נשים לב כי כל האפשרויות המקיימות את סעיף זה מקיימות את הסעיף הקודם. כעת, נוסיף את התנאי שיש לפחות שקית אחת מכל צבע.
ישנם שתי אפשרויות בהן התנאי הזה לא מתקיים: הכל אחדים והכל אפסים.
לכן, לפי עקרון ההפרש:

{מספר המחרוזות הכולל}∖{מספר המחרוזות בהן התנאי החדש לא מתקיים}=2n+1−2=2n−1\left\{ \R{\text{מספר המחרוזות הכולל}} \right\}\setminus \left\{ \R{\text{מספר המחרוזות בהן התנאי החדש לא מתקיים}} \right\}=2n+1-2=2n-1{מספר המחרוזות הכולל}∖{מספר המחרוזות בהן התנאי החדש לא מתקיים}=2n+1−2=2n−1

∎

תרגיל (3 [ג])

בחנות ממתקים יש 4n4n4n סוכריות לבנות ו-2n2n2n סוכריות שחורות. את הסוכריות ניתן לארוז בשקית בצבע זהב או שקית שקופה.
כעת התגלה שבכל אחת מהסוכריות יש פתגם ולכן סוכריות מאותו הצבע אינן זהות.

בכמה דרכים ניתן לחלק את הסוכריות ל-2n2n2n שקיות כך שבכל שקית יש לפחות 3 סוכריות, אחת לבנה ואחת שחורה ועוד אחת לא משנה הצבע?

תשובה: (4n)!(4n)!(4n)!
הוכחה:
נשים לב כי כמו בסעיף א', יש לנו סוכריה שחורה אחת לכל שקית ולכן בכל שקית יהיו שתי סוכריות לבנות ואחת שחורה.
בכל שקית נשים סוכריה שחורה אחת, יש לנו דרך אחת לעשות זאת שכן עד שאנו בוחרים דברים אחרים, כל השקיות "זהות".
כעת, נרצה לחלק את הסוכריות הלבנות, נדרש לשים 2 בכל שקית - נתחיל בלי התייחסות לסדר ואז זה יהיה תמורה של 4n4n4n. אך מכיוון שבכל שקית יש לנו 2 אפשרויות לסדר את הכדורים, נחלק ב-2!2!2! כדי למנוע ריבוי אפשרויות. זה מתרחש בכל שקית ולכן בעצם נחלק ב-(2!)2n(2!)^{2n}(2!)2n.
כעת, נדרש לבחור שקית, כל שקית יכולה להיות או שקופה או זהובה. זה שקול למחרוזת בינארית כאשר 0 מייצג שקית שקופה ו-1 מייצג שקית זהובה. מכיוון שכל שקית לא תלויה בשניה, יש לנו (2!)2n(2!)^{2n}(2!)2n.
לכן, לפי עקרון הכפל:

(4n)!(2!)2n(2!)2n=(4n)!\frac{(4n)!}{(2!)^{2n}}(2!)^{2n}=(4n)!(2!)2n(4n)!​(2!)2n=(4n)!

∎

תרגיל 4

Info (בהמשך)

תרגיל 5

תרגיל (5 [א])

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

יוסי יכול להטיל מחדש כל כמות של קוביות שיבחר בכל דקה. כמה רצפי צילומים שונים בני k+1k+1k+1 תמונות קיימים המסתיימים בכך שלא בהכרח כל הקוביות מראות 1?

תשובה: 5100⋅6100k5^{100}\cdot 6^{100^{k}}5100⋅6100k
הוכחה:
נסתכל על צילום יחיד תחילה.
כל קוביה היא מקרה נפרד, לכן, נשתמש בעקרון הכפל. כל קוביה היא מקרה זהה ולכן נקבל x100x^{100}x100 כאשר xxx הוא מספר האפשרויות לכל קוביה.
לכל קוביה יש 6 אפשרויות ולכן, x=6x=6x=6. בכך, בכל צילום יש 61006^{100}6100 אפשרויות.
ישנם kkk צילומים לאחר הראשון ולכן, גם כן לפי עקרון הכפל, יש 6100⋅6100⋯6100=6100k6^{100}\cdot 6^{100}\cdots6^{100}=6^{100^{k}}6100⋅6100⋯6100=6100k.
נוסף לכך, גם המצב ההתחלתי אינו מוגדר ויכול להיות כל מצב של הקוביות חוץ מ-1. לכן מתקיים כי למצב ההתחלתי יש 51005^{100}5100 אפשרויות.
לכן, לפי עקרון הכפל יש 5100⋅6100k5^{100}\cdot 6^{100^{k}}5100⋅6100k אפשרויות לרצפים.
∎

תרגיל (5 [ב])

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

נתון k=100k=100k=100. בכל דקה יוסי בוחר בדיוק קוביה אחת שאינה מראה 1 ומטיל אותה כך שבצילום הבא היא מראה 1. כמה רצפי צילומים שונים קיימים?

תשובה: 5100⋅(100)!5^{100}\cdot (100)!5100⋅(100)!
הוכחה:
אנו מתחילים מאותו מצב התחלתי כמו בסעיף א', לכן, יש 51005^{100}5100 אפשרויות למצב זה.
כעת, אנו מטילים כל קוביה עד שהיא מקבלת את הערך 1 לפני הצילום הבא. בכל צילום אנו משנים קוביה אחת בלבד. לכן, בצילום הראשון יש לנו 100100100 אפשרויות לבחור, שכן יש 100 קוביות שערכן אינו 1. בצילום השני יש 99 אפשרויות שכן יש קוביה אחת שערכה 1 וכך הלאה.
לכן, יש (100)!(100)!(100)! אפשרויות סה"כ מכיוון שיש 100100100 צילומים שזה מספיק כדי להפוך את כל הקוביות לערך 1.
לכן, לפי עקרון הכפל יש 5100⋅(100)!5^{100}\cdot (100)!5100⋅(100)! אפשרויות לרצפי צילומים.
∎

תרגיל (5 [ג])

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

נתון k=100k=100k=100. בכל דקה יוסי בוחר קבוצה של קוביות הכוללת לפחות קובייה אחת מבין אלו שאינן מראות 1 ומטיל אותן כך שבצילום הבא כולן מראות 1. כמה רצפי צילומים שונים קיימים המסתיימים בתמונה שבה כל הקוביות מראות 1?

תשובה: 5100⋅(100)!5^{100}\cdot(100)!5100⋅(100)!
הוכחה:
נתון כי ישנם 100100100 צילומים. בכל צילום חייבת להיות לפחות קוביה אחת שהיא אינה 1 שכן אחרת הוא לא יוכל לגלגל את הקוביות ונתון שבכל דקה יוסי בוחר קבוצה של קוביות לגלגל.
לכן, בצילום ה-100100100 בהכרח יש לפחות קוביה אחת שהיא איננה 1. מתוך כך, בצילום ה-999999 יש בהכרח לפחות 2 קוביות שהן אינם 1. וכך הלאה עד שבצילום ה-0 יש 100100100. לכן, בכל צילום יוסי בהכרח בוחר קבוצה בעלת קוביה יחידה שהיא אינה 1.
מכיוון שלנו משנה רק השינוי בין כל צילום לצילום, והקוביות שערכן 1 לא משתנות שכן הן נשארות 1, המקרה הזה זהה למקרה של סעיף ב' ולכן התשובה גם פה היא 5100⋅(100)!5^{100}\cdot(100)!5100⋅(100)!.
∎

תרגיל 6

Info (בהמשך)