האוניברסיטה הפתוחה · קורס 20476
פתרון מבחן — מתמטיקה בדידה
- סמסטר2024ב
- מועד א1
- בינוני
נושאים:שקילות פסוקים · עוצמות · עצים מתויגים · יחס שקילות · הכלה והדחה · יחסי נסיגה · מישוריות · גרף אוילרי · מסלול המילטון
5שאלות
מצב סימולציה: פתרו כל שאלה בעצמכם, חשפו את התשובה, וסמנו אם צדקתם. ההתקדמות נשמרת במכשיר שלכם.
0/5 נבדקו
שאלה 1
4/5סעיף א (6 נק'): נתון ש- קבוצות. נתייחס לפסוק . נניח כי ההקשר הוא קבוצה ש- וכל איבריהן שייכים אליה. להלן מדובר על שקילות בין פסוקים במובן הבא: פסוק נתון הוא שקול לפסוק אחר אם יש להם אותו ערך אמת.[1] מהנתונים נובע כי שקול ל-;[2] מהנתונים נובע כי שקול ל-;[3] מהנתונים נובע כי שקול ל-;[4] אף אחת מהטענות [1]–[4] אינה נכונה.
סעיף ב (7 נק'): תהי . נתון כי לכל מתקיים . כמו כן, נתון כי אף מספר רציונלי אינו שייך לאינסוף מאיברי (במלים אחרות: לכל מתקיים ).[1] מהנתון נובע כי ;[2] מהנתון נובע כי ;[3] מהנתון נובע כי ;[4] אף אחת מהטענות [1]–[3] אינה נכונה.
סעיף ג (6 נק'): בשאלה זו נתייחס לעצים מתויגים המקיימים את התנאים הבאים: (i) מספר הצמתים של הוא , ותגי הצמתים ב- הם . (ii) יש גרף אוילרי שמתקבל מ- על-ידי הוספת קשת יחידה בין שני עלים (שונים זה מזה) של . מספר העצים המתויגים המקיימים את התנאים (i) ו-(ii), כאשר עצים מתויגים איזומורפיים נחשבים זהים, הוא:[1] ;[2] ;[3] ;[4] שונה מהמספרים [1]–[3] (כלומר: אף אחת מהתשובות [1]–[3] אינה נכונה).
שאלה 2
4/5סעיף א (14 נקודות): הוכיחו כי הוא יחס שקילות על .
סעיף ב (13 נקודות): תהי קבוצת כל מחלקות השקילות של . האם סופית? הוכיחו את תשובתכם. תוכלו להסתמך בתשובתכם על הטענה הבאה מבלי לנמק אותה: לכל זוג קבוצות סופיות , הקבוצה היא סופית.
שאלה 3
4/5סעיף א (13 נק'): מהו מספר הפיזורים האפשריים של הכדורים בתאים? תנו תשובה מספרית. נמקו.
סעיף ב (14 נק'): בכמה מהפיזורים האפשריים אין אף תא שבו כדור לבן יחיד וכדור שחור יחיד? (במלים אחרות: בכמה מהפיזורים האפשריים אין אף תא, שמספר הכדורים הלבנים הנמצאים בו הוא , ומס' הכדורים השחורים הנמצאים בו הוא ?) תנו תשובה מספרית. נמקו. שימו לב: התנאי הנתון בסעיף ב' אינו מגביל את מספר הכדורים האדומים באף אחד מהתאים.
שאלה 4
4/5סעיף א (7 נק'): מצאו על-ידי חישוב ישיר את .
סעיף ב (7 נק'): מצאו יחס נסיגה עבור . בדקו האם הערכים של מתאימים ליחס הנסיגה שמצאתם.
סעיף ג (13 נק'): פתרו את יחס הנסיגה שמצאתם, וקבלו נוסחה מפורשת עבור .
שאלה 5
4/5סעיף א (9 נק'): הוכיחו כי (הגרף המשלים של ) אינו מישורי. תוכלו להשתמש כאן בטענה הבאה מבלי לנמק אותה: כל תת-גרף של גרף מישורי הוא בעצמו גרף מישורי.
סעיף ב (9 נק'): הוכיחו כי, אם כל אחד מרכיבי הקשירות של הוא אוילרי (ליתר דיוק: אם כל אחד מתתי-הגרפים של המושרים על-ידי רכיבי הקשירות של הוא אוילרי), אז אוילרי.
סעיף ג (9 נק'): הוכיחו שיש ב- מסלול המילטון.