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