المپدیا

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

ابزار کاربر

ابزار سایت


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

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:سوال_۱۷ [2018/12/18 08:51] (فعلی)
Hamidreza seydi ایجاد شد
خط 1: خط 1:
 +====== سوال ۱۷ ======
 +
 +
 +شکل زیر، یک جدول $5 \times 5$ با حذف چهار گوشه‌ی آن است. ​
 +می‌خواهیم این شکل را به طور کامل با کاشی‌های
 +$1 \times 1$، $2 \times 2$ و 
 +$3 \times 3$
 +بپوشانیم، طوری که
 +کاشی‌ها روی هم قرار نگرفته و از جدول بیرون نزنند. نیازی نیست از هر سه نوع کاشی استفاده کنیم. حداقل تعداد کاشی‌ها برای انجام این کار چیست؟
 +
 +{{ :​سوالات_المپیاد:​مرحله‌ی_اول:​دوره‌ی_۲۸:​untitled13.png |}}
 +
 +
 +
 +  - ۹
 +  - ۱۰
 +  - ۱۱
 +  - ۱۲
 +  - ۱۳
 +
 +
 +<​پاسخ>​
 + ​گزینه‌ی ۱ درست است.
 +
 +
 +روش پرکردن با  ۹ کاشی:
 +
 +
 +
 +
 +
 +{{ :​سوالات_المپیاد:​مرحله‌ی_اول:​دوره‌ی_۲۸:​untitled14.png |}}
 +
 +
 +
 +حال ثابت می‌کنیم با کم‌تر از ۹ کاشی امکان پر کردن جدول وجود ندارد. حداکثر یک کاشی $3 \times 3$ می‌توانیم داشته باشیم. اگر کاشی $3 \times 3$ نداشته باشیم، هر کاشی حداکثر یک خانه‌ی مشخص شده در شکل زیر را می‌پوشاند و دست کم به ۹ کاشی نیاز داریم:
 +
 +
 +
 +{{ :​سوالات_المپیاد:​مرحله‌ی_اول:​دوره‌ی_۲۸:​untitled15.png |}}
 +
 +
 +
 +اگر کاشی $3 \times 3$ داشته باشیم و این کاشی در وسط جدول باشد، بقیه‌ی جدول باید با کاشی‌های
 +$1 \times 1$ پر شوند که دست کم به ۱۳ کاشی نیاز داریم. اگر هم کاشی ​
 +$3 \times 3$
 +داشته باشیم ولی در وسط جدول نباشد، شش خانه به طور یکتا با
 +$1 \times 1$
 +پر می‌شوند و یک جدول
 +$2 \times 3$
 +می‌ماند که خودش دست کم به سه کاشی نیاز دارد. پس این حالت نیز دست کم
 +$1+6+3=10$
 +می‌خواهد.
 +
 +
 +</​پاسخ>​
 +
 +  * [[سوال ۱۶|سوال قبل]]
 +  * [[سوال ۱۸|سوال بعد]]
  

ابزار صفحه