به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+4 امتیاز
175 بازدید
در دبیرستان توسط alimohandes (21 امتیاز)
برچسب گذاری دوباره توسط alimohandes

مجموعه ای mn عضوی را به دو طریق به مجموعه های n عضوی افراز کرده ایم. ثابت کنید می توانm عضو انتخاب کرد به طوری که از هر کدام از 2m مجموعه دقیقا یک عضو انتخاب شده باشد

توسط Samaneh Soltani (1 امتیاز)
ویرایش شده توسط fardina
دوست عزیز سلام
شما از صورت سوال مطمین هستید؟ به نظرم به جای 2n باید 2m مینوشتید.
لطفا صورت سوال را بازبینی بفرمایید.تشکر
توسط alimohandes (21 امتیاز)
سلام ممنون از توجه شما
تصحیح شد
توسط moh_amin (352 امتیاز)
با عرض درود خدمت شما
ممنون میشم اگر مرجعی برای این سوال دارید ذکر بفرمایید
توسط alimohandes (21 امتیاز)
سلام
راستش به ذهن خودم رسید جایی ندیدمش
توسط moh_amin (352 امتیاز)
@alimohandes
اثبات یا مثال نقضی هم براش دارید ؟
اگر ندارید ممنون میشم تلاشتون برای اثبات یا ایده ای که باعث شد به این مسئله برسید ذکر کنید

2 پاسخ

0 امتیاز
توسط amir7788 (2,738 امتیاز)
ویرایش شده توسط amir7788

این مسئله در حالت خاص m=2 اثبات می کنم شاید به دوستان ایده بدهد که راه حل کلی پیدا شود. فرض می کنیم X مجموعه 2n عضوی باشه و A وB دو افراز n عضوی X باشند. $$A= \{A_1,A_2\} \quad B= \{B_1,B_2\} $$ حال ثابت می کنیم که 2 عضو وجود داره که دقیقا به یکی از $A_1,A_2,B_1,B_2$ تعلق داره.

  • اگر $A_1$ با یکی از اعضای B برابر باشه حکم بدیهی است چون مثلا $$A_1=B_1 \Rightarrow A_2=B_2 $$ در واقع دو افراز یکسانند
  • در غیر این صورت داریم $$A_1\neq B_1 \Rightarrow \exists a\in A_1, a\in B_2\& \exists b\in B_1,b\in A_2 $$ بنابراین همین دو عضو یعنی a و b جواب مورد نظر می باشد.
0 امتیاز
قبل توسط moh_amin (352 امتیاز)

دو افراز را $A$ و $B$ نامیده و اعضای آنها را $a_1,a_2,\cdots,a_m$ و $b_1,b_2,\cdots,b_m$ در نظر می‌گیریم. در حقیقت حکم بیان می‌دارد که می‌توان جایگشتی از $B$ مانند $c_1,c_2,\cdots,c_m$ پیدا کرد که برای هر $i$ طبیعی و کوچکتر مساوی $m$ داشته باشیم: $a_i\cap c_i\ne \phi $

گراف دوبخشی $G$ را با دو بخش $A$ و $B$ در نظر بگیرید و فرض کنید بین دو راس این گراف یالی وجود دارد اگر و فقط اگر زیرمجموعه های نسبت داده شده به آن دو راس دارای اشتراک غیر تهی باشند. اگر ثابت کنیم این گراف یک تطابق کامل دارد حکم نیز ثابت می‌شود زیرا می‌توان عضوی مشترک از هر دو راس که بین آنها یالی وجود دارد انتخاب کرد که در مجموع $m$ عضو مطابق با خواسته مسئله انتخاب خواهد شد.

با فرض $k\le m$ می‌دانیم هیچ $k$ عضوی از مجموعه $A$ با کمتر از $k$ عضو از مجموعه $B$ اشتراک ندارد؛ زیرا این $k$ عضو (که هر کدام خود یک زیرمجموعه $n$ عضوی است) اجتماعی با $kn$ عضو دارد و هر یک از این $kn$ عضو دقیقا در یکی از زیرمجموعه های عضو $B$ حضور دارد که هر کدام از آنها نیز شرایطی مشابه با آنچه ذکر شد دارند. از این رو $kn$ عضو نمی‌تواند در کمتر از $k$ زیرمجموعه جای گیرد. با توجه به این نتیجه گیری طبق قضیه هال گراف $G$ حداقل یک تطابق کامل دارد و بدین ترتیب اثبات حکم به پایان می‌رسد.


حمایت مالی

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