Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

امیرمحمد یک جدول 5×5 دارد. او می‌خواهد یکی از 25 خانه‌ی این جدول را حذف کند، و باقی خانه‌های جدول را با 6 قطعه به‌شکل زیر بپوشاند، با این شرط که هر یک از 24 خانه‌ی باقی‌مانده از جدول، توسط دقیقا یک قطعه پوشانده شده باشد. او می‌تواند قبل از قرار دادنِ یک قطعه در جدول، آن را به‌میزان دل‌خواه، دوران یا تقارن دهد. چند خانه از این جدول هستند که امیرمحمد می‌تواند با حذف آن خانه، باقی خانه‌های جدول را با شرایطِ گفته‌شده بپوشاند؟

  1. 1
  2. 4
  3. 5
  4. 8
  5. 9

پاسخ

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

برای 5 تا از حالات، این کار ممکن است که این حالات را در دو شکل زیر می‌بینید. توجه کنید که شکل دوم معادل 4 حالت است، چرا که اگر شکل را دوران دهیم، می‌توانیم ببینیم که همه‌ی 4 گوشه جزو حالات مناسب هستند.

برای اثبات اینکه باقی خانه‌ها مناسب نیستند، از دو رنگ‌آمیزی زیر استفاده می‌کنیم.

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

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


ابزار صفحه