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


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

В клет­ки таб­ли­цы n × n (n > 3) впи­са­ны числа 0 и 1 так, что в клет­ках каж­до­го квад­ра­та 2 × 2 стоит ровно три оди­на­ко­вых числа. Какое мак­си­маль­ное зна­че­ние может при­ни­мать сумма всех чисел в этой таб­ли­це?

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

Ре­ше­ние.

Оче­вид­но, что если k  — ми­ни­маль­но воз­мож­ное число нулей в таб­ли­це, то ис­ко­мая сумма до­сти­га­ет мак­си­му­ма, рав­но­го числу n в квад­ра­те минус k.

В любой таб­ли­це n \times n можно вы­де­лить  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те не­пе­ре­се­ка­ю­щих­ся 2 \times 2 квад­ра­тов, где через  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка обо­зна­че­на целая часть числа  дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби  левая круг­лая скоб­ка левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка = дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби , если n четно;  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка = дробь: чис­ли­тель: n минус 1, зна­ме­на­тель: 2 конец дроби , если n не­чет­но). В каж­дом таком 2 \times 2 квад­ра­те со­дер­жит­ся либо три нуля, либо один нуль, то есть не менее од­но­го нуля. Тогда во всей таб­ли­це n × n най­дет­ся не менее  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те нулей, а зна­чит ис­ко­мое число k= левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те . При­ве­дем при­мер таб­ли­цы n \times n с ми­ни­маль­ным чис­лом нулей, рав­ным  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те .

 

1111...
1010
1111
1010
...

 

В при­ве­ден­ной таб­ли­це нули на­хо­дят­ся лишь на пе­ре­се­че­нии стро­ки и столб­ца с чет­ны­ми но­ме­ра­ми.

Таким об­ра­зом, мак­си­маль­ное зна­че­ние суммы всех чисел в таб­ли­це равно n в квад­ра­те минус левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те .

 

Ответ: n в квад­ра­те минус левая квад­рат­ная скоб­ка дробь: чис­ли­тель: n, зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка в квад­ра­те .