שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2015 - יחסים

יהי שקילות $R$ מעל קבוצת $A = \{0,1\} \times \{0,1\} \times \{0,1\} \times \{0,1\}$ מוגדר באופן הבא: $R = \{((a_1, a_2, a_3, a_4), (b_1, b_2, b_3, b_4)) \in A \times A \mid a_1 + a_2 + a_3 + a_4 = b_1 + b_2 + b_3 + b_4\}$. מצאו קבוצות נציגים עבור $R$ ולכל אחד מהנציגים רשמו את מספר האיברים במחלקה שלו.

רמז: היחס מקבץ לפי סכום הקואורדינטות. מספר הוקטורים עם סכום $k$ הוא $\binom{4}{k}$.

פתרון: היחס $R$ מקבץ וקטורים בינאריים באורך 4 לפי **סכום הרכיבים** שלהם. הסכום האפשרי הוא $0, 1, 2, 3, 4$. **מחלקות השקילות והנציגים:** | נציג | סכום | מספר איברים $\binom{4}{k}$ | |---|---|---| | $(0,0,0,0)$ | 0 | $\binom{4}{0} = 1$ | | $(1,0,0,0)$ | 1 | $\binom{4}{1} = 4$ | | $(1,1,0,0)$ | 2 | $\binom{4}{2} = 6$ | | $(1,1,1,0)$ | 3 | $\binom{4}{3} = 4$ | | $(1,1,1,1)$ | 4 | $\binom{4}{4} = 1$ | **סה"כ:** $1 + 4 + 6 + 4 + 1 = 16 = |A|$. $\blacksquare$