المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۷:سوالات ۱۶ و ۱۷

سوالات ۱۶ و ۱۷

۲۲ نفر می‌خواهند با هم فوتبال بازی کنند. آن‌ها برای این کار باید به دو تیم ۱۱ نفری غیر نشان‌دار تقسیم شوند. منظور از غیر نشان‌دار این است که تیم‌ها نام و شماره‌ی اعضا ندارند. در حقیقت، تنها هم‌تیمی بودن و نبودن افراد مهم است. هر یک از این ۲۲ نفر به یک نفر دیگر علاقه دارد. به فرد مورد علاقه، محبوب او نیز می‌گوییم. طبیعی است که رابطه‌ی محبوب بودن لزومن دوطرفه نیست! هر یک از این ۲۲ نفر از یک نفر دیگر متنفّر است. به فرد مورد تنفّر، منفور او نیز می‌گوییم. بالطّبع رابطه‌ی تنفّر نیز لزومن دوطرفه نیست!

طبیعی است که کسی محبوب یا منفور خودش نیست! هم‌چنین یک نفر می‌تواند محبوب یا منفور بیش از یک نفر باشد.

سوال ۱۶

می‌خواهیم تیم‌کشی طوری انجام شود که هیچ کس با منفورش هم‌تیم نباشد. در میان تمام حالات برای روابط افراد، کمینه و بیشینه‌ی تعداد حالات تیم‌کشی به ترتیب چیست؟

  1. ۱ و ۱
  2. ۰ و $2^{11}$
  3. ۱ و $2^{11}$
  4. ۰ و ۱
  5. ۰ و $2^{10}$

پاسخ

گزینه (۵) درست است.

ابتدا کمینه‌ی تعداد حالات را می‌شماریم. فرض کنید یک نفر منفور تمام افراد دیگر باشد. پس نمی‌تواند در هیچ تیمی قرار بگیرد و تعداد حالات صفر می‌شود و طبیعی است که کم‌تر از صفر هم امکان ندارد!

حال بیشینه را می‌شماریم. گراف جهت‌دار تنفّر افراد را در نظر بگیرید. گراف زمینه‌ی این گراف، حداکثر $\frac{22}{2}$ مؤلّفه دارد. رئوس هر مؤلّفه حداکثر به دو حالت می‌توانند در دو تیم قرار بگیرند. از طرفی به دو تیم شماره داده‌ایم و حاصل را باید بر دو تقسیم کنیم. پس تعداد حالات از $\frac{2^{11}}{2}$ بیش‌تر نیست. از طرفی اگر افراد در یازده دسته‌ی دوتایی، هر کدام از دیگری متنفّر باشند، دقیقن $\frac{2^{11}}{2} = 2^{10}$ حالت خواهیم داشت.

سوال ۱۷

می‌خواهیم تیم‌کشی طوری انجام شود که هر کس با محبوب‌ش هم‌تیم باشد. در میان تمام حالات برای روابط افراد، بیشینه‌ی تعداد حالات تیم‌کشی چیست؟

  1. ۷۰
  2. ۰
  3. ۲۴
  4. ۷۲۰
  5. ۲۵۲

پاسخ

گزینه (۱) درست است.

گراف جهت‌دار علاقه‌های افراد را در نظر بگیرید. در گراف زمینه‌ی این گراف، رئوس هر مؤلّفه باید هم‌تیم باشند. حال اگر یک مؤلّفه‌ی $k$ رأسی داشته باشیم که $k \ge 4$، می‌توانیم آن را به دو مؤلّفه‌ی دو و $k-2$ رأسی تقسیم کنیم و تعداد حالات کم‌تر نخواهد بود. پس در وضعیت با بیشینه‌ی حالات، تمام مؤلّفه‌ها دو یا سه رأسی هستند. از طرفی تعداد مؤلّفه‌های سه رأسی باید زوج باشد (زیرا تعداد افراد زوج است). اگر تعداد مؤلّفه‌های سه رأسی بیش از سه باشد، دو تا از آن‌ها را در نظر گرفته و به سه مؤلّفه‌ی دو رأسی تبدیل می‌کنیم. با این کار نیز تعداد حالات کم‌تر نخواهد شد. از طرفی دست کم دو مؤلفه‌ی سه رأسی نیاز داریم تا تیم‌ها فرد نفره شوند. پس در وضعیت با بیشینه‌ی حالات، دقیقن دو مؤلفه‌ی سه رأسی و هشت مؤلّفه‌ی دو رأسی خواهیم داشت. دو مؤلّفه‌ی سه رأسی به یک حالت در دو تیم مختلف قرار می‌گیرند. حال باید چهار مؤلّفه‌ی دو رأسی انتخاب کرده و در کنار یکی از آن‌ها قرار دهیم و بقیه را در تیم دیگر بگذاریم که $\binom{8}{4}=70$ حالت دارد.


ابزار صفحه