شمول و عدم شمول: بخش‌پذیری: ریاضیات گسسته، فصل ۳

ایده

مضرب‌های هر عدد را مجموعه بگیر: $A$ مضرب‌های $a$ و $B$ مضرب‌های $b$ در بازهٔ $۱$ تا $N$ . تعداد مضرب‌های $a$ برابر $[\frac{N}{a}]$ است و عددِ بخش‌پذیر بر هر دو، مضربی از «کوچک‌ترین مضرب مشترک» آن دو است. «بر هیچ‌کدام» را با متمم بشمار و «بر $a$ ولی نه بر $b$ » را با $∣ A ∣ - ∣ A \cap B ∣$ .

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣, ∣ \overline{A} \cap \overline{B} ∣ = ∣ S ∣ - ∣ A \cup B ∣

نمونهٔ نهایی

نهایی تیر ۱۴۰۵، سؤال ۱۶۱/۵ نمره

با استفاده از اصل شمول و عدم شمول، مشخص کنید که در بین اعداد طبیعی $۱$ تا $۴۰۰$ ( $۱ \leq n \leq ۴۰۰$ )، چند عدد وجود دارد که بر هیچ یک از اعداد $۲$ و $۵$ بخش‌پذیر نباشند؟ (بر $۲$ بخش‌پذیر نباشند و بر $۵$ نیز بخش‌پذیر نباشند.)

مضرب‌های $۲$ را مجموعهٔ $A$ بگیر و تعدادشان را با جزء صحیح بشمار.۰/۲۵ نمره
$A = {n \in N ∣ ۱ \leq n \leq ۴۰۰, ۲ ∣ n} \Rightarrow ∣ A ∣ = [\frac{۴۰۰}{۲}] = ۲۰۰$
مضرب‌های $۵$ را مجموعهٔ $B$ بگیر.۰/۲۵ نمره
$B = {n \in N ∣ ۱ \leq n \leq ۴۰۰, ۵ ∣ n} \Rightarrow ∣ B ∣ = [\frac{۴۰۰}{۵}] = ۸۰$
عددِ بخش‌پذیر بر $۲$ و $۵$ بر $۱۰$ بخش‌پذیر است؛ مضرب‌های $۱۰$ را بشمار.۰/۲۵ نمره
$A \cap B = {n \in N ∣ ۱ \leq n \leq ۴۰۰, ۱۰ ∣ n} \Rightarrow ∣ A \cap B ∣ = [\frac{۴۰۰}{۱۰}] = ۴۰$
«بر هیچ‌کدام بخش‌پذیر نباشد» یعنی بیرونِ $A \cup B$ ؛ از کل، اجتماع را کم کن و اصل شمول را بگذار.۰/۵ نمره
$∣ \overline{A} \cap \overline{B} ∣ = ∣ S ∣ - ∣ A \cup B ∣ = ∣ S ∣ - (∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣) = ۴۰۰ - (۲۰۰ + ۸۰ - ۴۰)$
حساب کن.۰/۲۵ نمره
$۴۰۰ - ۲۴۰ = ۱۶۰$

همهٔ سؤال‌های این تیپ

امتحان نهایی ۱۳

۷ سؤال دیگر