المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:تئوری:سوال ۱۱

پوشاندن چنبره

یک چنبره، یک جدول $m\times n$ است که دو ضلع عمودیش به هم وصل باشند و همچنین دو ضلع افقیش هم به هم وصل باشند. می‌خواهیم یک چنبره را با کاشی‌هایی ۵ خانه‌ای به شکل به‌علاوه (یک خانه وسط و چهار خانه کنار) به طور کامل بپوشانیم. توجه کنید که مثلا اگر در یک جدول $5\times 5$ یک کاشی را طوری بگذاریم که خانه وسط آن بر روی خانه $(1,1)$‌ واقع شود، خانه‌های دیگر آن، خانه‌های $(1,5)،(2,1)،(1,2)$ و $(5,1)$ از جدول را خواهد پوشاند که این خاصیت با توجه به چسبیدن ضلع‌های افقی چنبره به هم و هم‌چنین چسبیدن ضلع‌های عمودی آن به هم، واضح است این گزاره را ثابت یا رد کنید: «شرط لازم و کافی برای انجام این کار آن است که $m$‌ و $n$ مضرب ۵ باشند».

پاسخ

گزاره گفته شده درست است. اثبات کافی بودن که بدیهی است: به راحتی می‌توان یک شکل $5\times 5$ طراحی کرد که به صورت پازل بتوان آن را کنار هم قرار داد تا هر شکل $5k\times 5k'$ پوشانده شود. اما برای اثبات لزوم، اولا چون مساحت هر کاشی ۵ است و ۵ عددی اول است، حتما باید یکی از دو ضلع چنبره به ۵ بخش‌پذیر باشد. حال فرض خلف را در نظر بگیرید: یک چنبره $5k\times l$ که $l$ مضرب ۵ نیست به صورت کامل فرش شده است. تعداد کاشی‌ها $kl$ تا است، بنابراین در هر سطر به طور متوسط $kl/5k=l/5$ مرکز کاشی قرار می‌گیرد (منظور از مرکز کاشی خانه وسطی کاشی است). چون $l$ مضرب ۵ نیست حتما سطری وجود دارد که تعداد مرکز کاشی‌هایی که روی آن قرار دارند از $l/5$ کم‌تر باشد. حال اگر دقت کنید به ازای هر مرکز کاشی که در یک سطر قرار دارد، دقیقا ۳ خانه از آن سطر توسط آن کاشی پوشیده می‌شود. پس کم‌تر از $3l/5$ خانه‌های این سطر با کاشی‌هایی که مرکزشان روی همین سطر قرار دارند پوشیده شده است، یعنی بیش از $2l/5$ خانه‌ها توسط کاشی‌هایی پوشیده شده‌اند که مرکز آن‌ها در یکی از دو سطر مجاور قرار دارد. با کمی دقت خواهید فهمید که چون دو انتهای این سطر به هم وصل‌اند (در واقع یک دور است) می‌توان ۳ خانه مجاور یافت که توسط کاشی‌هایی که مرکز آن‌ها در این سطر نیست پوشیده شده باشند. با کمی دقت بیش‌تر خواهید فهمید که حداکثر دو خانه مجاور در یک سطر می‌توانند توسط کاشی‌هایی پوشیده شوند که مرکز آن‌ها در سطر‌های مجاور است و این یک تناقض است.


ابزار صفحه