האוניברסיטה הפתוחה
ט"ז באלול תשפ"ב
12 בספטמבר 2022
סמסטר 2022ג
20476 / 4
מס' שאלון – 518
מס' מועד 82
שאלון בחינת גמר
מתמטיקה בדידה – 20476
משך בחינה: 3 שעות
מבנה הבחינה:
בבחינה שני חלקים:
חלק א: שאלת חובה. את התשובה לכל סעיף כתבו במחברת בלבד.
חלק ב: עליכם לענות על שלוש מתוך ארבע השאלות.
אם תענו על יותר מ-3 שאלות, יחושב הציון לפי 3 התשובות הראשונות.
שימו לב:
* בחלק ב יש לנמק כל תשובה, גם אם זה לא נדרש בפירוש בגוף השאלה.
* מותר להסתמך על כל טענה המופיעה בספרי הלימוד של הקורס, כולל התשובות לשאלות שבספרי הלימוד, וכולל החוברת "אוסף תרגילים פתורים". אפשר להסתמך גם על הפתרונות שפורסמו למטלות של הסמסטר הנוכחי.
* אם ברצונכם להסתמך על טענות ממפגשי הנחיה, כולל מפגשי אופק, עליכם לחזור ולהוכיחן.
* בפתרון סעיף של שאלה מותר להסתמך על סעיפים קודמים של אותה שאלה, גם אם לא פתרתם אותם.
חומר עזר:
כל חומר עזר מותר בשימוש. אפשר להשתמש במחשבון מדעי.
אסור בשימוש כל מכשיר אלקטרוני שבאמצעותו ניתן לאצור מידע לרבות מכשיר טלפון נייד, מחשב נישא, שעון חכם וכד'.
אינכם חייבים להחזיר את השאלון לאוניברסיטה הפתוחה
בהצלחה !!!
חלק א: שאלת חובה (19 נקודות)
שאלה 1
בחרו את התשובה הנכונה בכל סעיף. רשמו את התשובות בתוך המחברת.
בשאלה זו בלבד אין צורך בהוכחה. אפשר (לא חובה) לתת הסבר קצר: כמה מלים, לא יותר משתי שורות. ההסבר עשוי לאפשר לבודק לתת לכם נקודה או שתים גם אם בחרתם תשובה לא נכונה. מצד שני, הסבר שגוי בצורה קיצונית עלול להביא להורדה של נקודה או שתים.
(6 נק') א. להלן \(a,b\) מסמנים אברים בקבוצה \(A\) ו-\(f\) מסמן פונקציה שתחום ההגדרה שלה הוא \(A\). אז, את הפסוק "\(f\) היא לא חד-חד-ערכית" ניתן להצרין כך:
[1] \(\neg\forall a\forall b\bigl((a = b) \lor (f(a) \neq f(b))\bigr)\)
[2] \(\forall a\exists b\bigl((a \neq b) \land (f(a) = f(b))\bigr)\)
[3] \(\forall a\forall b\bigl((a \neq b) \rightarrow (f(a) = f(b))\bigr)\)
[4] כל הטענות הקודמות שגויות.
(7 נק') ב. נתונה סדרת קבוצות \(\langle A_n \mid n \in \mathbf{N}\rangle\), כך ש-\(\bigcup\limits_{n\in\mathbf{N}} A_n = \mathbf{N}\). אז:
[1] \(\left|\bigcup\limits_{n\in\mathbf{N}} \mathcal{P}(A_n)\right| = \aleph\)
[2] \(\left|\bigcup\limits_{n\in\mathbf{N}} \mathcal{P}(A_n)\right| = \aleph_0\)
[3] קיים \(k \in \mathbf{N}\) כך ש-\(|A_n| < \aleph_0\)
[4] כל הטענות הקודמות שגויות
(6 נק') ג. בשאלה זו \(T\) הוא עץ מתוייג על 8 צמתים שבו יש צומת \(v\) בעל דרגה 4 וצומת \(w\) בעל דרגה 3. אז:
[1] הצמתים \(v\) ו-\(w\) הם סמוכים זה לזה.
[2] \(v\) ו-\(w\) הם כל הצמתים שאינם עלים.
[3] מספר העלים ב-\(T\) גדול ב-2 ממספר הצמתים האחרים שלו.
[4] כל הטענות הקודמות שגויות
חלק ב: ענו על שלוש מתוך ארבע השאלות הבאות
משקל כל שאלה 27 נקודות. משקל חלק ב' כולו: 81 נקודות
שאלה 2
נתונה \(A = \{\langle x,y\rangle \mid x,y \in \{0,1,2,3\}\}\). על הקבוצה \(A\) מגדירים יחסים \(R,S\) כך:
לכל \(\langle x_1,y_1\rangle, \langle x_2,y_2\rangle \in A\), \(\langle x_1,y_1\rangle R \langle x_2,y_2\rangle\) אם ורק אם \(x_1 + x_2\) זוגי וגם \(y_1 + y_2\) זוגי.
לכל \(\langle x_1,y_1\rangle, \langle x_2,y_2\rangle \in A\), \(\langle x_1,y_1\rangle S \langle x_2,y_2\rangle\) אם ורק אם \(x_1^2 + 2y_1^2 < x_2^2 + 2y_2^2\).
(13 נק') א. הראו ש-\(R\) הוא יחס שקילות ורשמו באופן מפורט את מחלקות השקילות שלו.
(14 נק') ב. הראו ש-\(S\) הוא יחס סדר, מצאו בו את האיברים המינימליים ואת האיברים המקסימליים והוכיחו שאינו סדר מלא.
שאלה 3
בשני סעיפי השאלה נתייחס למשוואה \(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 8\).
(14 נק') א. חשבו את מספר הפתרונות בטבעיים של המשוואה, שבהם המשתנים \(x_1, x_2, x_3, x_4, x_5\) הם זוגיים (אין הגבלות על ארבעת המשתנים הנותרים)
(13 נק') ב. חשבו את מספר הפתרונות בטבעיים של המשוואה, שבהם \(x_1, x_2, x_3, x_4, x_5\) זוגיים או \(x_5, x_6, x_7, x_8, x_9\) זוגיים. (הכוונה שלפחות אחד משני התנאים מתקיים)
שאלה 4
בשני סעיפי השאלה נתייחס למילים באורך 8 הכתובות באותיות \(A, A, B, B, C, C, D, D\). (כל אות מופיעה פעמיים).
(13 נק') א. מצאו את מספר המילים שבהן האות \(A\) מופיעה רק בחצי הראשון של המילה. (דוגמה למילה כזו: \(ABDACDBC\))
(14 נק') ב. מצאו את מספר המילים שבהן אין שתי אותיות זהות שסמוכות זו לזו.
שאלה 5
נתון גרף פשוט על 7 צמתים \(G = (V,E)\).
ידוע שהמשלים שלו \(\overline{G} = (V,\overline{E})\) (ראו הגדרה 1.4 בספר) הוא גרף קשיר.
(12 נק') א. הוכיחו שאם \(G\) אוילרי אז גם \(\overline{G}\) אוילרי.
(15 נק') ב. הוכיחו שאם \(G\) גרף מישורי בעל 8 פאות אז גם \(\overline{G}\) מישורי, וחשבו את מספר הפאות שלו (רמז: חשבו תחילה את מספר הקשתות של \(\overline{G}\))
בהצלחה!
