====== سوال ۱۳ ======

در کلاسی ۲۰۰ دانش‌آموز وجود دارد. هر دانش‌آموز از این کلاس با دقیقا یکی دیگر از دانش‌آموزان کلاس دوست است. رابطه‌ی دوستی دوطرفه است، یعنی اگر فرد $a$ دوست فرد $b$ باشد، آنگاه فرد $b$ نیز دوست فرد $a$ است. معلم این کلاس برای آشنا شدن با دانش‌آموزان خود هر بار دو نفر از دانش‌آموزان را انتخاب می‌کند و از آن‌ها می‌پرسد که آیا با یکدیگر دوست هستند یا خیر. 
معلم کلاس با حداقل چند سوال می‌تواند رابطه‌های دوستی در کلاس را به طور کامل کشف کند؟


  - ۱۹۹۰۰
  - ۱۰۰۰۰
  - ۹۹۰۰
  - ۵۰۵۰
  - ۴۹۵۰


<پاسخ>
 گزینه‌ی ۳ درست است.

اگر $2n$ دانش‌آموز داشته باشیم ($n$ زوج رابطه‌ی دوستی)، آن‌گاه جواب $n(n-1)$ می‌شود. برای به دست آوردن رابطه‌ها بعد از این تعداد حرکت معلم باید با پرسیدن یک فرد با
$2n-2$
 دوست او را بیابد (یا یکی از آن $2n-2$ فرد دوست اوست یا فرد باقی‌مانده) و بقیه‌ی $n-1$ جفت را بصورت بازگشتی بیابد. برای اثبات بهینگی هم فرض کنید جواب‌ها تا زمانی که ممکن است منفی باشد. آن گاه هرگاه معلم جواب را بیابد‏، به ازای هر دو جفت دوستی باید دو سوال پرسیده باشد وگرنه راه دیگری برای جفت کردن دانش آموزان وجود دارد از تعداد جفت ها در $n$ تا و تعداد حالت های انتخاب ۲ تا از آن‌ها
 $n(n-1)/2$
است که با توجه به ضربدر نهایی حداقل $n(n-1)$ پرسش لازم است.
</پاسخ>

  * [[سوال ۱۴|سوال بعد]]
  * [[سوال ۱۲|سوال قبل]]