المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوالات ۲۴ و ۲۵ و ۲۶

سوالات ۲۴ و ۲۵ و ۲۶

  • موزاییک‌های از انواع زیر وجود دارند:

منظور از فرش کردن یک صفحه با موزاییک‌ها پوشاندن تمام خانه‌های صفحه با موزاییک‌ها است. به طوری که موزاییک‌ها روی هم قرار نگیرند.

سوال ۲۴

آیا با موزاییک‌هایی از نوع ۱ می‌توان یک صفحه شطرنجی $6\times6$ را فرش کرد؟

پاسخ

صفحه‌ی $6\times6$ را به شکل مقابل رنگ‌بندی می‌کنیم٬ معلوم است که هر موزاییکی از نوع ۱ یا ۳ خانه‌ی سفید و یک خانه‌ی سیاه را و یا ۳ خانه‌ی سیاه و یک خانه‌ی سفید را پوشانده است. بنابراین به خاطر مساوی بودن تعداد خانه‌های سفید و سیاه لازم است تعداد موزاییک‌ّهایی که ۳ خانه‌ی سفید و ۱ خانه‌ی سیاه را پوشش می‌دهند با تعداد موزاییک‌هایی که سه خانه سیاه و یک خانه‌ سفید را پوشش می‌دهند برابر باشند که چنین امری محال است٬ چون تعدا کل موزاییک‌ها ۹ عدد می‌باشد.

سوال ۲۵

آیا با موزاییک‌هایی از نوع ۲ می‌توان یک صفحه شطرنجی $6\times6$ را فرش کرد؟

پاسخ

اگر صفحه‌ی $6\times6$ را به صورت شطرنجی رنگ‌بندی کنیم و مثل استدلال سوال قبل عمل کنیم معلوم خواهد شد که فرش‌بندی صفحه‌ی $6\times6$ با موزاییک‌هایی از نوع ۲ نیز غیر ممکن است.

سوال ۲۶

آیا با موزاییک‌هایی از نوع ۲ می‌توان یک صفحه شطرنجی $100\times100$ را فرش کرد؟

پاسخ

اگر چون مربع $4\times4$ را می‌توان با موزاییک از نوع ۲ فرش کرد پس با کنار هم گذاشتن ۶۲۵ عدد از این مربع‌های $4\times4$ می‌توان صفحه‌ی شطرنجی $100\times100$ را به‌دست آورد.


ابزار صفحه