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

נתונה קבוצה $A$ כך ש-$|A| = 3$ וקבוצה $B = \{4,5,6,7,8,9,10\}$. מצאו את מספר הפונקציות $f$ מ-$A$ ל-$B$ אשר מקיימות את התנאים הבאים: קיים $k \in A$ כך ש-$f(k)$ מתחלק ב-2, קיים $l \in A$ כך ש-$f(l)$ מתחלק ב-3, וגם קיים $m \in A$ כך ש-$f(m)$ מתחלק ב-5.

רמז: השתמשו בהכלה-הדחה על המשלימים: חסרו מקרים שבהם אף איבר לא נשלח למכפלת 2, או 3, או 5.

פתרון: נסמן: - $X$ = קבוצת הפונקציות שבהן קיים $k$ עם $2 | f(k)$ - $Y$ = קבוצת הפונקציות שבהן קיים $l$ עם $3 | f(l)$ - $Z$ = קבוצת הפונקציות שבהן קיים $m$ עם $5 | f(m)$ נחשב את $|X \cap Y \cap Z|$ באמצעות **הכלה-הדחה** על המשלימים. ב-$B = \{4,...,10\}$: מתחלקים ב-2: $\{4,6,8,10\}$ (4 איברים). מתחלקים ב-3: $\{6,9\}$ (2 איברים). מתחלקים ב-5: $\{5,10\}$ (2 איברים). לא מתחלקים ב-2: $\{5,7,9\}$ (3 איברים). לא מתחלקים ב-3: $\{4,5,7,8,10\}$ (5 איברים). לא מתחלקים ב-5: $\{4,6,7,8,9\}$ (5 איברים). לא מתחלקים ב-2 ולא ב-3: $\{5,7\}$ (2 איברים). לא מתחלקים ב-2 ולא ב-5: $\{7,9\}$ (2 איברים). לא מתחלקים ב-3 ולא ב-5: $\{4,7,8\}$ (3 איברים). לא מתחלקים ב-2,3,5: $\{7\}$ (1 איבר). $|\overline{X}| = 3^3 = 27$, $|\overline{Y}| = 5^3 = 125$, $|\overline{Z}| = 5^3 = 125$. $|\overline{X} \cap \overline{Y}| = 2^3 = 8$, $|\overline{X} \cap \overline{Z}| = 2^3 = 8$, $|\overline{Y} \cap \overline{Z}| = 3^3 = 27$. $|\overline{X} \cap \overline{Y} \cap \overline{Z}| = 1^3 = 1$. סה"כ פונקציות: $7^3 = 343$. $|X \cap Y \cap Z| = 343 - (27+125+125) + (8+8+27) - 1 = 343 - 277 + 43 - 1 = 108$. **התשובה: $108$**. $\blacksquare$