المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

آقای جیم به یک جدول ‎$14\times 14$‎ خانه‌ای که یک زیرجدول ‎$3\times 3$‎ خانه‌ای از آن رنگ شده باشد، یک جدول جادویی می‌گوید. با این تعریف، «جادویی کردن»‎ یک جدول ‎$14 \times 14$‎ کاملاً تمیز یعنی انتخاب یک زیرجدول ‎$3\times 3$‎ از آن و رنگ کردن آن زیرجدول.

در ابتدا، آقای جیم تعداد بسیار زیادی جدول ‎$14\times 14$‎ کاملاً تمیز دارد و می‌خواهد تمام جداول جادویی مختلف ممکن را با استفاده از آن‌ها بسازد. او هر روز می‌تواند تعدادی از این جدول‌ها را انتخاب کرده و جادویی کند؛ منتها به‌ازای هر دو جدول ‎$A$‎ و ‎$B$‎ که در یک روز جادویی می‌شوند، اگر جدول ‎$A$‎ را دقیقاً روی جدول ‎$B$‎ قرار دهیم، باید حتماً حداقل یکی از ‎۹‎ خانه‌ی رنگ‌شده‌ی ‎$A$‎ روی یکی از ‎۹‎ خانه‌ی رنگ‌شده‌ی ‎$B$‎ بیافتد.

آقای جیم حداقل چند روز برای ساختن تمام جدول‌های جادویی ممکن لازم دارد؟ چرا؟


ابزار صفحه