תרגיל 1

תשובה: $F(n)=36\cdot 6^n+6\cdot (-1)^n$.
הוכחה:
נגדיר נוסחת נסיגה:

נסמן $A(x)=\displaystyle\sum_{i=0}^\infty F(i)x^i$ ואז:

לכן מתקיים:

כעת, נוכל לפרק לשברים חלקיים:

לכן נקבל:

נזכר כי לפי אינפי $\displaystyle \frac{1}{1-x}=\sum_{i=0}^\infty x^i$ ולכן מתקיים:

ולכן:

∎

תשובה: $F(n)=36\cdot 6^n+6\cdot (-1)^n$.
הוכחה:
נוסחת הנסיגה ליניארית ולכן נוכל לפתור באמצעות פולינום אופייני.

נסמן:

נפתור ונקבל כי:

נציב בנוסחה כללית:

נתונים לנו תנאי ההתחלה $F(0)=24,F(1)=210$, נשתמש בהם על מנת לקבל שתי משוואות בשני נעלמים:

לכן, נקבל כי:

∎

התשובות בסעיף א' ו-ב' זהות שכן המשוואות זהות ולכן לכל איבר $n \in \mathbb{N}$ מתקיים ש-$F_{א}(n)=F_{ב}(n)$.

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

נגדיר $\displaystyle A(x)=\sum_{i=0}^\infty\ G(i)x^i$ ואז:

נשתמש במשפט גזירה איבר-איבר:

נקבל כי:

לפי הנוסחה הנתונה בתרגיל, אם נסמן $P(x)=1-x,\;R(x)=1-2x+4x^2-x^3$ ו-$Q(x)=1-3x$ אזי נקבל:

מכך נקבל את המשוואות הבאות:

נפתור אותם מהאחרונה לראשונה:

לכן נקבל כי:

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

לפי הנוסחה $\displaystyle \frac{1}{(1-x)^m}=\sum_{i=0}^\infty \mathbb{C}_{m}^i x^i$ נקבל כי:

לכן מתקיים:

לכן, הנוסחה המפורשת לנוסחת הנסיגה הינה:

∎

נוסחת הנסיגה פה היא אינה הומוגנית, ולכן, לא ניתן להשתמש פה בשיטת הפולינום האופייני.
הסיבה היא שכדי לקבל פולינום אופייני אנו מנחשים את היות הפתרון $k^n$ ואז מחלקים את כל הביטוי ב-$k^{n-1}$ מה שנותן לנו פולינום ליניארי שאינו תלוי ב-$n$. בנוסחת הנסיגה הזו יש לנו איבר חופשי $n^2$ אשר ימשיך להיות תלוי ב-$n$ ולכן לא יווצר לנו פולינום במשתנה 1 ⟸ לא ניתן להשתמש בשיטת הפולינום האופייני.

תרגיל 3

נתחיל מ-$K_{2}$, לו יש $\begin{pmatrix}2\\ 2\end{pmatrix}=1$ קשתות.
​
נעבור כעת ל-$K_{3}$, לו יש $\begin{pmatrix}3\\ 2\end{pmatrix}=\frac{3!}{2!1!}=3$ קשתות.
​
לבסוף, נסתכל על $K_{4}$ לו יש $\begin{pmatrix}4\\ 2\end{pmatrix}=\frac{24}{2!2!}=\frac{24}{4}=6$ קשתות.
​

הוכחה:
מכיוון שהגרף מלא, קיימות כל הקשתות האפשריות בגרף ולכן, מכל צומת $u_{k}$ יוצאת קשת לכל צומת אחרת $u_{j}$ ולכן, לכל הצמתים אותו מספר קשתות $|V|-1$ שכן יש $|V|$ צמתים ולכן, $|V|-1$ צמתים שהם לא הצומת $u_{k}$.
לכן, לכל צומת $u_{k}$ (כאשר $1\leq k\leq 6$) מתקיים $d(u_{k})=5$.
נקח צומת כללית $u_{i}$ כאשר $1\leq i\leq 6$ ונסתכל על חמשת הקשתות היוצאות ממנה. לפי עקרון שובך היונים המוכלל, יש לפחות צבע אחד ממנו יש $\left\lceil \frac{5}{2} \right\rceil=3$ קשתות. נניח בה"כ כי צבע זה הוא כחול ונסתכל על הצמתים בקצה השני של שלושת הקשתות הללו. נסמנם $u_{m},u_{n},u_{\ell}$. מכיוון שהגרף מלא, בהכרח קיימת קשת מכל אחד מהם לכל אחד אחר מהם.
אם לפחות אחת מהקשתות הללו היא כחולה, אז יש לנו מגעל פשוט בעל שלוש קשתות בדיוק אשר כולן בצבע כחול. זהו בדיוק משולש בו כל הקשתות בצבע כחול.
אם אף אחת מהקשתות הללו אינה בצבע כחול, אז נסתכל על המעגל הפשוט $u_{m}\edge{e_{mn}}u_{n}\edge{e_{n\ell}}u_{\ell}\edge{e_{\ell m}}u_{m}$ המורכב משלוש קשתות בדיוק, ולכן הוא משולש. כל הקשתות הללו בהכרח אינן בצבע כחול ולכן, מכיוון שיש רק עוד אופציה אחת, הן כולן בצבע לבן ולכן, קיים משולש בו כל הקשתות בצבע לבן.
לכן, קיים בגרף $K_{6}$ משולש בו כל הקשתות באותו הצבע.
∎

הטענה אינה נכונה.
נסתכל על הגרף המוגדר $G=(\left\{ u_{1},u_{2},u_{3},u_{4},u_{5} \right\},\left\{ e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{7},e_{8},e_{9},e_{10} \right\})$ המוגדר כך:
​
נשים לב כי $\begin{pmatrix}5 \\ 2\end{pmatrix}=10$ ולכן יש לנו את כמות הקשתות המתאימה.
לכל צומת יש בדיוק $2$ קשתות לבנות ובדיוק שתי קשתות כחולות ובין כל שלושה צמתים יש לפחות שתי קשתות בצבעים שונים, שכן לפי עקרון שובח היונים המוכלל, מובטח לנו שיהיה לפחות צבע אחד לו יהיו $\left\lceil \frac{4}{2} \right\rceil=2$ קשתות ולא $3$ קשתות כמו בסעיף הקודם..

הוכחה:
מכיוון שהגרף מלא, קיימות כל הקשתות האפשריות בגרף ולכן, מכל צומת $u_{k}$ יוצאת קשת לכל צומת אחרת $u_{j}$ ולכן, לכל הצמתים אותו מספר קשתות $|V|-1$ שכן יש $|V|$ צמתים ולכן, $|V|-1$ צמתים שהם לא הצומת $u_{k}$.
לכן, לכל צומת $u_{k}$ (כאשר $1\leq k\leq 6$) מתקיים $d(u_{k})=16$.
נקח צומת כללית $u_{i}$ כאשר $1\leq i\leq 17$ ונסתכל על 16 הקשתות היוצאות ממנה. לפי עקרון שובך היונים המוכלל, יש לפחות צבע אחד ממנו יש $\left\lceil \frac{16}{3} \right\rceil=6$ קשתות. נניח בה"כ כי צבע זה הוא כחול ונסתכל על הצמתים בקצה השני של שלושת הקשתות הללו. נסמנם $u_{m},u_{n},u_{\ell},u_{k},u_{j},u_{r}$. מכיוון שהגרף מלא, בהכרח קיימת קשת מכל אחד מהם לכל אחד אחר מהם.
אם לפחות אחת מהקשתות הללו היא כחולה, אז יש לנו מגעל פשוט בעל שלוש קשתות בדיוק אשר כולן בצבע כחול. זהו בדיוק משולש בו כל הקשתות בצבע כחול.
אם אף אחת מהקשתות הללו אינה בצבע כחול, אזי נסמן $V'=\left\{ u_{m},u_{n},u_{\ell},u_{k},u_{j},u_{r} \right\}\subset V$ ונסמן ב-$E'$ את קבוצת כל הקשתות ב-$E$ שמתחילות בצומת הנמצאת ב-$V'$ וגם מסתיימות בצומת הנמצאת ב-$V'$.
קיבלנו אם כן, גרף לא מכוון ופשוט $G'=(V',E')$ בו קיימות כל הקשתות האפשריות לאור העובדה שב-$G$ היו קיימות כל הקשתות האפשריות. לכן, $G'$ הוא גרף מלא בעל $|V'|=6$ צמתים.
אנו צובעים את הקשתות של גרף זה בשני צבעים בלבד: שחור ולבן, שכן אף קשת לא יכולה להיות כחולה לפי הנ"ל ולכן, לפי סעיף ב', קיים משולש שכל הקשתות שלו צבועות באותו הצבע.
לכן, קיים בגרף $K_{17}$ משולש בו כל הקשתות באותו הצבע.
∎

תרגיל 5

נסתכל על הגרף הבא:

הנראה כך:
​
נקבע:

נשים לב כי מתקיים:

כל קשת מחברת צומת זוגית, מקבוצה $B$, לצומת אי זוגית, מקבוצה $A$ כנדרש.

תשובה: $10^4$ קשתות
הוכחה:
יהי הגרף הדו צדדי $G=(V,E)$ בעל $200$ צמתים המחולקים לקבוצות זרות $A,B$.
נסמן $|A|=x$. אזי, לפי הגדרת גרף דו צדדי, מתקיים $B=\overline{A}$ כאשר $V$ הוא העולם ולכן, $|B|=200-x$.
מספר הקשתות המקסימלי מתקיים כאשר בגרף קיימות כל הקשתות האפשריות מכל צומת ב-$A$ לכל צומת ב-$B$. (כלומר, מכל צומת ב-$A$ קיימת קשת לכל צומת ב-$B$)
במצב מקסימלי זה, מספר הקשתות הוא כמספר האפשריות ליצור קשת מצומת ב-$A$ לצומת ב-$B$ כפול מספר הצמתים ב-$A$ לפי עקרון הכפל ולכן זה בדיוק $x(200-x)$ אפשרויות.
נסמן $f(x)=x(200-x)$ ונמצא את ה-$x$ המקסימלי של הפונקציה באמצעות גזירה:

הפונקציה הזו הינה פרבולה חד מימדית עם נקודת מקסימום ולכן, $x=100$ היא נקודת מקסימום של $f$ ולכן, מספר הקשתות המקסימלי הינו:

∎

תשובה: $6400$ קשתות.
הוכחה:
נסתכל על הפונקציה של מספר הקשתות מסעיף ב' $f(x)=x(200-x)$ אשר הינה פרבולה בעלת נקודת מקסימום.
נתון לנו כי קיים צומת מדרגה של לפחות $160$ ולכן, בקבוצה שהוא לא נמצא בה בחלוקה של $A,B$ יש לפחות $160$ צמתים איתם הוא יוכל ליצור קשתות שיתאימו להגדרת הגרף הדו צדדי. נניח בה"כ כי הקבוצה הזו היא $A$ ולכן $x=|A|\geq 160$.
במקטע שלאחר $x=100$ הפונקציה $f$ הינה יורדת ולכן, המקסימום נמצא ב-$x$ הקטן ביותר האפשרי בקטע ולכן, זה מתקיים עבור $x=160$. אזי נקבל כי מספר הקשתות הינו:

∎

הוכחה:
נתון כי $G$ קשיר ולכן, לכל צומת $v \in V$ מתקיים $d(s,v)\neq \infty$.
⟹: נגדיר $A=\left\{ v \in V\;|\; d(s,v)(mod\; 2)\equiv 0 \right\}$ ו-$B=\left\{ v \in V\; | \; d(s,v)(mod\; 2)\equiv 1 \right\}$.
נשים לב כי מתקיים מספר בהכרח זוגי או אי זוגי אך לא שנייהם ולכן $A=\overline{B}$ ובנוסף $A \uplus B=V$ שכן כל מספר הוא זוגי או אי זוגי אך לא שניהם.
נתון כי לכל קשת $\left\{ u,v \right\}\in E$ מתקיים $|d(s,v)-d(s,u)|(mod\; 2)\equiv 1$. לכן מתקיים בהכרח כי אחד מהמרחקים זוגי והאחר אי זוגי. נניח בה"כ כי $d(s,u)(mod\; 2)\equiv0$ ו-$d(s,v)(mod\; 2)\equiv 1$ ולכן, $v \in B,u \in A$.
מכיוון שזה מתקיים לכל קשת ב-$E$, קיימות רק קשתות המחברות בין צמתים ב-$A$ לצמתים ב-$B$.
לכן, לפי הגדרה, הגרף $G$ דו צדדי.
⟸: נתון כי $G$ דו צדדי ולכן, קיימות שתי קבוצות $A,B \subseteq V$ כך ש-$A \cap B=\emptyset$ ו-$A \cup B=V$ ובנוסף, קיימות אך ורק קשתות מצמתים ב-$A$ ולצמתים ב-$B$.
נניח בה"כ כי $s \in A$, ונבחר $v \in A$. על מנת להגיע מ-$s$ ל-$v$ נדרש לעבור דרך צמתים ב-$B$.
קשת מ-$A$ ל-$B$ היא קשת $1$ ולכן זה אי זוגי, ואז קשת בחזרה ל-$A$ הן שתי קשתות ולכן זה מספר זוגי של קשתות.
לכן, מכיוון שכל מעבר בין $A$ ל-$A$ דורש מעבר ב-$B$, אנו יודעים כי $d(s,v)(mod\; 2)\equiv 0$.
בנוסף, עבור כל $u \in B$ מתקיים $d(s,u)(mod\; 2)\equiv 1$ מאותן הסיבות.
לכן, $|d(s,v)-d(s,u)|(mod\; 2)\equiv 1$ לכל $\left\{ u,v \right\}\in E$ כנדרש.
∎