פתרון בחינה 8 old exams solutions for math exams available PDF

Preview

Summary

Download פתרון בחינה 8 old exams solutions for math exams available PDF

Description

‫פתרון בחינה ‪8‬‬ ‫שאלה ‪1‬‬ ‫מי שענה [‪ ]4‬יקבל קצת נקודות‪...‬‬

‫א‪.‬‬

‫[‪. ]5‬‬

‫ב‪.‬‬

‫הפונקציות ב‪ A -‬הן אלה שיכולות לקבל במקומות מהצורה ‪ ( n  N ( 4n  2‬כל ערך‬ ‫מתוך }‪{0,1‬באופן חופשי‪ .‬לכן ‪ A‬שקולה לקבוצה כל הפונקציות מ‪ N -‬ל‪.{0,1} -‬‬ ‫מכאן ש‪ | A |  |{0,1} N |  20   -‬והתשובה היא [‪.]3‬‬ ‫[‪ . ]2‬דרגת כל צומת היא ‪ ,5‬לכן מספר הקשתות ‪. 32  5 / 2  80‬‬

‫ג‪.‬‬ ‫שאלה ‪2‬‬ ‫א‪.‬‬

‫כן‪ (1,1) :‬‬

‫ב‪.‬‬

‫כן‪ (1,1),(2,2),(1, 2), (2,1),(3, 4) :‬‬

‫ג‪.‬‬

‫רפלקסיביות יחס רפלקסיבי מקיים ‪. R  R 2‬‬ ‫‪,‬‬ ‫לא ‪ :‬לפי טענה המופיעה יחד עם הגדרת‬

‫ד‪.‬‬

‫כן‪ .  (1, 2),(1,3),(1, 4),(2,3),(2,4) :‬זה יחס אנטי רפלקסיבי טרנזיטיבי שוב ‪ 1‬הוא קטן‬ ‫ביותר ו‪ 3,4 -‬איברים מקסימליים‪.‬‬

‫שאלה ‪3‬‬ ‫‪ 12 ‬‬ ‫נסמן ב‪ U -‬את קבוצת כל הפתרונות (ללא הגבלות)‪ .‬מספרם הוא‪  220 :‬‬ ‫‪3‬‬

‫‪. |U |  D (4,9)  ‬‬

‫נסמן‪ - A i :‬קבוצת הפתרונות בהם ‪ - B i , x i  5‬קבוצת הפתרונות בהם ‪ , x i  4‬עבור ‪. 1  i  4‬‬ ‫אז ‪ A1  A2  A3  A 4  B1 B 2 B 3 B 4‬היא קבוצת כל הפתרונות שבהם לפחות אחד‬ ‫המשתנים הוא ‪ 4‬או ‪ 5‬ולכן ) ‪ U  ( A1  A2  A3  A4  B1  B 2 B 3 B 4‬היא קבוצת‬ ‫פתרונות בהם אף משתנה לא שווה ל‪ 4 -‬או ל‪( 5 -‬שאנו מחפשים )‪.‬‬ ‫לחישוב | ‪ | A1  A2  A3  A4  B1  B2  B3  B 4‬בעזרת עקרון ההכלה וההפרדה עלינו לחשב‬ ‫את מספרי האיברים בכל החיתוכים האפשריים של קבוצות מן האיחוד הנ"ל‪.‬‬ ‫‪ 6‬‬

‫‪ , | Ai |  D (3, 4)     15‬יש ‪ 4‬כאלה‪.‬‬ ‫‪2‬‬ ‫‪ ‬‬

‫‪7‬‬

‫‪ , | Bi |  D (3,5)     21‬יש ‪ 4‬כאלה‪.‬‬ ‫‪2‬‬ ‫‪ ‬‬

‫נעבור כעת לחיתוכים של שתי קבוצות מתוך ‪ 8‬הקבוצות הנתונות‪:‬‬

‫‪ | Ai  A j |  ‬לכל ‪( i  j‬כי לא ייתכן ששני משתנים יהיו שווים ל‪5 -‬‬ ‫‪2 ‬‬

‫‪ | Bi  B j |  D (2,1)     2‬לכל ‪( i  j‬כלומר שני משתנים שווים ל‪ )4 -‬יש ‪ 6‬חיתוכים כאלה‪.‬‬ ‫‪1‬‬ ‫‪ ‬‬

‫‪( | Ai  B j |  1‬כאשר אחד המשתנים הוא ‪ 4‬ואחד הוא ‪ . ) 5‬יש ‪ 12‬חיתוכים כאלה‪..‬‬ ‫החיתוכים של כל ‪ 3‬קבוצות או יותר מתוך ‪8‬הקבוצות הנתונות הוא ריק‪ ,‬לכן התרומה שלהם‬ ‫בספירה היא ‪ . 0‬לכן מספר הפתרונות המבוקש הוא‪:‬‬ ‫‪| U |  | A1  A2  A3  A4  B1  B2 B3  B4 |  220  4  (15  21)  6  2  12 1  100‬‬

‫פתרון אחר‪ -‬בעזרת פונקציות יוצרות‬ ‫המשתנים יכולים לקבל כל ערך שלם בין ‪ 0‬ל‪ 9 -‬למעט ‪ 4‬ו‪ 5 -‬לכן הפונקציה היוצרת המתאימה‬ ‫לפתרון הבעיה היא ‪ f ( x)  (1  x  x 2  x 3  x 6  x 7  x 8  x 9 ) 4‬ועלינו למצוא את‬ ‫המקדם של ‪ x 9‬ב‪ . f ( x ) -‬לשם כך נשים לב ש‪-‬‬ ‫‪f ( x)  ((1  x  x 2  x 3 )  x 6 (1  x  x 2  x 3 ) 4 ‬‬ ‫‪4‬‬

‫‪4‬‬ ‫‪6 4 1  x ‬‬

‫‪2‬‬

‫‪3 4‬‬

‫‪6 4‬‬

‫‪ (1  x ) (1  x  x  x )  (1  x ) ‬‬ ‫‪‬‬ ‫‪ 1 x ‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪1‬‬ ‫‪(1  x) 4‬‬

‫‪ (1  x 6 ) 4 (1  x 4 ) 4‬‬

‫מאחר שאנו מתעניינים רק בחזקות של ‪ x‬שלא עוברות את ‪ x 9‬נרשום רק את מה שרלוואנטי‬ ‫בפיתוחי הבינומים‪ .‬נקבל‪:‬‬ ‫‪‬‬

‫‪ k  3 k ) ‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪k 0‬‬

‫‪f ( x )  (1  4 x 6 ‬‬ ‫‪‬‬

‫‪k 3 k‬‬ ‫) ‪x‬‬ ‫‪3 ‬‬ ‫‪k 0 ‬‬

‫‪ (1  4 x 4  4 x 6  6 x 8 ‬‬

‫המקדם של ‪ x 9‬הוא‪:‬‬ ‫‪9  3   5  3   3  3   1  3  ‬‬ ‫‪ 3  4  3  4  3  6  3  220  4  56  4  20  6  4  100‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫שאלה ‪4‬‬ ‫א‪.‬‬ ‫ב‪.‬‬

‫‪11 ‬‬ ‫‪ ‬‬ ‫‪4‬‬

‫נחשוב על ‪ 7‬הספרות שהן ‪ 0‬כמחיצות שיוצרות ‪ 8‬תאים שונים שבהם נושיב כעת את ‪4‬‬ ‫הספרות שהן ‪ 1‬כאשר בכל תא יש לכל היותר ספרה אחת שהיא ‪_ 0 _ 0_ 0 _ 0_ 0 _ 0 _ 0_ :1‬‬

‫בעצם כל מה שצריך זה לבחור באלו תאים מתוך ה‪ 8-‬נשים את הספרות וזה כמו לבחור ‪4‬‬ ‫‪8 ‬‬

‫תאים מתוך ה‪ .8 -‬לכן התשובה היא ‪.    70‬‬ ‫‪4‬‬ ‫‪ ‬‬

‫ג‪.‬‬

‫לכל קבוצה‬

‫‪ X  {1, 2,3‬מתאימה מחרוזת אחת ויחידה באורך ‪ 11‬שבנויה רק מן‬

‫הספרות ‪ 0‬ו‪ 1 -‬כאשר במקום ‪ i‬במחרוזת מופיע ‪ 1‬אם ‪ i  X‬ומופיע ‪ 0‬אם ‪i  X‬‬

‫(זו אותה הגדרה שבעזרתה מגדירים את הפונקציה האופיינית של קבוצה ‪) X‬‬ ‫לקבוצות‬

‫‪ X  {1, 2,3‬כך ש‪ X  4 -‬מתאימות כל המחרוזות באורך ‪ 11‬שבהן בדיוק‬

‫‪ 4‬הופעות של ‪( 1‬ו‪ 7 -‬בהופעות של ‪) 0‬‬ ‫התאני "אם ‪ i  X‬אז ‪( " i  1  X‬פירושו שאין בקבוצה ‪ X‬שני מספרים עוקבים) שקול‬ ‫לכך שבמחרוזת המתאימה לקבוצה ‪ X‬אין הופעות צמודות של ‪.1‬‬ ‫את מספר המחרוזות האלה ספרנו בסעיף הקודם‪ ,‬לכן גם התשובה בסעיף זה היא‪. 70‬‬ ‫שאלה ‪5‬‬ ‫דוגמא נגדית‪ :‬בגרף המלא ‪ K5‬כל הדרגות זוגיות‪ ,‬לכן יש מעגל אוילר‪.‬‬ ‫ברור שיש מעגל המילטון‪.‬‬ ‫אבל מעגל אוילר לא יכול להיות מעגל המילטון‪ ,‬כי מסלול באורך‪ 10‬לא יכול לעבור דרך כל צומת‬ ‫פעם אחת בלבד (או כי האורך של מעגל המילטון הוא ‪.) 5‬‬...