المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۸:سوال ۱۷

سوال ۱۷

شکل زیر، یک جدول $5 \times 5$ با حذف چهار گوشه‌ی آن است. می‌خواهیم این شکل را به طور کامل با کاشی‌های $1 \times 1$، $2 \times 2$ و $3 \times 3$ بپوشانیم، طوری که کاشی‌ها روی هم قرار نگرفته و از جدول بیرون نزنند. نیازی نیست از هر سه نوع کاشی استفاده کنیم. حداقل تعداد کاشی‌ها برای انجام این کار چیست؟

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

پاسخ

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

روش پرکردن با ۹ کاشی:

حال ثابت می‌کنیم با کم‌تر از ۹ کاشی امکان پر کردن جدول وجود ندارد. حداکثر یک کاشی $3 \times 3$ می‌توانیم داشته باشیم. اگر کاشی $3 \times 3$ نداشته باشیم، هر کاشی حداکثر یک خانه‌ی مشخص شده در شکل زیر را می‌پوشاند و دست کم به ۹ کاشی نیاز داریم:

اگر کاشی $3 \times 3$ داشته باشیم و این کاشی در وسط جدول باشد، بقیه‌ی جدول باید با کاشی‌های $1 \times 1$ پر شوند که دست کم به ۱۳ کاشی نیاز داریم. اگر هم کاشی $3 \times 3$ داشته باشیم ولی در وسط جدول نباشد، شش خانه به طور یکتا با $1 \times 1$ پر می‌شوند و یک جدول $2 \times 3$ می‌ماند که خودش دست کم به سه کاشی نیاز دارد. پس این حالت نیز دست کم $1+6+3=10$ می‌خواهد.


ابزار صفحه