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

Preview

Summary

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

Description

‫פתרון בחינה ‪7‬‬

‫שאלה ‪1‬‬ ‫א‪[5] .‬‬ ‫ב‪ .‬עלינו למצוא את העוצמה של )‪. P(R ) P( N‬‬ ‫מתקיים‪ . | P (R )P (N ) |= | P (R ) ||P (N )| = (2|R | )|R | = 2ℵ⋅ℵ = 2ℵ :‬לכל התשובה היא ]‪[3‬‬ ‫ג‪[2] .‬‬ ‫שאלה ‪2‬‬ ‫א‪ .‬יהי ‪ . x ∈ A‬עלינו להראות שיש לו מקור‪ .‬נסמן )‪. y = f ( x‬‬ ‫בשל הנתון ‪ f ( f ( x)) = x‬מתקיים ‪. f ( y ) = x‬‬ ‫מצאנו אבר ב‪) A -‬האבר )‪ ( y = f ( x‬שתמונתו היא ‪. x‬‬ ‫ב‪ .‬יהיו ‪ x1 , x 2 ∈ A‬כך שמתקיים ) ‪. f ( x1 ) = f ( x 2‬‬ ‫נפעיל את ‪ f‬בשני האגפים ונקבל )) ‪. f ( f ( x1 )) = f ( f ( x 2‬‬ ‫מהנתון ‪ , f ( f ( x)) = x‬קיבלנו ‪. x1 = x 2‬‬ ‫ג‪ .‬לפי הנתון‪ ,‬לכל ‪ , x , y ∈ A‬כדי שיתקיים ‪ xEy‬מספיק שיתקיים לפחות אחד מבין שני‬ ‫התנאים‪ x = y :‬או ‪. f ( x) = y‬‬ ‫לכן לכל ‪ x ∈ A‬מתקיים ‪) xEx‬מפני ש‪ ( x = x -‬ולכן היחס רפלקסיבי‪.‬‬ ‫נניח כעת ש‪ . xEy -‬לפי הגדרת היחס ‪ E‬קיימות שתי אפשרויות‪:‬‬ ‫‪ x = y .1‬ואז ברור שמתקיים גם ‪. yEx‬‬ ‫‪ f ( x) = y .2‬ואז )‪ . f ( f ( x)) = f ( y‬אבל ‪ . f ( f ( x)) = x‬לכן ‪ f ( y ) = x‬ולכן ‪. yEx‬‬ ‫מכאן שלכל ‪ x , y ∈ A‬אם ‪ xEy‬אז ‪ yEx‬לכן ‪ E‬סימטרי‬ ‫וכעת נניח ש‪ xEy -‬ו‪. yEz -‬‬ ‫‪ .1‬אם ‪ x = y‬או ‪ y = z‬אז ברור שמתקיים ‪. xEz‬‬ ‫‪ .2‬אם ‪ x, y , z‬שונים זה מזה אז לפי הגדרת ‪ E‬חייב להתקיים ‪ f ( x) = y‬ו‪ f ( y ) = z -‬לכן‬ ‫‪ f ( f ( x)) = f ( y) = z‬ומאחר ש‪ f ( f ( x)) = x -‬נקבל ש‪ x = z -‬ולכן ‪. xEz‬‬ ‫כך קיבלנו שלכל ‪ , x , y , z ∈ E‬אם ‪ xEy‬ו‪ yEz -‬אז ‪ xEz‬לכן ‪ E‬טרנזיטיבי‪.‬‬ ‫לכן ‪ E‬יחס שקילות‪.‬‬

‫‪1‬‬

‫שאלה ‪3‬‬ ‫א‪.‬‬

‫לכל קבוצה ‪ X‬המקיימת ‪ {1, 2,3} ⊆ X ⊆ A‬יש הצגה יחידה מהצורה ‪X = {1, 2,3} ∪ Y‬‬

‫כאשר }‪ . Y ⊆ {4,  , n + 3‬לכן מספר הקבוצות ‪ X‬המקיימות ‪ {1, 2,3} ⊆ X ⊆ A‬שווה‬ ‫למספר הקבוצות ‪ Y‬שחלקיות ל‪{4,  , n + 3} -‬ולכן שווה ל‪) 2 n -‬שכן ‪.( |{4,  , n + 3}| = n‬‬ ‫ב‪.‬‬

‫לכל }‪ i ∈ {1, 2,3‬נסמן ב‪ S i -‬את קבוצת הקבוצות החלקיות ל‪ A = {1, 2,3,  , n + 3} -‬שאינן‬ ‫מכילות את הספר ‪ . i‬אז ‪ S 1 ∪ S 2 ∪ S 3‬היא קבוצת הקבוצות החלקיות ל‪ A -‬שאינן‬ ‫מכילות לפחות אחד מהמספרים ‪ 1,2,3‬ולכן )‪ P ( A) \ ( S 1 ∪ S 2 ∪ S 3‬היא קבוצת הקבוצות‬ ‫שמכילות את }‪ {1, 2,3‬שאת מספרן אנו רוצים לחשב‪.‬‬ ‫מאחר ש‪ | P( A) | = 2 n + 3 -‬ולכל שני מספרים שונים }‪ i, j ∈ {1,2,3‬מתקיים ‪ | S i | = 2 n +2‬ו‪-‬‬ ‫‪ | S i ∩ S j | = 2 n +1‬ובנוסף ‪ ,| S1 ∩ S2 ∩ S3 | = 2 n‬נקבל מעקרון ההכלה וההפרדה‬ ‫שמספר הקבוצות ‪ X‬המקיימות ‪ {1, 2,3} ⊆ X ⊆ A‬הוא‪:‬‬ ‫‪3‬‬ ‫‪3‬‬ ‫‪3‬‬ ‫‪,| P( A) |− | S 1 ∪ S 2 ∪ S 3 | = 2 n +3 −   ⋅ 2 n +2 +   ⋅ 2 n +1 −   ⋅ 2 n‬‬ ‫‪ 3‬‬

‫ג‪.‬‬

‫‪ 2‬‬

‫‪1 ‬‬

‫המספר שקיבלנו בסעיף ב' הוא‪:‬‬ ‫‪2 n + 3 − 3 ⋅ 2 n + 2 + 3 ⋅ 2 n +1 − 2 n = 2 n (2 3 − 3 ⋅ 2 2 + 3 ⋅ 2 1 − 1) = 2 n‬‬

‫שאלה ‪4‬‬ ‫א ‪ .‬מספר הפתרונות בטבעיים של המשוואה ‪ x 1 + x 2 + x 3 = 12‬שווה למספר הפיזורים של ‪12‬‬ ‫עצמים זהים ב‪ 3 -‬תאים שונים ולכן שווה ל‪. D(3,12) -‬‬ ‫ב ‪ .‬כל פתרון ) ‪ ( x 1, x 2, x 3, x 4 , x 5, x 6‬של המשוואה ‪ x1 + x 2 + x 3 + x 4 + x5 + x 6 = 24‬מקיים‬ ‫בדיוק אחד משלושת התנאים הבאים‪:‬‬ ‫‪x 1 + x 2 + x 3 > x 4 + x 5 + x 6 .1‬‬ ‫‪x 4 + x 5 + x 6 > x1 + x 2 + x3 .2‬‬ ‫‪x 1 + x 2 + x 3 = x 4 + x 5 + x 6 .3‬‬

‫אנו רוצים לספור את מספר הפתרונות המקיים את תנאי )‪ .(1‬נסמן אותו ב‪. x -‬‬ ‫נשים לב שמספר הפתרונות המקיימים את תנאי )‪ (2‬שווה למספר הפתרונות המקיימים את‬ ‫תנאי )‪ ) (1‬כי זה אותו אי‪-‬שוויון עם שמות אחרים לנעלמים(‪.‬‬ ‫כל פתרון ) ‪ ( x 1, x 2 , x 3, x 4 , x 5, x 6‬המקיים תנאי )‪ (3‬הוא בעצם פתרון של המערכת‬ ‫‪ x1 + x 2 + x 3 = 12‬‬ ‫‪ x 4 + x 5 + x 6 = 12‬‬

‫‪.‬‬

‫‪2‬‬

‫עבור שלושת המקומות הראשונים )‪ ( x 1, x 2, x 3‬יש )‪ D(3,12‬אפשרויות )כמספר פתרונות‬ ‫המשוואה ‪. ( x 1 + x 2 + x 3 = 12‬‬ ‫גם עבור שלושת המקומות האחרונים ) ‪ ( x 4 , x 5 , x 6‬יש )‪ D(3,12‬אפשרויות )כמספר פתרונות‬ ‫המשוואה ‪. ( x 4 + x 5 + x 6 = 12‬‬ ‫לכן מספר הפתרונות המקיימים תנאי )‪ (3‬הוא ‪. D (3,12) 2‬‬ ‫מספר הפתרונות המקיימים אחד משלושת התנאים הנ"ל שווה למספר כל הפתרונות של‬ ‫המשוואה ‪ x1 + x 2 + x 3 + x 4 + x5 + x 6 = 24‬שהוא )‪. D(6,24‬‬ ‫לסיכום‪ ,‬מאחר שהתנאים )‪ (2) ,(1‬ו‪ (3) -‬מתארים את קבוצת פתרונות המשוואה‬ ‫‪ x1 + x 2 + x 3 + x 4 + x5 + x 6 = 24‬כאיחוד של שלוש קבוצות זרות זו לזו נקבל‪:‬‬ ‫‪. D (6, 24) = 2 x + D (3,12) 2‬‬ ‫לפיכך שהתשובה לסעיף זה היא‪:‬‬ ‫‪118,755 − 8281‬‬ ‫‪= 55237‬‬ ‫‪2‬‬

‫‪2‬‬

‫=‪‬‬ ‫‪‬‬

‫‪1  29   14‬‬ ‫‪−‬‬ ‫‪‬‬ ‫‪2   5   2 ‬‬

‫‪2‬‬

‫=‬

‫))‪D(6, 24) − ( D(3,12‬‬ ‫‪2‬‬

‫=‪x‬‬

‫שאלה ‪5‬‬ ‫א‪ .‬בגרף ‪ G‬יש קשתות בין כל שני צמתים שבקבוצה}‪ {1, 2, 3, 4‬ויש קשתות בין כל שני צמתים‬ ‫שבקבוצה }‪ .{5,6, 7,8,9‬לאחר מחיקת כל הקשות האלה מן הגרף המלא על קבוצה‬ ‫הצמתים }‪{1, 2,3, 4,5, 6,7,8,9‬ישארו כל הקשתות עם קצה אחד ב‪{1, 2, 3, 4} -‬וקצה שני ב‪-‬‬ ‫}‪ {5,6, 7,8,9‬שהוא הגרף הדו‪-‬צדדי המלא עם צדדים }‪.{1,2,3, 4} , {5,6,7,8,9‬‬ ‫לכן הגרף המשלים ‪ H‬מוכל בגרף הדו‪-‬צדדי הזה‪ .‬מאחר שב‪ G -‬יש עוד חמש קשתות )שהן‬ ‫בהכרח עם קצה אחד ב‪{1, 2, 3, 4} -‬וקצה אחר ב‪ ({5,6, 7,8,9} -‬נקבל שהמשלים ‪ H‬הוא‬ ‫גרף המתקבל מהגרף הדו‪ -‬צדדי המלא הנ"ל לאחר מחיקת אותן חמש קשתות שהיו קיימות‬ ‫ב‪ . G -‬לכן גם ‪ H‬דו‪-‬צדדי )כתת גרף של גרף דו‪-‬צדדי(‬ ‫‪ 4  5 ‬‬ ‫‪ 2  2‬‬

‫ב‪ .‬ב‪ G -‬יש ‪   +   + 5 = 6 + 10 + 5 = 21‬קשתות‪.‬‬ ‫‪ 9‬‬

‫לכן ב‪ H -‬יש ‪   − 21 = 36 − 21 = 15‬קשתות‪.‬‬ ‫‪ 2‬‬ ‫ג‪ .‬בשאלה ‪ 3‬בתורת הגרפים מראים שלגרף מישורי פשוט‪ ,‬קשיר ודו‪-‬צדדי מספר הקשתות‬ ‫הוא לכל היותר ‪ , 2n − 4‬משמע אצלנו ‪ .14‬לכן ‪ H‬לא מישורי‬

‫‪3‬‬...