сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Трех­цвет­ный пря­мо­уголь­ный пазл раз­ме­ра 25 × 50 со­сто­ит из квад­рат­ных эле­мен­тов еди­нич­ной пло­ща­ди. Каж­дый эле­мент имеет либо белый, либо синий, либо крас­ный цвет. Будем го­во­рить, что квад­ра­ты гра­ни­чат друг с дру­гом, если у них есть хотя бы одна общая точка. (Таким об­ра­зом, любой квад­рат может гра­ни­чить с не более чем 8 со­се­дя­ми). И белые, и крас­ные эле­мен­ты могут гра­ни­чить толь­ко с си­ни­ми. Опре­де­ли­те, какое мак­си­маль­ное ко­ли­че­ство белых эле­мен­тов может быть в пазле?

Спрятать решение

Ре­ше­ние.

Белые и крас­ные де­та­ли по гра­нич­ным свой­ствам оди­на­ко­вы  — они могут гра­ни­чить толь­ко с си­ни­ми. За­ме­тим, что в квад­ра­те 2 × 2 может быть не более 1 белой/крас­ной де­та­ли. Сле­до­ва­тель­но, в об­ла­сти 24 × 50 может быть не более 300 белых/крас­ных де­та­лей. Также в пря­мо­уголь­ни­ке 1 × 2 может быть не более 1 белой/крас­ной де­та­ли. От­сю­да по­лу­ча­ем, что в по­ло­се 1 × 50 может быть не более 25 белых/крас­ных. По­это­му во всей об­ла­сти 25 × 50 может быть не более 300 плюс 25=325 белых/крас­ных де­та­лей.

По­сколь­ку пазл трех­цвет­ный, то в нем долж­на быть де­таль каж­до­го цвета, т. е. крас­ная де­таль долж­на быть хотя бы одна. Сле­до­ва­тель­но, белых может быть не более 324.

При­ве­дем при­мер, как можно рас­ста­вить 324 белых де­та­ли, удо­вле­тво­ряя гра­нич­ным усло­ви­ям. Про­ну­ме­ру­ем стро­ки от 1 до 25 и столб­цы от 1 до 50. По­ста­вим белые на пе­ре­се­че­нии не­чет­ных строк и не­чет­ных столб­цов, кроме пер­во­го пе­ре­се­че­ния (пер­вой стро­ки и пер­во­го столб­ца); крас­ный эле­мент по­ста­вим на пе­ре­се­че­нии пер­вой стро­ки и пер­во­го столб­ца. Всё осталь­ное за­пол­ним си­ни­ми эле­мен­та­ми.

 

Ответ: 324.