Question

Мистер Фокс записал в каждую клетку таблицы 13 x 13 Одно из двух чисел "1" или "-1" таким образом, что строк с отрицательной суммой оказалось больше, чем с положительной. Чему равно наибольшее число столбцов этой таблицы с положительной суммой?

Answer 1

Ответ:

13

Пример:

− − − − − − − + + + + + +

− + + + + + + − − − − − −

+ − − − − − − − + + + + +

− − + + + + + + − − − − −

+ + − − − − − − − + + + +

− − − + + + + + + − − − −

+ + + − − − − − − − + + +

+ + + + + + + + + + + + +

+ + + + + + + + + + + + +

+ + + + + + + + + + + + +

+ + + + + + + + + + + + +

+ + + + + + + + + + + + +

+ + + + + + + + + + + + +

Оценка:

Столбцов 13, значит число столбцов с положительной суммой не более 13.

Answer 2

Предположим, что в таблице сумма каждой строки и каждого столбца представлена в виде 1 или -1. Поскольку количество строк с отрицательной суммой больше, чем строк с положительной суммой, то количество строк с положительной суммой не может быть больше 6 (половина от 13).

Для доказательства этого, рассмотрим следующий аргумент: если бы количество строк с положительной суммой было больше 6, то сумма всех строк была бы положительной, потому что положительная сумма в каждой из 7 строк превышает отрицательную сумму в каждой из оставшихся 6 строк.

Теперь давайте рассмотрим столбцы. В каждом столбце сумма будет равна сумме всех элементов этого столбца. Если количество строк с положительной суммой равно 6 или менее, то для получения наибольшего числа столбцов с положительной суммой мы можем выбрать столбцы, в которых сумма всех элементов положительна, и количество таких столбцов будет равно количеству строк с положительной суммой.

Таким образом, наибольшее число столбцов этой таблицы с положительной суммой равно 6.