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


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

Ген­зель и Гре­тель иг­ра­ют в игру, Ген­зель ходит пер­вым. Они по оче­ре­ди ста­вят фишки на клет­ча­тую доску 7 × 8 (7 строк и 8 столб­цов). Каж­дый раз, когда Гре­тель ста­вит фишку, она по­лу­ча­ет 4 очка за каж­дую фишку, уже сто­я­щую в той же стро­ке и 3 очка за каж­дую фишку, уже сто­я­щую в том же столб­це.

На одной клет­ке может сто­ять толь­ко одна фишка. Игра за­кан­чи­ва­ет­ся, когда все клет­ки доски за­пол­не­ны.

Какое наи­боль­шее ко­ли­че­ство очков может за­ра­бо­тать Гре­тель вне за­ви­си­мо­сти от дей­ствий Ген­зе­ля?

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

Ре­ше­ние.

Да­вай­те ска­жем, что Ген­зель тоже по­лу­ча­ет очки по тому же прин­ци­пу, что и Гре­тель. В таком слу­чае, каж­дая пара кле­ток в одной стро­ке даст в итоге ка­ко­му-то из иг­ро­ков 4 очка, а каж­дая пара кле­ток в одном столб­це  — 3 очка. В одной стро­ке можно найти  дробь: чис­ли­тель: 8 умно­жить на 7, зна­ме­на­тель: 2 конец дроби =28 пар кле­ток, а в одном столб­це  —  дробь: чис­ли­тель: 7 умно­жить на 6, зна­ме­на­тель: 2 конец дроби =21пару. Общая сумма очков, на­бран­ных обо­и­ми иг­ро­ка­ми в конце игры, будет равна 7 умно­жить на 28 умно­жить на 4 плюс 9 умно­жить на 21 умно­жить на 3=1288.

При­ведём стра­те­гию за Гре­тель, поз­во­ля­ю­щую ей каж­дый ход по­лу­чать на 4 очка боль­ше, чем перед этим Ген­зель. Для этого раз­объём каж­дую стро­ку на 8 пря­мо­уголь­ни­ков 1 × 2. Как толь­ко Ген­зель ста­вит фишку в одну из кле­ток пря­мо­уголь­ни­ка, Гре­тель тут же за­ни­ма­ет вто­рую. Столб­цы, в ко­то­рых на­хо­дят­ся эти клет­ки, иден­тич­ны из-за стра­те­гии Гре­тель, а в стро­ке к мо­мен­ту её хода на­хо­дит­ся на одну фишку боль­ше  — ровно на ту, ко­то­рую по­ста­вил Ген­зель.

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

Каж­дый игрок сде­ла­ет 28 ходов и, при пра­виль­ной игре, Гре­тель наберёт на 112 очков боль­ше. Зная сумму и раз­ность двух чисел, можно легко найти сами числа, это 700 и 588.

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

 

Ответ: 700.