المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوالات ۲۴ و ۲۵ و ۲۶

سوالات ۲۴ و ۲۵ و ۲۶

۱۰۰ انسان و لیستی از نام های ۱۰۰ حیوان وجود دارد. هر انسان نام دقیقا ۱۰ حیوان را می‌داند و نام هر حیوان را دقیقا ۱۰ انسان می‌دانند. هیچ دو انسانی دقیقا ۱۰ نام مشابه را نمی‌دانند.

آنها می‌خواهند نام حیوانات را روی تخته بنویسند و از نوشتن نام های تکراری پرهیز کنند. برای این منظور تعدادی بازی طراحی کرده‌اند.

با توجه به توضیحات بالا به ۳ سوال زیر پاسخ دهید:

سوال ۲۴

در بازی «ننویسی می‌بازی» انسان‌ها در یک صف قرار می‌گیرند و هر کس در نوبت خود نام حیواناتی را که می‌داند و هنوز روی تخته نیستند٬ روی تخته می‌نویسد. هر کس در نوبت خود نتواند نام حیواناتی را به تخته اضافه کند بازنده است.

وقتی نوبت همه انسان‌ها تمام شد تعداد بازنده‌ها چند عدد مختلف می‌تواند باشد؟

  1. ۸۹
  2. ۸۲
  3. ۹۰
  4. ۸۰
  5. ۸۱

راهنمایی

سعی کنید بیشینه و کمینه‌ای برای تعداد افرادی که می‌بازند بدست آورید.

راهنمایی

برای محاسبه‌ی بیشینه‌ی تعداد بازنده‌ها، دقت کنید تمام اسامی می‌بایست توسط برنده‌ها نوشته شود. هر فرد هم حداکثر می‌تواند ۱۰ نام بنویسد. پس حداقل چند برنده نیاز داریم تا تمام اسامی حیوانات نوشته شود؟

راهنمایی

برای محاسبه‌ی کمینه‌ی تعداد بازنده‌ها، دقت کنید نفر اول دقیقا ۱۰ نام پای تخته می‌نویسد.

راهنمایی

در ادامه‌ی راهنمایی پیشین، هر فرد نیز غیر بازنده حداقل یک نام جدید می‌بایست بنویسد.

راهنمایی

برای یافتن مثال‌هایی از تعداد بازنده‌های میان مقادیر کمینه و بیشینه، ابتدا مثالی برای حداقل تعداد بازنده‌ها بیابید و به باقی اعداد تعمیم دهید.

راهنمایی

برای مثال راهنمایی پیشین، فرض کنید نفر $i$ اسامی حیوانات $i, i+1, ..., i+9$ را بداند. (حیوان ۱۰۱ همان حیوان ۱ است.)

پاسخ

گزینه‌ی ۲ درست است.

می‌دانیم حداقل ۱۰ نفر بازنده نمی‌شوند. پس حداکثر ۹۰ نفر بازنده خواهند شد. از طرفی نفر اول نام ۱۰ حیوان را می‌نویسد و هر فرد غیربازنده‌ای نام حداقل یک حیوان را می‌نویسد. پس حداقل ۹ نفر بازنده خواهیم داشت.

تمام اعداد بین ۹ تا ۹۰ قابل دستیابی است و می‌توان مثالی برای هریک یافت. در نتیجه جواب مسئله برابر ۸۲ است.

سوال ۲۵

در بازی «بنویس ولی می بازی» انسان ها در یک صف قرار می گیرند و هر کس در نوبت خود نام حیواناتی را که می داند و هنوز روی تخته نیستند٬ روی تخته می نویسد و اگر حداقل نام یکی از حیواناتی را که می داند قبلا روی تخته نوشته باشند٬ می بازد.

وقتی نوبت همه‌ي انسان ها تمام شد تعداد بازنده ها چند عدد مختلف می تواند باشد؟

  1. ۸۱
  2. ۹۹
  3. ۸۰
  4. ۱۰
  5. ۹۰

راهنمایی

مقدار کمینه و بیشینه‌ای برای تعداد افرادی که می‌برند بیابید.

راهنمایی

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

راهنمایی

هر فرد برنده می‌بایست دقیقا ۱۰ نام جدید روی تخته بنویسد. چون ۱۰۰ نام مختلف وجود دارد حداکثر چند برنده داریم؟

پاسخ

گزینه‌ی ۴ درست است.

یک نفر در صورتی بازنده نیست که بتواند دقیقا نام ۱۰ حیوان مختلف را بنویسد. در نتیجه تعداد افرادی که بازنده نیستند عددی بین ۱ تا ۱۰ خواهد بود. به وضوح تمام حالات نیز با ارائه‌ی مثال قابل دستیابی هستند. در نتیجه جواب مسئله ۱۰ است.

سوال ۲۶

در بازی «ببازی نمی‌نویسی» انسان‌ها در یک صف قرار می‌گیرند و هر کس در نوبت خود اگر حداقل نام یکی از حیواناتی را که می‌داند قبلا روی تخته نوشته باشند، می‌بازد و چیزی روی تخته نمی‌نویسد. در غیر این صورت نام حیواناتی را که می داند روی تخته می نویسد.

وقتی نوبت همه‌ی انسان ها تمام شد٬ تعداد حیوانات روی تخته چند عدد مختلف می‌تواند باشد؟

  1. ۱
  2. ۹۰
  3. ۱۰
  4. ۹۱
  5. ۹

راهنمایی

هر فردی که نامی روی تخته بنویسد، دقیقا ۱۰ نام می‌نویسد.

راهنمایی

پس اگر $k$ نفر نبازند، $10k$ عدد روی تخته نوشته خواهد شد. $k$ چند مقدار متفاوت می‌تواند داشته باشد؟

راهنمایی

دقت کنید نفر اول همواره ۱۰ نام می‌نویسد. پس $1 \le k$

راهنمایی

آیا ممکن است $k=1$ ؟

راهنمایی

دقت کنید که اگر تنها یک نفر ببرد، هر یک از باقی افراد حداقل یکی از ۱۰ اسمی که فرد اول پای تخته نوشته را می‌دانند.

پاسخ

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

هر نفر که نبازد نام دقیقا ۱۰ حیوان را خواهد نوشت. در نتیجه همیشه تعداد حیوانات روی تخته بر ۱۰ بخش‌پذیر است.

ولی می‌دانیم در انتها حالتی که ۱۰ حیوان روی تخته نوشته شده باشد اتفاق نمی‌افتد. چرا که در این صورت ۹۹ نفر بعدی باید نام یکی از ۱۰ حیوان روی تخته را بداند. این بدان معنی است که نام این ۱۰ حیوان حداقل ۱۰۹ بار (۱۰ حیوان برای نفر اول و ۹۹ حیوان برای ۹۹ نفر بعدی) باید آمده باشد که با توجه به شرایط اولیه مسئله ممکن نیست.

پس تعداد حیوانات روی تخته ۹ عدد مختلف می‌تواند باشد. برای هرکدام از این حالات می‌توان مثالی یافت.


ابزار صفحه