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


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

Тaблицa 7 на 7 зaпол­ненa ну­ля­ми. Зa одну оперaцию в тaблице нaхо­дит­ся минимaльное число (если тaких не­сколь­ко выбирaется любое) и к нему, a тaкже ко всем числaм, сто­я­щим в со­сед­них с ним по сто­ро­не или углу клеткaх, добaвля­ет­ся еди­ницa. Кaкое нaиболь­шее число может окaзaться в одной из кле­ток тaблицы через 90 оперaций?

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

Ре­ше­ние.

Назовём n-ой фазой не­сколь­ко под­ряд иду­щих опе­ра­ций, ко­то­рый при ме­ня­ют­ся к чис­лам, рав­ным n. Если таких опе­ра­ций не было, будем го­во­рить, что дан­ная фаза со­сто­ит из нуля опе­ра­ций. На­чи­на­ет­ся всё с ну­ле­вой фазы.

В те­че­ние одной фазы ни­ка­кое число не может уве­ли­чит­ся боль­ше, чем на 4. Дей­стви­тель­но, если мы уве­ли­чи­ли само число, то ни к нему, ни к его со­се­дя м не может быть при­ме­не­на наша опе­ра­ция в те­че­ние этой фазы ни до, не после, по­сколь­ку число, уве­ли­чен­ное на один в не­ко­то­рой фазе, не может ока­зать­ся ми­ни­маль­ным в те­че­ние той же самой фазы. Среди со­се­дей числа можно вы­брать не боль­ше 4 не со­сед­них между собой, зна­чит, дей­стви­тель­но мы можем уве­ли­чить число не боль­ше, чем на 4 за одну фазу.

Рас­смот­рим пер­вые, четвёртые и седь­мые клет­ки в пер­вой, четвёртой и седь­мой стро­ках таб­ли­цы, всего 9 штук. За­ме­тим, что ни­ка­кая опе­ра­ция не за­тра­ги­ва­ет две из них. Зна­чит, чтобы сме­ни­лось n фаз, надо со­вер­шить хотя бы 9n опе­ра­ций. Важно! Мы не можем утвер­ждать, что одна фаза длит­ся хотя бы 9 опе­ра­ций, так как не­ко­то­рые из наших чисел могли быть уве­ли­че­ны на преды­ду­щих фазах.

Зна­чит, у нас про­шло не более 10 фаз и в каж­дой ни­ка­кое число не могло уве­ли­чит­ся более, чем на 4. Сле­до­ва­тель­но, за 90 опе­ра­ций ни­ка­кое число не могло стать боль­ше, чем 40.

При­мер стро­ит­ся сле­ду­ю­щим об­ра­зом: рас­смот­рим вто­рые, четвёртые и ше­стые клет­ки во вто­рой, четвёртой и ше­стой стро­ках таб­ли­цы, всего 9 штук. Будем при­ме­нять опе­ра­ции толь­ко к ним. Опе­ра­ции, при­менённые к одной из этих кле­ток, не за­тра­ги­ва­ют осталь­ные 8, и при этом после при­ме­не­ния опе­ра­ций ко в см 9 клет­кам все числа в таб­ли­це уве­ли­чи­ва­ют­ся хотя бы на 1. При этом число в тре­тьей клет­ке тре­тьей стро­ки будет каж­дую фазу уве­ли­чи­вать­ся на 4.

Ра­зу­ме­ет­ся, при­мер не един­ствен­ный.

 

Ответ: 40.