المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۵ و ۲۶

امین می خواهد کف اتاق خود را که به شکل شش ضلعی است٬ کاشی کاری کند. پدر امین کف اتاق و کاشی ها را مثلث بندی کرده و از او می خواهد طوری کاشی کاری کند که مثلث های کاشی ها و کف اتاق دقیقا روی هم قرار بگیرند. امین برای این کار تنها یک نوع کاشی در اختیار خواهد داشت و نمی تواند کاشی ها را بشکند. شکل مثلث بندی شده‌ي روبه‌رو کف اتاق امین را نشان می دهد.

با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:

سوال ۲۵

امین به چند طریق می‌تواند با کاشی هایی به شکل کف اتاق خود را بپوشاند؟

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

پاسخ

گزینه‌ی «۴» درست است.

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

برای مثال با حالت بندی روی خانه‌های وسطی آن‌هارا به سه طریق می‌توان قرار داد با دو کاشی پر کرد و به ازای هر طریق بقیه جدول را به ۳ طریق می‌توان پر کرد پس در کل ۹ حالت داریم. و اما حالاتی که یک کاشی یکی از خانه‌های وسطی را با یکی از خانه‌های دوری پر کند، برخی از خانه طوری می‌شوند که دیگر نمی‌توان آن‌هارا با کاشی پر کرد در نتیجه جواب همان ۹ حالت است.

سوال ۲۶

امین به چند طریق می تواند با کاشی هایی به شکل کف اتاق خود را بپوشاند؟

  1. ۱۳۶
  2. ۱۰۰
  3. ۷۸۴
  4. ۷۶۸
  5. ۸۵۶

پاسخ

گزینه‌ی «۳» درست است.

این سوال نیز حالت بندی است. با این تفاوت که باید خانه‌هارا یکی در میان سیاه و سفید کنید طوری که خانه های مجاور هر مثلث رنگ مخالف آن باشند. حال می‌بینید که خانه‌های سیاه و سفید به صورت قرینه هم قرار دارند و هر کاشی دقیقا خانه‌های یک رنگ را پر می‌کند، پس به هر تعداد روشی که بتوان خانه‌های سیاه را پر کرد، خانه های سفید را نیز می‌توان پس می‌شود تعداد روش های پرکردن خانه‌های سیاه به توان 2. اما پر کردن همین خانه‌ها هم کار راحتی نیست، از این رو در این سوال با توجه به گزینه‌ها که تنها 2 گزینه هستند که مربع یک عدد هستند که یکی 100 است و دیگری 784. اما با کمی بررسی در می‌یابید که تعداد روش های پرکردن خانه‌های سیاه بیش‌تر از 10 است، پس جواب 784 است.


ابزار صفحه