به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
2,841 بازدید
در دبیرستان توسط rafig256 (646 امتیاز)
ویرایش شده توسط AmirHosein

گزارهٔ زیر را در نظر بگیرید.

تعداد زیرمجموعه‌های زوج عضوی - و فرد عضوی - هر مجموعه برابر است با $ 2^{n-1} $.

می‌دانم که این قضیه با استقرای ریاضی به سادگی اثبات می‌شود. اما بنده به دنبال اثبات‌های متفاوت هستم. همچنین این قضیه با اصل دوسویگی هم قابل اثبات است. به نظر من باید بتوان با نوشتن جمع تعداد زیرمجموعه‌های $2k$ عضوی ($2k+1$ عضوی) به عدد $2^{n-1}$ رسید. یعنی

$$\binom{n}{0}+ \binom{n}{2}+\binom{n}{4}+ ... + \binom{n}{2[ \frac{n}{2} ]} = \binom{n}{1}+ \binom{n}{3}+\binom{n}{5}+ ... + \binom{n}{2[ \frac{n}{2} ]-1}= 2^{n-1}$$

اما چگونه باید این فرمول را ثابت کنم؟

توسط kazomano (2,561 امتیاز)
+2
در بسط خیام $ (x+y)^{n} $ قرار بدید x=-1 , y=1
توسط rafig256 (646 امتیاز)
x=-1 , y=1 از کجا می یان و نشان دهنده چیه؟
توسط rafig256 (646 امتیاز)
+1
ممنون از راهنماییتون.
حذف شد
توسط AmirHosein (19,620 امتیاز)
@rafig256 همان عبارتی که در انتهای متن پرسش‌تان را نوشتید بدون $=2^{n-1}$ را نگاه کنید. هر دو عبارت را به یک طرف بیاورید. منفی یک به توان $i$ها درست می‌شود و یک هم که به هر توانی یک می‌شود پس چرا $n-i$ نگذارید؟ سپس به همان دیدگاه @kazomano نمی‌رسید؟ گزینش $x$ و $y$ از همین چند محاسبهٔ ساده می‌آیند و نشأت می‌گیرند. و خود $2^{n-1}$ هم که بدیهی است. جمع دو چیز برابر شده‌است $2^n$ پس تک تک $2^{n-1}$ بوده‌اند.

2 پاسخ

0 امتیاز
توسط
انتخاب شده توسط rafig256
 
بهترین پاسخ

یک روش ساده دیگه ایهم که هست اینه ما میایم عضو اول رو کنار میزاریم
و بقیه عضو ها دو حالت دارند یا باشند یا نباشند که میشه 2^{n-1}
حالا اگه ما زوج عضوی بخوایم و زیر مجموعه انتخاب شدمون فرد عضو داشته باشه برا اون عدده که کنار گزاشتیم یک حالت وجود داره که باشه یا بالعکسش ما زوج عضوی داریم و زوج عضوی میخوایم یه حالت وجود داره که نباشه

+1 امتیاز
توسط mahdiahmadileedari (3,075 امتیاز)

این مسئله به ترکیبیات اشاره دارد. برای یافتن تعداد زیر مجموعه های زوج عضوی و فرد عضوی، می توانیم به صورت زیر عمل کنیم:

فرض کنید مجموعه ما$ n$ عضو داشته باشد. حال برای هر عضو، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو، دو حالت وجود دارد. پس تعداد کل زیر مجموعه ها برابر است با $2×2×2....=2^n$

حال برای یافتن تعداد زیر مجموعه های زوج عضوی، می توانیم به این صورت عمل کنیم: ابتدا یک عضو را به عنوان "اولین عضو" انتخاب می کنیم. حال برای هر عضو دیگر، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو دیگر، دو حالت وجود دارد. اما برای اینکه زیر مجموعه زوج عضوی باشد، باید تعداد عضوهای حضور دار در زیر مجموعه فرد باشد. بنابراین برای هر عضو دیگر، تنها یک حالت وجود دارد. پس تعداد زیر مجموعه های زوج عضوی برابر است با

$2^{(n-1)}$

حال برای یافتن تعداد زیر مجموعه های فرد عضوی، می توانیم به همین روش عمل کنیم: ابتدا یک عضو را به عنوان "اولین عضو" انتخاب می کنیم. حال برای هر عضو دیگر، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو دیگر، دو حالت وجود دارد. اما برای اینکه زیر مجموعه فرد عضوی باشد، باید تعداد عضوهای حضور دار در زیر مجموعه زوج باشد. بنابراین برای هر عضو دیگر، نیز تنها یک حالت وجود دارد. پس تعداد زیر مجموعه های فرد عضوی برابر است با $$2^{n-1}$$

بنابراین، تعداد زیر مجموعه های زوج عضوی و فرد عضوی هر کدام برابر با$$ 2^{(n-1) }$$است. پس تعداد زیر مجموعه های زوج عضوی و فرد عضوی در مجموع برابر است با $$2^n$$ اما این تعداد کل زیر مجموعه هاست. بنابراین تعداد زیر مجموعه های زوج عضوی برابر است با نصف تعداد کل زیر مجموعه ها، و همچنین تعداد زیر مجموعه های فرد عضوی نیز برابر است با نصف تعداد کل زیر مجموعه ها.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...