المپدیا

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

ابزار کاربر

ابزار سایت


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

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

کف یک سالن به صورت جدول $۳\times ۳$ و یا $۴\times ۴$ از موزاییک‌هایی پوشیده شده که روی هریک از آن‌ها عدد ۰ و یا ۱ نوشته شده است. پنج روبات داریم که یکی از آن‌ها دروغ‌گو و سایرین راست‌گو هستند.

ابتدا روبات دلخواهی را روی یکی از موزاییک‌ها (به دلخواه) می‌گذاریم و آن را روشن می‌کنیم. روبات هر بار عدد موزاییکی را که روی آن قرار دارد اعلام می‌کند و سپس به یکی از موزاییک‌های مجاور (که با آن ضلع مشترکی دارند) می‌رود. مسیر حرکت روبات توسط خودش تعیین می‌شود اما طوری حرکت می‌کند که روی هر موزاییک دقیقا یک‌ بار قرار گیرد و پس از اعلام عدد همه‌ي موزاییک‌ها متوقف می‌شود. همین فرآیند را برای روبات‌های دیگر٬ یکی پس از دیگری٬ انجام می‌دهیم.

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

سوال ۲۴

ابتدا در یک سالن $۳\times ۳$ فرآیند بالا را انجام داده و عددهای اعلام شده توسط هر روبات را به ترتیب (از چپ به راست) در پنج گزینه‌ی زیر آورده‌ایم. می‌دانیم روبات‌های راست‌گو همواره عدد نوشته شده روی موزاییک‌ها را به درستی اعلام می‌کنند٬ اما روبات دروغ‌گو عدد حداقل یک موزاییک را نادرست می‌گوید. کدام گزینه مربوط به روبات دروغ‌گو می‌باشد؟

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

پاسخ

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

فرض می‌کنیم جدول را شطرنجی رنگ کرده‌ایم. در جایگاه‌های فرد ربات‌ها در یک رنگ و در جایگاه‌های زوج در رنگ دیگر هستند. اگر تعداد یک‌های خانه‌های هم‌رنگ در یک گزینه با بقیه گزینه‌ها متفاوت باشد آن ربات دروغ‌گو خواهد بود:

  1. ۴و۲
  2. ۴و۲
  3. ۴و۲
  4. ۴و۲
  5. ۳و۳

پس گزینه‌ی (۵) دروغ است.

سوال ۲۵

فرآیند سوال قبل را در یک سالن $۴\times ۴$ اجرا کرده‌ایم. این بار کدام گزینه٬‌ اعداد اعلام شده توسط روبات دروغ‌گو است؟

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

پاسخ

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

تعداد یک‌ها در گزینه‌ی ۲ با بقیه فرق دارد. در نتیجه گزینه‌ی ۲ دروغ است.

سوال ۲۶

فرآیند سوال قبل را در یک سالن $۴\times ۴$ دیگر اجرا کرده‌ایم. این بار کدام گزینه٬‌ اعداد اعلام شده توسط روبات دروغ‌گو است؟

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

پاسخ

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

همانند سوال ۲۴ عمل می‌کنیم. بازهم تعداد یک‌های جایگاه‌های فرد و زوج را با بقیه گزینه‌ها مقایسه می‌کنیم تا گزینه‌ی دروغ مشخص شود:

  1. ۳و۱
  2. ۰و۴
  3. ۴و۰
  4. ۴و۰
  5. ۰و۴

پس گزینه‌ی (۱)دروغ است.


ابزار صفحه