שיעור פתרון

מבחן תשפ"ד ב', מועד א', שאלה 3 - קבוצת חזקה ועוצמה

שיעורי תאוריה רלוונטיים

קבוצת חזקה, עוצמה והפרש סימטרי

נוסח השאלה

תהי C=P({1})-{1}. קבעו נכון או לא נכון ונמקו: {1}∈C.
עבור A={1,2,3,...,n}, כאשר n≥4, חשבו את גודל הקבוצה {B∈P(A) | B∩{1,2,3,4}={1,3}}.
נתונות D={5ⁿ·11^m | m,n∈{0,1,2,...,20}} ו-E={3ⁿ·11^m | m,n∈{0,1,2,...,20}}. חשבו |P(D×E)| ו-|DΔE|.

זיהוי השיטה

זו שאלה על קריאה מדויקת של קבוצת חזקה ועל ספירה. צריך להבדיל בין 1 לבין {1}, לספור בחירות חופשיות בתת-קבוצה, ולהשתמש בפירוק יחיד לגורמים ראשוניים.

פתרון מודרך

א. האם {1} שייך ל-C?

נוסח הסעיף: תהי C=P({1})-{1}. קבעו נכון או לא נכון ונמקו: {1}∈C.

קבוצת החזקה של {1} היא:

P({1}) = {∅, {1}}

בביטוי P({1})-{1} מחסרים את הקבוצה שהאיבר היחיד שלה הוא 1. כלומר בודקים אם האיבר 1 עצמו נמצא בתוך P({1}), ולא מסירים את האיבר {1}.

P({1}) \ {1} = {∅, {1}} \ {1}

האיברים של P({1}) הם ∅ ו-{1}. המספר 1 אינו אחד מהם, ולכן לא הוסר דבר:

C = {∅, {1}}

לכן {1}∈C.

ב. ספירת תתי-קבוצות עם תנאי חיתוך

נוסח הסעיף: עבור A={1,2,3,...,n}, כאשר n≥4, חשבו את גודל הקבוצה {B∈P(A) | B∩{1,2,3,4}={1,3}}.

התנאי B∩{1,2,3,4}={1,3} אומר:

1 ו-3 חייבים להיות ב-B.
2 ו-4 חייבים לא להיות ב-B.
האיברים 5,6,...,n חופשיים.

למה סופרים דווקא את האיברים החופשיים? תת-קבוצה B נקבעת לפי החלטה על כל איבר של A: האם האיבר נכנס ל-B או לא. עבור 1,3 ההחלטה כבר נקבעה ל"נכנס"; עבור 2,4 ההחלטה כבר נקבעה ל"לא נכנס". לכן ארבעת האיברים האלה אינם מוסיפים אפשרויות בחירה.

לעומת זאת, לכל איבר מתוך 5,6,...,n אין מגבלה נוספת. כל אחד מהם יכול להיכנס או לא להיכנס, והבחירה לגבי איבר אחד אינה משנה את הבחירה לגבי איבר אחר. לכן הגודל המבוקש אינו מספר האיברים החופשיים עצמו, אלא מספר כל דרכי הבחירה עליהם. אם יש n-4 איברים חופשיים, מספר הבחירות הוא:

2·2·...·2 = 2^n-4 |{B∈P(A) | B∩{1,2,3,4}={1,3}}| = 2^n-4

ג. הקבוצות D ו-E

נוסח הסעיף: נתונות D={5ⁿ·11^m | m,n∈{0,1,2,...,20}} ו-E={3ⁿ·11^m | m,n∈{0,1,2,...,20}}. חשבו |P(D×E)| ו-|DΔE|.

בכל אחת מהקבוצות יש 21 אפשרויות ל-n ו-21 אפשרויות ל-m. בגלל פירוק יחיד לגורמים ראשוניים, כל הבחירות יוצרות ערכים שונים.

|D| = |E| = 21·21 = 441

לכן:

|D×E| = 441² = 194481 |P(D×E)| = 2¹⁹⁴⁴⁸¹

כדי למצוא את החיתוך, נדרוש:

5ⁿ·11^m = 3^a·11^b

משווים מעריכים של ראשוניים. בצד ימין אין גורם 5, לכן חייב להיות n=0. בצד שמאל אין גורם 3, לכן חייב להיות a=0. לגורם 11 צריך אותו מעריך בשני הצדדים, ולכן m=b.

D∩E = {11^m | m=0,...,20}

יש כאן 21 אפשרויות ל-m, ולכן |D∩E|=21.

הפרש סימטרי סופר את האיברים שנמצאים בדיוק באחת משתי הקבוצות. סכום |D|+|E| סופר כל איבר משותף פעמיים, ולכן מחסרים 2|D∩E|:

|DΔE| = |D| + |E| - 2|D∩E| = 441 + 441 - 42 = 840

תשובה סופית

הטענה {1}∈C נכונה.

גודל קבוצת תתי-הקבוצות הוא 2^n-4.

|P(D×E)| = 2¹⁹⁴⁴⁸¹, ו-|DΔE| = 840.

המשך במבחן

מבחן תשפ"ד ב', מועד א' · שאלה 3

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 4 - PNF ותכונות יחס