المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۳:سوال ۷

فهرست مندرجات

سوالات ۷ تا ۸

در بازی شکرز، یک جدول $n × n$ داریم، که در ابتدا روی یک خانە ی آن مهره‌ای سفید، و روی برخی دیگر از خانه‌ها مهره‌ای سیاه قرار دارد. در هر مرحله، مهره‌ی سفید می‌تواند به یک خانه‌ی خالی هم‌سطر یا هم‌ستون برود، ِ بە شرط آن که در مسیرِ مستقیم خانه‌ی فعل̞ی مهره‌ی سفید تا خانه‌ی مقصد، دقیقا یک مهره‌ی سیاه قرار داشته باشد. پس از حرکت مهره‌ی سفید مهره‌ی سیاهی که از روی آن پریده شده، حذف می‌شود. می‌خواهیم در ابتدا، بیش‌ترین تعداد مهره‌ی سیاه را روی جدول قرار دهیم، طوری که بتوانیم با تعدادی مرحله همه‌ی مهره‌های سیاه را از جدول حذف کنیم.

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

سوال ۷

بیش‌ترین تعداد مهره‌ی سیاه بە ازای ۳ = $n$ چه‌قدر است؟

  1. ۶
  2. ۷
  3. ۳
  4. ۴
  5. ۵

راهنمایی

به ازای هر خانه بررسی کنید اگر مهره‌ی سفید در این خانه باشد، با انجام دقیقاً یک حرکت، امکان رفتن به کدام خانه(ها) را دارد؟

راهنمایی

اگر مهره‌ی سفید در خانه‌ی مرکز جدول باشد، نمی‌تواند به خانه‌ی دیگری برود.

راهنمایی

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

راهنمایی

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

سوال ۸

بیش ترین تعداد مهرە ی سیاه بە ازای ۴ = $n$ چە قدر است؟

  1. ۶
  2. ۴
  3. ۵
  4. ۳
  5. ۷

راهنمایی

نمی‌توانیم مهره‌ی سیاهی روی خانه‌های گوشه‌ی جدول قرار دهیم؛ زیرا مهره‌ی سیاهی که در خانه‌های گوشه باشد، برداشته نمی‌شود.
شرایط و محدودیت‌های قرار دادن مهره‌ی سیاه روی خانه‌های وسط اضلاع جدول و خانه‌های مرکز جدول را بررسی کنید.


ابزار صفحه