المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۳:سوال پنج

کار گروهی

آقای امینی معلم کلاسی شامل $nk$ دانش‌آموز می‌باشد. در این کلاس تعدادی رابطه دوستی بین دانش‌آموزان برقرار است (رابطه دوستی دوطرفه است، یعنی اگر دانش‌آموز a با دانش آموز b دوست باشد، دانش‌آموز b هم با a دوست هست). آقای امینی به کارهای گروهی خیلی علاقه‌مند هست. او می‌خواهد دانش‌آموزان را به $n$ گروه $k$ نفری تقسیم کند. اما برای او مهم است که افراد یک گروه همه با هم دوست باشند. ما می‌دانیم حداقل یک راه برای دسته‌بندی دانش‌آموزان با شرایط گفته شده وجود دارد. دانش‌آموزان که از این امر مطلع شده‌اند به دنبال این هستند که دسته‌بندی معلم را از قبل پیش‌بینی کنند.

الف) نشان دهید که اگر تعداد رابطه‌های دوستی برابر با ${k \choose 2} n^ 2$ باشد، حالتی از روابط دوستی وجود دارد که دسته‌بندی معلم به صورت یکتا مشخص شود.

ب) نشان دهید که اگر تعداد رابطه‌های دوستی بیشتر از ${k \choose 2} n^ 2$ باشد، هیچ حالتی نیست که دسته‌بندی بصورت یکتا انجام پذیرد.

پاسخ

قسمت اول

گراف روابط دوستی دانش‌آموزان را در نظر می‌گیریم. در واقع مسئله از ما خواسته است تا اثبات کنیم گرافی $nk$ راسی با$\binom{k}{2}n^2$ یال وجود دارد که افراز آن به خوشه‌های $k$ راسی یکتا مشخص شود. برای اثبات این حکم از استقرا روی $n$ استفاده می کنیم.

پایه: حکم برای $n=1$ برقرار است چرا که $\binom{k}{2}$ یال دقیقا یک خوشه را تشکیل می‌دهند.

فرض می‌کنیم برای کلاسی با $nk$دانش‌آموز چنین حالتی وجود داشته باشد.

کلاسی با $(n+۱)k$ نفر را در نظر بگیرید.ابتدا $k$ نفر از کلاس حذف و برای $nk$ نفر باقی‌مانده تعداد $\binom{k}{2} n^2$ رابطه‌ی دوستی در نظر می‌گیریم. حال $k$ نفر را به $nk$ نفر برمی‌گردانیم. برای این که شرایط مساله بر قرار باشد لازم است $\binom{k}{2} n^2((n+1)^2-n^2 ) = \binom{k}{2} n^2(۲n+۱)=\binom{k}{2} n^2+(k-۱)\times (nk)$ رابطه‌ی دوستی به روابط دوستی اضافه کنیم.به $\binom{k}{2}$ رابطه دوستی که برای گروه کردن $k$ دانش‌آموز نیاز داریم. پس$(k-۱)\times (nk)$ رابطه‌ی دوستی باقی می‌ماند که آن‌ها را باید به شکلی نسبت دهیم. با کمی دقت در میابیم که کافی است از شکل همین عبارت این ایده به ذهن می‌رسد که از آن $k$ نفر، یک نفر را کنار گذاشته‌ایم و بقیه را با تمام $nk$ نفر دوست کرده‌ایم. حال ادعا می‌کنیم که با این ساختار گروه بندی یکتا است (چرا؟).

قسمت دوم

طبق آنچه در صورت سوال آمده، تعداد روابط دوستی حداقل $\binom{k}{2} n^2+1$می‌باشد و حداقل یک گروه‌بندی وجود دارد. روابط دوستی غیر از رابطه‌ی هم گروه‌ها در این گروه‌بندی را در نظر بگیرید. تعداد این رابطه‌ها حداقل برابر است با$\binom{k}{2} n^2+1 – n\binom{k}{2} = \binom{k}{2} n(n-1)+1$ .

اما تعداد زوج‌ گروه‌ها برابر با $\binom{n}{2}$ است و $\binom{k}{2}n(n-1)+1$ رابطه دوستی بین این $\binom{n}{2}$ زوج گروه قرار دارد. پس طبق اصل لانه‌کبوتر حداقل یک زوج گروه وجود دارد که تعداد روابط دوستی بین اعضای آن بیش‌تر از یا مساوی با $⌈\frac{(\binom{k}{2} n(n-1)+1 )}{(\binom{n}{2} )}⌉ = k\times(k-1)+1$ باشد. از سوی دیگر کل روابط دوستی بین اعضای این دو گروه با یکدیگر حداکثر $k\times k$ تا بوده و حالا تنها $k-1$ رابطه‌ی دوستی از کل این رابطه‌ها را نداریم. پس در هر گروه عضوی هست که با تمامی اعضای گروه دیگر دوست باشد و در نتیجه با عوض کردن جای این دو نفر می‌توان یک گروه بندی جدید ایجاد کرد. با توجه به آنچه گفته شد در صورتی‌که تعداد یال‌ها بیش‌تر از $\binom{k}{2} n^2$ باشد و حداقل یک گروه‌بندی وجود داشته باشد، نمی‌توان گروه‌بندی را به صورت یکتا مشخص کرد.


ابزار صفحه