Question

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

Comments

دوست عزیز سلام
شما از صورت سوال مطمین هستید؟ به نظرم به جای 2n باید 2m مینوشتید.
لطفا صورت سوال را بازبینی بفرمایید.تشکر

---

سلام ممنون از توجه شما
تصحیح شد

---

با عرض درود خدمت شما
ممنون میشم اگر مرجعی برای این سوال دارید ذکر بفرمایید

---

سلام
راستش به ذهن خودم رسید جایی ندیدمش

---

@alimohandes
اثبات یا مثال نقضی هم براش دارید ؟
اگر ندارید ممنون میشم تلاشتون برای اثبات یا ایده ای که باعث شد به این مسئله برسید ذکر کنید

Answer 1

این مسئله در حالت خاص 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 جواب مورد نظر می باشد.

Answer 2

دو افراز را $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$ حداقل یک تطابق کامل دارد و بدین ترتیب اثبات حکم به پایان می‌رسد.