المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

«جدول صفر و یک» به جدولی می‌گوییم که در هر خانه‌ی آن صفر یا یک قرار گرفته است. عملی را تعریف می‌کنیم که از روی یک جدول صفر و یک ۴ × ۴، یک جدول صفر و یک ۴ × ۴ دیگر را به این شکل می‌سازد که هر خانه‌ی جدول جدید برابر حاصل‌ضرب خانه‌های مجاور آن خانه در جدول قدیمی است (خانه مجاور یک خانه، خانه‌ای است که با آن خانه یک ضلع مشترک دارد). برای مثال با دو بار اعمال این عمل روی جدول زیر به «جدول تمام صفر» (جدولی که تمام خانه‌های آن صفر است) می‌رسیم.

تعداد کل جدول‌های صفر و یک ۴ × ۴ که با تکرار این عمل روی آن‌ها به جدول تمام صفر نمی‌رسیم چند تا است؟

  1. ۰
  2. ۱
  3. ۳
  4. ۱۲۰
  5. ۵۱۱

راهنمایی

جدول را به صورت شطرنجی رنگ‌آمیزی کنید و تاثیر عدد خانه‌های همرنگ روی خانه‌های دیگر را بررسی کنید.

راهنمایی

فاصله‌ی دو خانه‌ی صفر از جدول را برابر با مجموع فاصله‌ی سطرهایشان و فاصله‌ی ستون‌هایشان در نظر بگیرید. آیا می‌توان گفت که در هر گام، کمترین فاصله‌ی بین صفر‌های جدول کاهش می‌یابد؟

راهنمایی

در جدول تمام صفر کمترین فاصله‌ی بین صفر‌های جدول چند است؟ با در نظر گرفتن مقدار نهایی و مقدار کاهش یا افزایش این مقدار در هر گام، ساختار جدول اولیه را بررسی کنید.

پاسخ

گزینه‌ی ۵ درست است.

دو حالت شطرنجی صفر و یک حالت مادر هستند که هر یک ۸۲ حالت را در بردارند که یک حالت تمام یک بین آن‌ها مشترک است.


ابزار صفحه