المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

به چند طریق می‌توان برخی از خانه‌های یک جدول $5 \times 5$ را علامت زد، به طوری که در هر زیر‌جدول $2 \times 4$ و $4 \times 2$ دقیقاً یک خانه علامت‌دار و در هر زیرجدول $3 \times 3$ حداقل یک خانه علامت‌دار وجود داشته باشد.

  1. ۹
  2. ۰
  3. ۱
  4. ۸
  5. ۴

راهنمایی

ابتدا سعی کنید یک علامت‌گذاری مطلوب بیابید.

راهنمایی

در راستای راهنمایی اول، خانه‌ی میانه‌ی جدول (سطر سوم، ستون سوم) را علامت بگذارید.

راهنمایی

در راستای راهنمایی دوم، با توجه به شرط زیر‌جدول‌های ۲×۴ و ۴×۲، تنها خانه‌هایی که می‌توانید علامت بزنید را بیابید.

راهنمایی

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

راهنمایی

نشان دهید در هیچ علامت گذاری مطلوبی همسایه‌ی راسی‌ای از خانه‌ی میانی جدول علامت نخواهد خورد.

راهنمایی

در راستای راهنمایی قبل، از برهان خلف استفاده کنید و سعی کنید مربع ۳×۳ ای بیابید که نتوان هیچ خانه‌ای از آن را علامت گذاری کرد.

راهنمایی

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


ابزار صفحه