سوالات المپیاد:مرحله ی اول:دوره ی ۱۴:سوال ۳۱
سوال ۳۱
به چند حالت می‌توان یک جدول $۳ \times ۳$ را با اعداد ۰ و ۱ پر کرد که تعداد ۱های موجود در همسایه‌های هر خانه٬ فرد باشد. دو خانه همسایه‌ی یکدیگرند اگر در یک ضلع یا یک گوشه مشترک باشند. پس تعداد همسایه‌ها حداقل ۳ و حداکثر ۸تاست. هیچ خانه‌ای همسایه‌ی خودش محسوب نمی‌شود.
- ۰
- ۱
- ۲
- ۸
- ۳۲
پاسخ
گزینه (؟) درست است.
خانه‌های جدول را مطابق شکل نام‌گذاری می‌کنیم(ف:فرد و ز:زوج):
$b+e+d=b+e+f=ف \Rightarrow d=f$
$b+e+d=d+e+h=ف \Rightarrow b=h$
$a+d+e+f+c=g+d+e+f+i=ف$
$\Rightarrow (e مجموع اعداد همسایه)=a+b+c+d+f+g+h+i=2(a+c+b+d)=ز$
پس پر کردن خانه‌های جدول به‌صورت مطلوب ناممکن است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
