می خواهید یک جدول را چنان رنگ کنیم که بتوان چهار خانه ی سفید متوالی عمودی یا افقی در آن یافت!
از سئوالات المپیاد ریاضی:
معمای المپیادی: چهار خانه سفید متوالی
:: از سئوالات المپیاد ریاضی:
یك
جدول 9×9 از مربعات سفید موجود است. حداكثر مقدار n را بیابید كه اگر به
هر طریق ممكن n تا از خانه های جدول را سیاه كنیم، باز هم در این جدول
بتوان چهار خانه ی سفید متوالی عمودی یا افقی یافت.
الف) 17 ب) 18 ج) 19 د) 20 هـ) 21
[جواب این سوال المپیاد ریاضی را در بخش پاسخ مشاهده نمایید...]
هر
جدول ۴×۴ به وضوح حداقل ۴ خانه ی سياه نياز دارد تا هيچ ۴ خانه ی متوالی
سفيدی در آن يافت نشود . شکل سمت چپ در بالا يک مثال برای ۴ خانه ی سياه
است. همچنين هر سطر يا ستون ۹ تايی برای اين که ۴ خانه ی متوالی سفيد در آن
يافت نشود، حداقل ۲ خانه ی سياه نياز دارد و چون جدول ۹×۹ را میتوان به ۴
جدول ۴×۴ و دو رديف ۹ تايی مانند شکل افراز کرد پس حداقل ۲۰=۲×۲+۴×۴ خانه ی
سياه نياز است تا هيچ ۴ خانه ی سفيد متوالی يافت نشود. شکل بالا نشان
میدهد که ۲۰ خانه ی سياه برای رسيدن به اين هدف کافی هم هست. بنابراين با
حداکثر ۱۹ خانه ی سياه نمی توان اين کار را کرد و حتماً ۴ خانه ی متوالی
سفيد يافت خواهد شد.