Навчання / Бібліотека / Комбінаторика

Вимушений прямокутник

КомбінаторикаСкладне

Кожну клітинку сітки з $3$ рядками і $n$ стовпцями пофарбовано в червоний або синій колір. Прямокутник монохромний, якщо його $4$ кутові клітинки, взяті з $2$ різних рядків і $2$ різних стовпців, мають однаковий колір. Яке найменше $n$ таке, що кожне фарбування мусить містити монохромний прямокутник?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

У кожному стовпці є $2$ клітинки одного кольору; познач стовпці тим, які рядки збігаються і якого кольору.

Розв’язок

Стовпець має $3$ клітинки і $2$ кольори, тож деякі клітинки стовпця мають однаковий колір.
Познач стовпець парою його рядків, що збігаються, і їхнім кольором; є $3$ пари рядків і $2$ кольори, тобто $6$ позначок.
Якщо $2$ стовпці отримали однакову позначку, $4$ кути утворюють монохромний прямокутник, тож $7$ стовпців змушують позначку повторитися.
Для $6$ стовпців позначки можуть бути всі різні, наприклад зі стовпцями $RRB$ , $BBR$ , $RBR$ , $BRB$ , $BRR$ і $RBB$ , кожен з яких має рівно одну пару однакових клітинок, і прямокутник не виникає.
Отже, найменше $n$ дорівнює $7$ .

Відповідь: $7$

Наступна задача Назад до бібліотеки