Имеется таблица 100 × 100, все клетки которой изначально пусты. двое играют в следующую игру. за один ход можно записать в любую незанятую клетку таблицы любое нату- ральное число от 1 до 10 000, если такого числа еще нет в таблице. игроки записывают числа, пока не заполнят всю таблицу. пусть a — количество строк, в каждой из которых сумма чисел делится на 10 000, а b — количество столбцов, в каждом из которых сумма чисел делится на 10 000. пер- вый игрок выигрывает, если a > b, иначе выигрывает вто- рой. кто из игроков сможет выиграть независимо от игры соперника?

Пусть nn -- чётное натуральное число, и мы играем для таблицы n×nn×n (в данном случае n=100n=100). Дано также чётное число N≥n2N≥n2 (здесь это N=105N=105). Покажем, как второй может выиграть, добившись выполнения неравенства A≤BA≤B. Для этого ему достаточно сделать так, чтобы суммы чисел во всех строках оказались равными. При этом значение сумм будет равно AA, и тогда сумма всех чисел таблицы окажется равна nAnA. Ясно, что при этом найдётся столбец, сумма чисел в котором будет не меньше nA/n=AnA/n=A, то есть B≥AB≥A.

Разобьём все числа каждой строки на пары, что возможно ввиду чётности nn (например, покроем их горизонтальными плитками 1×21×2, где клетки одной и той же плитки образуют пару). Далее, каждому натуральному числу k≤Nk≤N сопоставим парное, равное N+1−kN+1−k. Парные числа в сумме дают нечётное число N+1N+1, поэтому не могут быть равны.

Стратегия второго состоит в том, чтобы в ответ на ход первого вписывать парное число в парную клетку. Тогда в каждой паре (плитке) сумма чисел равна N+1N+1, и в каждой строке сумма чисел будет равна A=(N+1)n2A=(N+1)n2, что и требовалось.