توابع پوشا و توزیع با «حداقل یکی»

نهایی: در ۱۰ امتحان از ۲۶، روی‌هم ۱۱ نمره

ایده

توزیعِ $m$ شیءِ متفاوت بین چند نفر که هر نفر حداقل یکی بگیرد، یعنی تابع پوشا از $A$ ( $m$ عضو) به $B$ . برای $∣ B ∣ = ۳$ ، $A_{j}$ را تابع‌هایی بگیر که به $b_{j}$ نمی‌رسند و اجتماعشان را از همهٔ تابع‌ها کم کن: $∣ S ∣ = ۳^{m}$ ، $∣ A_{j} ∣ = ۲^{m}$ ، $∣ A_{i} \cap A_{j} ∣ = ۱$ و $∣ A_{۱} \cap A_{۲} \cap A_{۳} ∣ = ۰$ . اگر $∣ A ∣ < ∣ B ∣$ تابع پوشا وجود ندارد.

۳^{m} - (۳ \times ۲^{m} - ۳ \times ۱ + ۰)

نمونهٔ نهایی

نهایی شهریور ۱۴۰۴، سؤال ۱۵۱/۵ نمره

به چند طریق می‌توان $۴$ مهره به رنگ های سبز، قرمز، آبی و سفید را در $۳$ ظرف قرار دهیم، به‌شرطی‌که هیچ ظرفی خالی نماند؟ (ذکر راه‌حل الزامی است.)

هر چیدمان یک تابع از مهره‌ها ( $A$ ، چهار عضو) به ظرف‌ها ( $B$ ، سه عضو) است و «هیچ ظرفی خالی نماند» یعنی پوشا؛ $A_{j}$ را تابع‌هایی بگیر که به ظرف $j$ نمی‌رسند.
$A_{j} = {f : A \to B ∣ f (a_{i}) \neq = b_{j}, ۱ \leq i \leq ۴}, ۱ \leq j \leq ۳$
تابع‌های پوشا بیرونِ $A_{۱} \cup A_{۲} \cup A_{۳}$ هستند؛ از همهٔ تابع‌ها، اجتماع را کم کن.۰/۲۵ نمره
$∣ \overline{A_{۱}} \cap \overline{A_{۲}} \cap \overline{A_{۳}} ∣ = ∣ \overline{A_{۱} \cup A_{۲} \cup A_{۳}} ∣ = ∣ S ∣ - ∣ A_{۱} \cup A_{۲} \cup A_{۳} ∣$
هر مهره سه ظرف برای رفتن دارد؛ تعداد همهٔ تابع‌ها را بنویس.۰/۲۵ نمره
$∣ S ∣ = ۳^{۴} = ۸۱$
اجتماع را با اصل شمول بنویس: هر $A_{j}$ برای هر مهره دو انتخاب دارد، اشتراکِ دوتاییِ آن‌ها یک تابع است و اشتراکِ سه‌تایی هیچ.۰/۷۵ نمره
$∣ A_{۱} \cup A_{۲} \cup A_{۳} ∣ = ۳ \times ۲^{۴} - ۳ \times ۱^{۴} + ۰$
اجتماع را از کل کم کن.۰/۲۵ نمره
$۸۱ - (۴۸ - ۳) = ۸۱ - ۴۵ = ۳۶$

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

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

۴ سؤال دیگر