المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۴:سوالات ۱۳ تا ۱۵

سوالات ۱۳ تا ۱۵

سوال ۱۳

راهنمایی

با توجه به راهنمایی اول سوال $6$، ابتدا سعی کنید با کمترین تعداد حرکتی که می‌توانید، تمام خانه‌های سیاه را پیمایش کنید؛ سپس یک کران پایین مناسب برای تعداد حرکت‌ها بدست آورید.

راهنمایی

برای اثبات کران پایین، دقت کنید که برای اینکه هرکدام از خانه‌های گوشه را ببینیم باید مهره‌ی فیل روی آن خانه قرار بگیرد.(به عبارت دیگر، در مسیر حرکت از خانه‌ای به خانه‌ی دیگر، از خانه‌ی گوشه عبور نمی‌کند.)

راهنمایی

خانه‌های وسط اضلاع هم همینطور!

سوال ۱۴

راهنمایی

دو فیل در دو خانه با رنگ‌های متفاوت نمی‌توانند یکدیگر را تهدید کنند. پس می‌توانیم مسئله را برای خانه‌های سفید و سیاه به طور جداگانه حل کنیم.

راهنمایی

برای اثبات کران بالا، تعداد قطرها را بشمارید.

سوال ۱۵

راهنمایی

طبق راه حل سوال قبل، باید در هر قطر دقیقاً یک مهره قرار بگیرد. اگر خانه‌های گوشه جدول سیاه باشند، باید در خانه‌های سیاه و سفید به ترتیب $7$ و $6$ مهره قرار بگیرد. باز هم می‌توانیم تعداد حالت‌ها را برای خانه‌های هر رنگ به طور مجرا بیابیم و سپس طبق اصل ضرب جواب نهایی را محاسبه کنیم.

راهنمایی

برای شمردن تعداد حالت‌ها برای خانه‌های سیاه، دقت کنید که باید در هر چهار گوشه‌ی جدول مهره قرار بگیرد.

راهنمایی

برای شمردن تعداد حالت‌ها برای خانه‌های سفید، می‌توانید روی $4$ مهره‌ای که باید در خانه‌های کنار گوشه‌ها قرار بگیرند، حالت‌بندی کنید.


ابزار صفحه