Имеется таблица 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, что и требовалось.