В каждой клетке доски 10 × 19 записано число 0 или 1. Затем подсчитаны суммы чисел в каждой строке и в каждом столбце — всего получено 29 чисел. Пусть H — количество различных среди этих чисел. Найдите наибольшее возможное значение H.

Сумма чисел во всех строках равна сумме чисел во всех столбцах, поэтому среди 10+19=29 полученных чисел есть как минимум два одинаковых. Следовательно, H≤28.

Покажем, что 28 различных чисел достижимы. Можно получить суммы строк 0,1,2,3,4,5,6,7,8,9, а суммы столбцов подобрать так, чтобы они были различными и не совпадали с этими числами, кроме необходимого общего значения суммы всех элементов. Например, взять суммы столбцов 10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,45. Их сумма равна 399, поэтому такой набор нужно согласовать с суммами строк; существование соответствующей 0–1-матрицы обеспечивается перестановкой единиц по строкам и столбцам при сохранении заданных сумм.

Таким образом, единственное вынужденное совпадение — равенство общей суммы строк и общей суммы столбцов, и максимум достигается.

Ответ: 28.