اگر $X$ مجموعهٔ $n$ عضوی باشد، تعداد $(A,B)$هایی که $A\subset B\subseteq X$ را بیابید.

Question

فرض کنید $X$ مجموعه‌ای $n$ عضوی باشد. تعداد زوج مرتب‌های $(A,B)$ را بیابید که $ A, B\subseteq X$ و همچنین $ A \subset B$. پاسخ باید $3^n - 2^n $ باشد. این پرسش را در یکی از آزمون‌های المپیاد ریاضی سال ۱۳۷۱ دیده‌ام.

Comments

سلام. لطفا برای نوشتن صورت سوال. مسئله سوال رو در بین دو دلار قرار بدید.
@pantea

---

@pantea می‌دانید چند المپیاد ریاضی در سال ۱۳۷۱ برگزار شده‌است؟ مرجع باید به طور یکتا مشخص شود، این المپیاد برای چه مقطعی بوده‌است؟ در چه مرحله‌ای بوده‌است؟ کدام کشور؟ برای نمونه راهنمایی، دبیرستان، کارشناسی، مرحلهٔ گزینش مدرسهٔ فلان، ناحیه فلان در شهر فلان، استان فلان، مرحلهٔ کشوری، مرحلهٔ بین‌المللی.
بعلاوه عنوان پرسش‌تان به نظر خودتان مناسب است؟ پست زیر را بخوانید و سپس پرسش‌تان را ویرایش کنید. https://math.irancircle.com/11973 در مورد تایپ ریاضی نیز پست‌های زیر را نگاه بیندازید. https://math.irancircle.com/52 و https://math.irancircle.com/56

Answer 1

به نام خدا.

فرض کنید که B یک زیرمجموعه $ k $ عضوی از مجموعه ی $n$ عضوی $X$ باشد. در این صورت مجموعه $A$ دارای $2^k−1$ حالت است. علت $-1$ برای این است که نباید $A=B$ باشد. پس تعداد زوج $(A,B)$ که $B \subseteq X$ و $A \subset B$ و $B$ مجموعه $k$ عضوی است، برابر است با:

$ \binom{n}{k} ×(2^k−1)$

علت $\binom{n}{k} $ برای این است که تعداد حالت هایی که B مجموعه ایk عضوی است برابر است با $\binom{n}{k}$ .

حال $k$ می تواند برابر با $0$,$ 1$,...,یا $n$ باشد. پس پاسخ سوال می شود:

$\binom{n}{0} (2^0-1)+ \binom{n}{1} (2-1)+...+ \binom{n}{n} (2^n-1)= \binom{n}{0}2^0 +..+ \binom{n}{n} 2^n-( \binom{n}{0} +...+ \binom{n}{n} )=(2+1)^n-(1+1)^n=3^n-2^n$

Answer 2

صورت سوال این است :

(( فرض کنید $X$ یک مجموعه $n$ عضوی است . تعداد زوج های مرتب $(A,B)$ به طوری که $A,B \subseteq X$ و $A \subset B$ برابر است با $ 3^{n} - 2^{n} $ . ))

اثبات :

به هر زوج $(A,B)$ از زیر مجموعه های $X$ که $A \subseteq B$ می توان یک کد $n$ رقمی همچون $ a_{1} a_{2} a_{3} \ ... \ a_{n} $ متشکل از ارقام $0,1,2$ نسبت داد که به ازای هر $i=1,2,3 $ داریم :

$$ a_{i} =\begin{cases}0 & i \in A\1 & i \in B-A\2 & i \in X-B\end{cases} $$

و بعکس به هر کدی به این شکل می توان یک زوج مرتب $(A,B)$ از زیرمجموعه های $X$ را نسبت داد که $A \subseteq B$ . پس تعداد این زوج های مرتب برابر تعداد کدهای $n$ رقمی با ارقام $0,1,2$ است که برابر $ 3^{n} $ است .

از طرفی تعداد زوج های $(A,B)$ که $A,B \subseteq X$ و $A=B$ برابر $ 2^{n} $ است . زیرا مجموعه $X$ دارای $ 2^{n} $ زیرمجموعه است . در نتیجه تعداد زوج های مرتب $(A,B)$ که $A,B \subseteq X$ و $A \subset B$ برابر $ 3^{n} - 2^{n} $ است .