האוניברסיטה הפתוחה
י"ג באדר א' תשפ"ב, 14 בפברואר 2022
סמסטר 2022א
מס' שאלון: 488
מס' מועד: 87
שאלון בחינת גמר
20476 – מתמטיקה בדידה
משך בחינה: 3 שעות
מבנה הבחינה:
בבחינה שני חלקים:
חלק א: שאלת חובה. את התשובה לכל סעיף כתבו במחברת בלבד.
חלק ב: עליכם לענות על שלוש מתוך ארבע השאלות.
אם תענו על יותר מ-3 שאלות, יחושב הציון לפי 3 התשובות הראשונות.
שימו לב:
* בחלק ב יש לנמק כל תשובה, גם אם זה לא נדרש בפירוש בגוף השאלה.
* מותר להסתמך על כל טענה המופיעה בספרי הלימוד של הקורס, כולל התשובות לשאלות שבספרי הלימוד, וכולל החוברת "אוסף תרגילים פתורים". אפשר להסתמך גם על הפתרונות שפורסמו למטלות של הסמסטר הנוכחי.
* אם ברצונכם להסתמך על טענות ממפגשי הנחיה, כולל מפגשי אופק, עליכם לחזור ולהוכיחן.
* בפתרון סעיף של שאלה מותר להסתמך על סעיפים קודמים של אותה שאלה, גם אם לא פתרתם אותם.
חומר עזר:
כל חומר עזר מותר בשימוש. אפשר להשתמש במחשבון מדעי.
אסור בשימוש כל מכשיר אלקטרוני שבאמצעותו ניתן לאצור מידע לרבות מכשיר טלפון נייד, מחשב נישא, שעון חכם וכד'.
אינכם חייבים להחזיר את השאלון לאוניברסיטה הפתוחה.
בהצלחה !!!
חלק א': שאלת חובה (19 נקודות)
שאלה 1
בחרו את התשובה הנכונה בכל סעיף. רשמו את התשובות בתוך המחברת.
בשאלה זו בלבד אין צורך בהוכחה. אפשר (לא חובה) לתת הסבר קצר: כמה מלים, לא יותר משתי שורות. הסבר עשוי לאפשר לבודק לתת לכם נקודה או שתים גם אם בחרתם תשובה לא נכונה. מצד שני, הסבר שגוי בצורה קיצונית עלול להביא להורדה של נקודה או שתים.
(6 נק') א. נתונים פסוקים \( p,q \). אז
[1] \( p \rightarrow (p \wedge q) \equiv p \rightarrow (p \wedge \neg q) \).
[2] \( p \rightarrow (p \wedge q) \equiv p \rightarrow (\neg p \vee q) \).
[3] \( p \rightarrow (p \wedge q) \equiv p \rightarrow \neg (p \wedge q) \).
[4] כל הטענות הקודמות שגויות
(7 נק') ב. נתונות קבוצות \( A,B \) ופונקציה \( f : A \rightarrow B \) שהיא על ואינה חד-חד-ערכית.
[1] \( |A| > |B| \).
[2] \( |\mathcal{P}(A)| > |B| \).
[3] \( |A| > |\mathcal{P}(B)| \).
[4] \( |A| = |\mathcal{P}(B)| \).
(6 נק') ג. \( (1,2,3,3,2,4) \) היא סדרת פרופר של עץ מתוייג \( T_1 \), \( (1,2,3,3,2) \) היא סדרת פרופר של עץ מתוייג \( T_2 \). אז
[1] ל-\( T_1 \) ו-\( T_2 \) יש אותו מספר צמתים.
[2] ל-\( T_1 \) ו-\( T_2 \) יש אותו מספר עלים.
[3] ל-\( T_1 \) ו-\( T_2 \) יש אותו מספר צמתים שאינם עלים.
[4] כל הטענות הקודמות שגויות.
חלק ב': ענו על שלוש מתוך ארבע השאלות הבאות
משקל כל שאלה 27 נקודות. משקל חלק ב' כולו: 81 נקודות
שאלה 2
נתונה \( A = \{\, \langle x,y \rangle \mid x,y \in \{0,1,\sqrt{2},\sqrt{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^2 + y_1^2 = x_2^2 + y_2^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 + y_1^2 = x_2^2 + y_2^2 \) וגם \( x_1 < x_2 \).
(13 נק') א. הראו ש-\( R \) הוא יחס שקילות, ורישמו את כל מחלקות השקילות שלו.
(14 נק') ב. הראו ש-\( S \) הוא יחס סדר. קבעו אם הוא סדר חלקי או מלא (נמקו את התשובה) ומיצאו בו את האיברים המינימליים ואת האיברים המקסימליים.
שאלה 3
בסעיפים א' ו-ב' נתייחס לפתרונות בטבעיים של משוואה \( x_1 + x_2 + x_3 = 15 \).
(8 נק') א. חשבו את מספר הפתרונות של המשוואה כאשר \( x_1 \neq 2 \) ו-\( x_2 \neq 5 \).
(14 נק') ב. חשבו את מספר הפתרונות של המשוואה כאשר \( x_1 \notin \{2,5\} \) וגם \( x_2 \notin \{2,5\} \).
(5 נק') ג. מיצאו את המקדם של \( x^{15} \) בביטוי
\[ \left( \frac{1}{1-x} – x^2 – x^5 \right)^{2} \cdot \frac{1}{1-x} \]
שאלה 4
תהי \( A \) קבוצת כל המחרוזות שבהן מופיעות הספרות \( 1,2,3,4,5,6,7 \) בלבד. נסמן:
\( a_n \) מספר המחרוזות ב-\( A \) שהן באורך \( n \) ואין בהן שתי ספרות שונות מ-1 שסמוכות זו לזו. (למשל את 212 סופרים כשמחשבים את \( a_3 \) אך את 122 לא סופרים). נתון גם ש-\( a_0 = 1 \).
(9 נק') א. עבור כל \( n \geq 2 \) הביעו את \( a_n \) בעזרת \( a_{n-1} \) ו-\( a_{n-2} \) (נוסחת נסיגה).
(9 נק') ב. חשבו את \( a_1 \) ואת \( a_2 \) ובדקו את נכונות הנוסחה שמצאתם בסעיף א' עבור \( n = 2 \).
(9 נק') ג. מיצאו נוסחה כללית עבור \( a_n \).
שאלה 5
בגרף פשוט וקשיר \( G \) על \( m + n + 5 \) צמתים יש 5 צמתים בעלי דרגות \( 4,4,4,3,3 \), \( n \) צמתים בעלי דרגה 2 ו-\( m \) צמתים בעלי דרגה 1.
(9 נק') א. הוכיחו שהמספר \( m \) הוא זוגי וחשבו את מספר הקשתות של \( G \).
(9 נק') ב. הוכיחו ש-\( G \) הוא גרף מישורי ושמספר הפאות שלו אינו תלוי במספר הצמתים בעלי דרגה 2.
(9 נק') ג. כמה עלים יהיו ב-\( G \) במקרה שהוא עץ? נמקו את התשובה.
בהצלחה!
