Имеется таблица 100х100, все клетки которой изначально пусты. Двое играют в следующую игру. За один ход можно написать в любую незанятую клетку таблицу любое натуральное число от 1 до 100000, если такого числа еще нет в таблице. Игроки записывают, пока не заполнят всю таблицу. После этого подсчитывается суммы чисел в каждом из столбцов. Пусть A - наибольшая из сумм чисел в строках, а B - наибольшая из сумм чисел в столбцах. Первый игрок выигрывает если A > B, иначе выигрывает второй. Кто из игроков сможет выиграть незавсисмо от игры соперника?

задан 10 Дек '16 1:34

10|600 символов нужно символов осталось
1

Пусть $%n$% -- чётное натуральное число, и мы играем для таблицы $%n\times n$% (в данном случае $%n=100$%). Дано также чётное число $%N\ge n^2$% (здесь это $%N=10^5$%). Покажем, как второй может выиграть, добившись выполнения неравенства $%A\le B$%. Для этого ему достаточно сделать так, чтобы суммы чисел во всех строках оказались равными. При этом значение сумм будет равно $%A$%, и тогда сумма всех чисел таблицы окажется равна $%nA$%. Ясно, что при этом найдётся столбец, сумма чисел в котором будет не меньше $%nA/n=A$%, то есть $%B\ge A$%.

Разобьём все числа каждой строки на пары, что возможно ввиду чётности $%n$% (например, покроем их горизонтальными плитками $%1\times2$%, где клетки одной и той же плитки образуют пару). Далее, каждому натуральному числу $%k\le N$% сопоставим парное, равное $%N+1-k$%. Парные числа в сумме дают нечётное число $%N+1$%, поэтому не могут быть равны.

Стратегия второго состоит в том, чтобы в ответ на ход первого вписывать парное число в парную клетку. Тогда в каждой паре (плитке) сумма чисел равна $%N+1$%, и в каждой строке сумма чисел будет равна $%A=(N+1)\frac{n}2$%, что и требовалось.

ссылка

отвечен 10 Дек '16 8:30

@falcao - а для нечетного числа n?

(10 Дек '16 19:39) Даниил Ребянин

@Даниил Ребянин: для нечётного в условии стоит неравенство A>=B (сегодня такой вопрос был). Там идея почти такая же, но побеждает первый. В центр таблицы пишем максимальное число, а потом разбиваем на пары сами числа кроме последнего, числа средней строки, и числа всех столбцов без средней строки. Первый в ответ на ходы второго пишет симметричные числа в симметричные клетки. Сумма по средней строке будет равна сумме по среднему столбцу, а в остальных столбцах она будет меньше.

(10 Дек '16 20:45) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×78

задан
10 Дек '16 1:34

показан
2637 раз

обновлен
10 Дек '16 20:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru