האוניברסיטה הפתוחה
מספר התלמיד הנבחן – רשום את כל תשע הספרות
י"ז בסיון תשפ"ב
סמסטר 2022ב
20476 / 4
מס' שאלון – 492
מס' מועד 82
16 ביוני 2022
שאלון בחינת גמר
20476 – מתמטיקה בדידה
משך בחינה: 3 שעות
מבנה הבחינה:
בבחינה שני חלקים:
חלק א: שאלת חובה. את התשובה לכל סעיף כתבו במחברת בלבד.
חלק ב: עליכם לענות על שלוש מתוך ארבע השאלות.
אם תענו על יותר מ-3 שאלות, יחושב הציון לפי 3 התשובות הראשונות.
שימו לב:
* בחלק ב יש לנמק כל תשובה, גם אם זה לא נדרש בפירוש בגוף השאלה.
* מותר להסתמך על כל טענה המופיעה בספרי הלימוד של הקורס, כולל התשובות לשאלות שבספרי הלימוד, וכולל החוברת "אוסף תרגילים פתורים". אפשר להסתמך גם על הפתרונות שפורסמו למטלות של הסמסטר הנוכחי.
* אם ברצונכם להסתמך על טענות ממפגשי הנחיה, כולל מפגשי אופק, עליכם לחזור ולהוכיחן.
* בפתרון סעיף של שאלה מותר להסתמך על סעיפים קודמים של אותה שאלה, גם אם לא פתרתם אותם.
חומר עזר:
כל חומר עזר מותר בשימוש. אפשר להשתמש במחשבון מדעי.
אסור בשימוש כל מכשיר אלקטרוני שבאמצעותו ניתן לאצור מידע לרבות מכשיר טלפון נייד, מחשב נישא, שעון חכם וכד'.
אינכם חייבים להחזיר את השאלון לאוניברסיטה הפתוחה
בהצלחה !!!
חלק א': שאלת חובה (19 נקודות)
שאלה 1
בחרו את התשובה הנכונה בכל סעיף. רשמו את התשובות בתוך המחברת.
בשאלה זו בלבד אין צורך בהוכחה. אפשר (לא חובה) לתת הסבר קצר: כמה מלים, לא יותר משתי שורות. הסבר עשוי לאפשר לבודק לתת לכם נקודה או שתים גם אם בחרתם תשובה לא נכונה. מצד שני, הסבר שגוי בצורה קיצונית עלול להביא להורדה של נקודה או שתים.
א. (6 נק') להלן האותיות \(a,b,c\) מסמנות מספרים ממשיים. את הפסוק "אם \(ac = bc\) ואם \(c\) שונה מ-0 אז \(a = b\)" ניתן להצרין כך:
[1] \(\forall a \forall b \forall c ((ac \neq bc) \vee (a = b) \vee (c = 0))\)
[2] \(\forall a \forall b \forall c ((ac \neq bc) \rightarrow ((a \neq b) \vee (c \neq 0)))\)
[3] \(\forall a \forall b \forall c ((ac = bc) \wedge (c \neq 0) \wedge (a = b))\)
[4] כל הטענות הקודמות שגויות.
ב. (7 נק') נתונות קבוצות לא ריקות \(A,B\) כך ש-\(|A \times \mathcal{P}(B)| = \aleph_0\). אז
[1] \(A\) יכולה להיות קבוצה סופית.
[2] \(|\mathcal{P}(B)| \geq |A|\).
[3] \(|B| = |A|\)
[4] \(|A^B| = |A|\)
[5] כל הטענות הקודמות שגויות.
ג. (6 נק') \(T\) הוא עץ מתוייג על 6 צמתים שבו דרגות הצמתים המתוייגים ב-1,2,3 הן 1,2,3 בהתאמה. אז מספר העצים המקיימים את תנאי השאלה הוא:
[1] 36
[2] 12
[3] 6
[4] כל הטענות הקודמות שגויות.
חלק ב': ענו על שלוש מתוך ארבע השאלות הבאות
משקל כל שאלה 27 נקודות. משקל חלק ב' כולו: 81 נקודות
שאלה 2
נתונה \(A = \{\langle x,y \rangle \mid x,y \in \{0,1,2,4\}\}\). על הקבוצה \(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 y_1 = x_2 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 y_1 = x_2 y_2\) וגם \(y_1 < y_2\).
א. (13 נק') הוכיחו ש-\(R\) הוא יחס שקילות ורשמו את האיברים בכל אחת ממחלקות השקילות.
ב. (14 נק') הוכיחו ש-\(S\) הוא יחס סדר. קבעו אם הוא סדר חלקי או מלא (נמקו את התשובה) ומצאו את האיברים המינימליים והמקסימליים.
שאלה 3
בשני סעיפי השאלה נתייחס לפתרונות בטבעיים של המשוואה:
\[ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 30 \]
כאשר \(x_1\), \(x_2\) ו-\(x_3\) הם מספרים אי-זוגיים המתחלקים ב-3 ו-\(x_4, x_5, x_6 \leq 5\).
א. (13 נק') רישמו פונקציה יוצרת שמתאימה לחישוב מספר הפתרונות המשוואה.
ב. (14 נק') מיצאו את מספר פתרונות המשוואה.
שאלה 4
נסמן ב-\(a_n\) את מספר המחרוזות באורך \(n\), שאיבריהן הם הספרות \(1,2,3,4\), שבהן מימין לספרה 1 מופיעה תמיד הספרה 2 ומימין לספרה 3 מופיעה תמיד הספרה 4. \(a_0\) מוגדר כ-1.
לדוגמה: המחרוזות 2, 4, 12, 42, 344 הן חוקיות, המחרוזות 3, 21, 334, 23414 הן לא חוקיות.
א. (7 נק') מיצאו בעזרת חישוב ישיר את \(a_1, a_2\).
ב. (7 נק') מיצאו יחס נסיגה ל-\(a_n\) ובדקו שהערכים של \(a_0, a_1, a_2\) מתאימים ליחס הנסיגה.
ג. (13 נק') פתרו את יחס הנסיגה וקבלו נוסחה מפורשת ל-\(a_n\).
שאלה 5
נתון גרף פשוט \(G = (V,E)\) שבו \(V = \{1,2,3,4,5,6,7\}\) ובין כל שני צמתים \(a,b \in V\) קיימת קשת ב-\(E\) אם ורק אם \(|a – b| \geq 3\).
(שימו לב: לכל מספר \(x\), \(|x|\) מסמן את הערך המוחלט של \(x\))
א. (9 נק') מיצאו את דרגות כל הצמתים ב-\(G\) והראו שיש בו מסלול אוילר שאינו מעגל.
ב. (9 נק') הוכיחו ש-\(G\) הוא גרף מישורי ומיצאו את מספר הפאות שלו.
ג. (9 נק') הוכיחו ש-\(G\) אינו גרף דו-צדדי.
בהצלחה!
