האוניברסיטה הפתוחה
י"ד בכסלו תשפ"ב, 18 בנובמבר 2021
סמסטר 2021ג
מס' שאלון: 487
מס' מועד: 91
20476 / 4
שאלון בחינת גמר
20476 – מתמטיקה בדידה
משך בחינה: 3 שעות
מבנה הבחינה:
בבחינה שני חלקים:
חלק א: שאלת חובה. את התשובה לכל סעיף כתבו במחברת בלבד.
חלק ב: עליכם לענות על שלוש מתוך ארבע השאלות.
אם תענו על יותר מ-3 שאלות, יחושב הציון לפי 3 התשובות הראשונות.
שימו לב:
* בחלק ב יש לנמק כל תשובה, גם אם זה לא נדרש בפירוש בגוף השאלה.
* מותר להסתמך על כל טענה המופיעה בספרי הלימוד של הקורס, כולל התשובות לשאלות שבספרי הלימוד, וכולל החוברת "אוסף תרגילים פתורים". אפשר להסתמך גם על הפתרונות שפורסמו למטלות של הסמסטר הנוכחי.
* אם ברצונכם להסתמך על טענות ממפגשי הנחיה, כולל מפגשי אופק, עליכם לחזור ולהוכיחן.
* בפתרון סעיף של שאלה מותר להסתמך על סעיפים קודמים של אותה שאלה, גם אם לא פתרתם אותם.
חומר עזר:
כל חומר עזר מותר בשימוש. אפשר להשתמש במחשבון מדעי.
אסור בשימוש כל מכשיר אלקטרוני שבאמצעותו ניתן לאצור מידע לרבות מכשיר טלפון נייד, מחשב נישא, שעון חכם וכד'.
בהצלחה !!!
אינכם חייבים להחזיר את השאלון לאוניברסיטה הפתוחה
חלק א': שאלת חובה (19 נקודות)
שאלה 1
בחרו את התשובה הנכונה בכל סעיף. רשמו את התשובות בתוך המחברת.
בשאלה זו בלבד אין צורך בהוכחה. אפשר (לא חובה) לתת הסבר קצר: כמה מלים, לא יותר משתי שורות. הסבר עשוי לאפשר לבודק לתת לכם נקודה או שתים גם אם בחרתם תשובה לא נכונה. מצד שני, הסבר שגוי בצורה קיצונית עלול להביא להורדה של נקודה או שתים.
א. (6 נק') נתונים פסוקים \( p, q \). ידוע ש-\( p \rightarrow q \) גורר טאוטולוגית את \( q \). אז:
[1] \( p \rightarrow q \) גורר טאוטולוגית את \( p \).
[2] \( p \vee q \) טאוטולוגיה.
[3] \( p \) גורר טאוטולוגית את \( q \).
[4] אף אחת מהתשובות הקודמות אינה נכונה.
ב. (7 נק') \( \mathbf{R} \) היא קבוצת המספרים הממשיים, \( \mathbf{N} \) היא קבוצת המספרים הטבעיים, \( \mathbf{Q} \) היא קבוצת המספרים הרציונליים.
אם \( A \subseteq \mathbf{R} \) ואם לכל \( n \in \mathbf{N} \) חיובי מתקיים \( |A \cap (-n,n)| = \aleph_0 \) אז:
[1] \( |A \cap (0,1)| = \aleph_0 \)
[2] \( |A| = \aleph_0 \)
[3] \( |A| = \aleph \)
[4] \( |A \cap \mathbf{Q}| \neq \varnothing \)
ג. (6 נק') גרף פשוט \( G \) על 6 צמתים התקבל ממעגל \( C \) בעל 4 צמתים, על-ידי הוספת שני צמתים חדשים וחיבורם בקשתות לכל אחד מצומתי \( C \). לא הוסיפו עוד קשתות.
אז:
[1] קיים ב-\( G \) מסלול אוילר שאינו מעגל.
[2] \( G \) הוא המילטוני.
[3] \( G \) הוא לא מישורי.
[4] \( G \) הוא דו-צדדי.
חלק ב': ענו על שלוש מתוך ארבע השאלות הבאות
משקל כל שאלה 27 נקודות. משקל חלק ב' כולו: 81 נקודות
שאלה 2
על הקבוצה \( A = \{ \langle a,b \rangle \mid a,b \in \{1,2,4\} \} \) מגדירים שני יחסים \( R, S \) כך:
לכל \( \langle a_1,b_1 \rangle, \langle a_2,b_2 \rangle \in A \), \( \langle a_1,b_1 \rangle R \langle a_2,b_2 \rangle \) אם ורק אם \( a_1 b_2 = a_2 b_1 \) ו-\( \langle a_1,b_1 \rangle S \langle a_2,b_2 \rangle \) אם ורק אם \( a_1 b_2 < a_2 b_1 \).
א. (13 נק') הראו ש-\( R \) הוא יחס שקילות ורשמו באופן מפורט את מחלקות השקילות שלו.
ב. (14 נק') הראו ש-\( S \) הוא יחס סדר. קבעו אם הוא סדר חלקי או מלא ומיצאו בו את כל האיברים המינימליים והמקסימליים.
שאלה 3
בסל יש 2 כדורים מסוג \( A \), 2 כדורים מסוג \( B \), 3 כדורים מסוג \( C \) ו-3 כדורים מסוג \( D \). כדורים מאותו סוג הם זהים.
א. (14 נק') חשבו את מספר האפשרויות לבחירת 5 כדורים מתוך הסל, כאשר אין חשיבות לסדר הכדורים.
ב. (13 נק') חשבו את מספר האפשרויות לבחור 9 כדורים מתוך הסל ולסדר אותם בשורה.
שאלה 4
תהי \( A \) קבוצת כל המחרוזות שבהן מופיעות הספרות 1,2,4 בלבד. נסמן:
\( a_n \) מספר המחרוזות ב-\( A \) שהן באורך \( n \) וסכום הספרות שלהן זוגי.
\( b_n \) מספר המחרוזות ב-\( A \) שהן באורך \( n \) וסכום הספרות שלהן אי-זוגי.
למשל את המחרוזת 211 סופרים כשמחשבים את \( a_3 \) ואת המחרוזת 2142 סופרים ב-\( b_4 \).
א. (9 נק') עבור כל \( n \geq 2 \) הביעו את \( a_n \) בעזרת \( a_{n-1} \) ו-\( b_{n-1} \) וגם את \( b_n \) בעזרת \( a_{n-1} \) ו-\( b_{n-1} \).
ב. (9 נק') מיצאו נוסחת נסיגה עבור \( a_n \).
הדרכה: השוויון הראשון מסעיף א' מאפשר להביע את \( b_{n-1} \) בעזרת \( a_n \) ו-\( a_{n-1} \) ולכן גם את \( b_n \) בעזרת \( a_{n+1} \) ו-\( a_n \). הציבו אותם במקום \( b_{n-1} \) ו-\( b_n \) בשוויון השני מסעיף א')
ג. (9 נק') חשבו את \( a_1 \) ואת \( a_2 \) ומיצאו נוסחה כללית ל-\( a_n \).
שאלה 5
\( G \) הוא גרף על 8 צמתים שבו הדרגה של כל צומת היא 3. לאחר מחיקת כמה קשתות ב-\( G \) התקבל עץ \( T \) על 8 צמתים שבו הדרגה של כל צומת היא מספר אי-זוגי.
א. (9 נק') חשבו את מספר הקשתות שנמחקו ב-\( G \).
ב. (9 נק') חשבו את מספר העלים של \( T \).
ג. (9 נק') האם כל העצים \( T \) שמתאימים לנתוני השאלה הם איזומורפיים? נמקו את התשובה. (שימו לב, לא מדובר כאן על עצים מתוייגים)
בהצלחה!
