المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

سوال ۲۴

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

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

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

پاسخ

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

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

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

سوال ۲۵

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

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

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

پاسخ

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

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

سوال ۲۶

در بازی «ببازی نمی نویسی» انسان ها در یک صف قرار می گیرند و هر کس در نوبت خود اگر حداقل نام یکی از حیواناتی را که می داند قبلا روی تخته نوشته باشند٬ می بازد و چیزی روی تخته $\underline{ نمی نویسد}$. در غیر این صورت نام حیواناتی را که می داند روی تخته می نویسد.

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

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

پاسخ

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

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

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

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


ابزار صفحه