האוניברסיטה הפתוחה
ג' בניסן תשפ"ב, 4 באפריל 2022
סמסטר 2022א
מס' שאלון: 488
מס' מועד: 96
שאלון בחינת גמר
20476 – מתמטיקה בדידה
משך בחינה: 3 שעות
מבנה הבחינה:
בבחינה שני חלקים:
חלק א: שאלת חובה. את התשובה לכל סעיף כתבו במחברת בלבד.
חלק ב: עליכם לענות על שלוש מתוך ארבע השאלות.
אם תענו על יותר מ-3 שאלות, יחושב הציון לפי 3 התשובות הראשונות.
שימו לב:
* בחלק ב יש לנמק כל תשובה, גם אם זה לא נדרש בפירוש בגוף השאלה.
* מותר להסתמך על כל טענה המופיעה בספרי הלימוד של הקורס, כולל התשובות לשאלות שבספרי הלימוד, וכולל החוברת "אוסף תרגילים פתורים". אפשר להסתמך גם על הפתרונות שפורסמו למטלות של הסמסטר הנוכחי.
* אם ברצונכם להסתמך על טענות ממפגשי הנחיה, כולל מפגשי אופק, עליכם לחזור ולהוכיחן.
* בפתרון סעיף של שאלה מותר להסתמך על סעיפים קודמים של אותה שאלה, גם אם לא פתרתם אותם.
חומר עזר:
כל חומר עזר מותר בשימוש. אפשר להשתמש במחשבון מדעי.
אסור בשימוש כל מכשיר אלקטרוני שבאמצעותו ניתן לאצור מידע לרבות מכשיר טלפון נייד, מחשב נישא, שעון חכם וכד'.
בהצלחה !!!
אינכם חייבים להחזיר את השאלון לאוניברסיטה הפתוחה
חלק א': שאלת חובה (19 נקודות)
שאלה 1
בחרו את התשובה הנכונה בכל סעיף. רשמו את התשובות בתוך המחברת.
בשאלה זו בלבד אין צורך בהוכחה. אפשר (לא חובה) לתת הסבר קצר: כמה מלים, לא יותר משתי שורות. הסבר עשוי לאפשר לבודק לתת לכם נקודה או שתים גם אם בחרתם תשובה לא נכונה. מצד שני, הסבר שגוי בצורה קיצונית עלול להביא להורדה של נקודה או שתים.
א. (6 נק')
נתונים פסוקים \( p,q \).
ידוע ש-\( p \to q \) אינו טאוטולוגיה וגם \( q \to p \) אינו טאוטולוגיה. אז:
[1] \( p \vee q \) לא טאוטולוגיה.
[2] \( p \vee q \) טאוטולוגיה.
[3] \( p \wedge q \) סתירה.
[4] \( (p \to q) \to (q \to p) \) טאוטולוגיה.
[5] כל הטענות הקודמות שגויות
ב. (7 נק')
יהיו \( A,B \) קבוצות אינסופיות של מספרים ממשיים. אז:
[1] \( |A| < |\mathcal{P}(B)| \).
[2] \( |A| < |\mathcal{P}(\mathcal{P}(B))| \).
[3] \( |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(B))| \).
[4] \( |A| < |A \times B| \).
[5] כל הטענות הקודמות שגויות.
ג. (6 נק')
\( T \) הוא עץ מתויג שבו לצומת בעל התג 2 יש דרגה 2, לצומת בעל התג 3 יש דרגה 3 ולצומת בעל התג 4 יש דרגה 4. כל שאר הצמתים ב-\( T \) הם עלים. אז:
[1] מספר העצים \( T \) האפשריים הוא 60.
[2] ל-\( T \) יש בדיוק 6 צמתים.
[3] ל-\( T \) יש 8 קשתות.
[4] כל הטענות הקודמות שגויות.
חלק ב': ענו על שלוש מתוך ארבע השאלות הבאות
משקל כל שאלה 27 נקודות. משקל חלק ב' כולו: 81 נקודות.
שאלה 2
נתונה \( A = \{ \langle x,y \rangle \mid x,y \in \mathbf{R} \setminus \{0\} \} \). על הקבוצה \( 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 > 0 \) וגם \( y_1 y_2 > 0 \).
ולכל \( \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 = x_2 \) וגם \( y_1 > y_2 \).
א. (14 נק') הראו ש-\( R \) הוא יחס שקילות, מיצאו את מספר מחלקות השקילות ורישמו נציג אחד מכל מחלקה.
ב. (13 נק') הראו ש-\( S \) הוא יחס סדר. קבעו אם הוא סדר חלקי או מלא (נמקו את התשובה) והוכיחו שאין בו איברים מינימליים או מקסימליים.
שאלה 3
בתוך 4 תאים שונים מפזרים 9 כדורים שעליהם רשומות הספרות \( 0,0,0,0,1,1,1,2,2 \). אין חשיבות לסדר הכדורים שבאותו תא. כדורים שעליהם רשומה אותה ספרה נחשבים זהים.
א. (13 נק') חשבו את מספר הפיזורים השונים.
ב. (14 נק') חשבו את מספר הפיזורים שבהם אף תא לא נשאר ריק.
שאלה 4
א. (9 נק') חשבו את המקדם של \( x^{19} \) בביטוי \( (1+x^3)^6 (1+x^4)^6 \).
ב. (9 נק') חשבו את מספר הפתרונות בטבעיים של המשוואה \( x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 19 \) כאשר הנעלמים \( x_1, x_2, x_3, x_4, x_5, x_6 \) יכולים לקבל רק את הערכים \( 0,3,4,7 \).
(רמז: נסו להיעזר בסעיף א')
ג. (9 נק') חשבו את מספר הפתרונות בטבעיים של המשוואה \( x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 19 \) שבהם קיים \( 1 \le i \le 6 \) כך ש-\( x_i \notin \{0,3,4,7\} \).
שאלה 5
נתון \( G = (V,E) \) גרף פשוט שבו \( V = \{1,2,3,4,5,6,7\} \) ו-\( E = \{ \{x,y\} \mid x,y \in V,\ x+y \le 9 \} \).
א. (9 נק') מיצאו את דרגות כל הצמתים בגרף \( G \) והוכיחו שיש בו מסלול אוילר שאינו מעגל.
ב. (9 נק') הוכיחו בעזרת משפט קורטובסקי ש-\( G \) אינו מישורי.
ג. (9 נק') הוכיחו ש-\( G \) אינו מקיים את משפט אור (משפט 3.2) אך יש בו מעגל המילטון.
בהצלחה!
