کارت های همانی

قسمت الف)

راه حل اول:

نوید می‌تواند به $99!$ حالت دسته‌بندی سعید را شماره‌گذاری کند. نشان‌ می‌دهیم حتمادریکی ازاین $99!$ حالت شماره‌گذاری،۱۵کارت‌ همانی وجود دارد. دسته‌ها را در دسته‌بندی دوم به ترتیب $A_1,A_2,…,A_99$ نام‌گذاری می‌کنیم.

جدولی با $99!$ سطر و ۹۹‌ ستون در نظر بگیرید. ستون $i$ ام این جدول را نماینده دسته $A_i$ و سطر $j$ ام این جدول را نماینده حالت $j$ ام شماره گذاری دسته‌ها توسط نوید در نظر بگیرید. در خانه تقاطع سطر $j$ام و ستون$i$ام این جدول، تعداد کارت‌های همانی که در دسته $A_i$در ترتیب $j$ ام وجود دارد را یادداشت می‌کنیم.

حال مجموع اعداد جدول را به صورت ستون به ستون محاسبه می‌کنیم. می‌دانیم ستون $j$ ام معرف دسته $A_j$ است. ادعا می‌کنیم مجموع اعداد ستون $j$ ام برابر است با$|A_j |\times 98!$. یک کارت خاص موجود در دسته $A_j$ را در نظر بگیرید و آن را $x$ بنامید . $x$در صورتی همانی است که شماره دسته‌اش در شماره‌گذاری نوید نیز برابر با $j$ باشد. پس آن دسته‌ای که حاوی تیله $x$ است (در ترتیب نوید) باید شماره‌اش j شود و بقیه ۹۸ دسته می‌توانند هر شماره دلخواهی پیدا کنند. پس x در $98!$ شماره‌گذاری مختلف همانی است. با توجه به این استدلال واضح است که مجموع اعداد ستون $j$ ام برابر است با $|A_j |\times 98!$. پس مجموع اعداد جدول برابر است با :

$$\sum_{i=1}^{99} |A_i |×98! = 98!×\sum_{i=1}^{99}|A_i | = 98!× 1392$$

از طرفی چون این جدول۹۹! سطر دارد، طبق اصل لانه کبوتر، سطری با مجموع$⌈\frac{98!\times 1392}{99!}⌉=$15 وجود خواهد داشت. اما همان‌طور که در ابتدا گفتیم، هر سطر نشان‌دهنده‌ی یک روش شماره‌گذاری توسط نوید بود. این یعنی نوید می‌تواند طوری دسته‌هایش را شماره‌گذاری کند که حداقل ۱۵کارت همانی وجود داشته باشد و حکم ثابت شد.

توجه: در این راه از این‌که در دسته‌بندی دوم هیچ دو کارت هم‌دسته در دسته‌بندی اول هم‌دسته نیستند استفاده نشده است.

راه‌حل دوم:

این مسئله را می‌توان با گراف و مسئله تطابق مدل کرد.

از روی دسته‌بندی‌های سعید می‌توان یک گراف دوبخشی ساخت. در این گراف دوبخشی هر بخش متناظر با یکی از دسته‌بندی‌ها خواهد بود و در هر بخش ۹۹ راس متناظر با ۹۹ دسته‌ی دسته‌بندی وجود دارد. حال بین هر دو راسی که دسته‌های متناظر آن‌ها شامل یک کارت مشترک است یک یال می‌گذاریم.

مشاهده۱: این گراف یال چندگانه ندارد (چرا؟).

مشاهده۲: در هر شیوه شماره‌گذاری کارت‌های همانی معادل یک تطابق در گراف دو بخشی هستند(چرا؟).

قضیه: در گراف فوق تطابق بیشنه حداقل ۱۵ یال دارد.

اثبات: یک راه برای اثبات این قضیه اثبات از طریق برهان خلف می‌باشد.

راه حل سوم:

در این روش از شیوه احتمالاتی استفاده شده است، که انتظار نمی‌رود دانش‌آموزان از این روش مسئله را حل کنند، لیکن برای آشنایی علاقه‌مندان این روش نیز بیان می‌گردد.

اگر یک شماره‌گذاری تصادفی را در نظر بگیریم احتمال این‌که یک کارت، کارت ‌همانی باشد برابر با $\frac{1}{99}$ خواهد بود. حال اگر $X$ را متغیر تصادفی تعداد کارت‌های همانی در یک شماره گذاری بنامیم. می‌دانیم:

$$X=X_1+X_2+⋯+X_{1392}$$

که $X_i‌$ متغیرتصادفی شاخص همانی بودن کارت $i$ ام خواهد بود و می‌دانیم امید ریاضی $X_i$ برابر است با:

$$E[X_i ]=Pr[X_i=1]=\frac{1}{99}$$

واما برای امیدریاضی $X$ خواهیم داشت:

$$E[X]=E[\sum_{i=1}^{1392} X_i ]=\sum_{i=1}^{1392} E[X_i]= \frac{1392}{99}>14$$

اما با توجه به این‌که همیشه حالتی وجود دارد که $X≥E[X]$ و این‌که مقدار $X$ عدد صحیح می‌باشد پس شماره‌گذاری وجود دارد که در آنX یعنی تعداد کارت‌های همانی بیش‌تر از ۱۴ باشد.

قسمت ب)

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

در گراف نشان داده شده ۹۵ راس از بخش پایین به یک راس از بخش بالا وصل شده اند و بقیه یال‌ها بین دسته ۱۴تایی و ۹۸ تایی قرار می‌گیرد. می‌دانیم که می‌توانیم $14\times 99=1386$ یال از نوع دوم داشته‌باشیم که بیش‌تر از نیاز ما نیز می‌باشد. اما در این گراف تطابق بیشینه حداکثر برابر با ۱۵ خواهد بود و با توجه به قسمت الف می‌دانیم این مقدار دقیقا برابر ۱۵ می‌باشد.