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

חשבו את המספר $|\{x \in \mathbb{N} \mid x \leq 490, \gcd(x, 7070) = 1\}|$. ($\gcd$ פירושו מחלק משותף מקסימלי). אפשרויות: 154, 164, 166, 170, 173, 176, 900, 1020, 1200, 1220, 1240, 1260, 2112, 2442, 2460, 4224, 4884, 8448

רמז: פרקו $7070 = 2 \cdot 5 \cdot 7 \cdot 101$ והשתמשו בהכלה-הדחה כדי לספור מספרים שלא מתחלקים באף גורם ראשוני.

פתרון: נפרק: $7070 = 2 \cdot 5 \cdot 7 \cdot 101$. צריך לספור כמה מספרים $x \in \{1, 2, \ldots, 490\}$ מקיימים $\gcd(x, 7070) = 1$, כלומר $x$ לא מתחלק ב־2, 5, 7, או 101. נשתמש ב**הכלה-הדחה**. נסמן: - $A_2$ = מספרים עד 490 המתחלקים ב-2: $\lfloor 490/2 \rfloor = 245$ - $A_5$ = מתחלקים ב-5: $\lfloor 490/5 \rfloor = 98$ - $A_7$ = מתחלקים ב-7: $\lfloor 490/7 \rfloor = 70$ - $A_{101}$ = מתחלקים ב-101: $\lfloor 490/101 \rfloor = 4$ - $|A_2 \cap A_5| = \lfloor 490/10 \rfloor = 49$ - $|A_2 \cap A_7| = \lfloor 490/14 \rfloor = 35$ - $|A_2 \cap A_{101}| = \lfloor 490/202 \rfloor = 2$ - $|A_5 \cap A_7| = \lfloor 490/35 \rfloor = 14$ - $|A_5 \cap A_{101}| = \lfloor 490/505 \rfloor = 0$ - $|A_7 \cap A_{101}| = \lfloor 490/707 \rfloor = 0$ - $|A_2 \cap A_5 \cap A_7| = \lfloor 490/70 \rfloor = 7$ - $|A_2 \cap A_5 \cap A_{101}| = \lfloor 490/1010 \rfloor = 0$ - $|A_2 \cap A_7 \cap A_{101}| = \lfloor 490/1414 \rfloor = 0$ - $|A_5 \cap A_7 \cap A_{101}| = \lfloor 490/3535 \rfloor = 0$ - $|A_2 \cap A_5 \cap A_7 \cap A_{101}| = 0$ לפי הכלה-הדחה: $$|A_2 \cup A_5 \cup A_7 \cup A_{101}| = (245+98+70+4) - (49+35+2+14+0+0) + (7+0+0+0) - 0$$ $$= 417 - 100 + 7 = 324$$ לכן מספר ה-$x$ עם $\gcd(x, 7070) = 1$ הוא $490 - 324 = 166$. לחלופין, ניתן להשתמש ב**פונקציית אוילר**: $490 \cdot \frac{\varphi(7070)}{7070}$. $\varphi(7070) = 7070 \cdot (1 - 1/2)(1 - 1/5)(1 - 1/7)(1 - 1/101) = 7070 \cdot \frac{1}{2} \cdot \frac{4}{5} \cdot \frac{6}{7} \cdot \frac{100}{101} = 2400$. $490 \cdot \frac{2400}{7070}$... אבל $7070/490 = 101 \cdot 70 / 490 = 7070/490$. נבדוק: $7070 = 490 \cdot 14 + 210$. זה לא מתחלק. נשאר עם תוצאת ההכלה-הדחה: **$166$**. $\blacksquare$