Петя покрасил клетки квадратной доски размером 8 × 8 клеток в два цвета. Вася выбирает цвет, 2 строки и 2 столбца и считает суммарное количество клеток выбранного им цвета в этих строках и столбцах. Какое наибольшее суммарное количество клеток Вася гарантированно может получить, какую бы раскраску не выбрал Петя?
Без ограничения общности пусть клеток чёрного цвета не меньше 32, тогда можно оставить только 32 из них и максимум, естественно, не увеличится. Соответственно, будем решать задачу для ровно 32 чёрных клеток.
Пусть мы можем выбрать две строчки, в которых суммарно n чёрных клеток. Тогда в остальных 6 строках 
чёрных клеток, которые находятся в 8 столбцах из 6 клеток. По принципу Дирихле среди них можно выбрать два столбца, в которых не меньше 
чёрных клеток. Получится не меньше
что строго больше 15, если n хотя бы 10. Следовательно, если можно выбрать две строки/столбца, в которых суммарно не менее 10 чёрных клеток, то можно выбрать крест с не менее, чем 16 чёрными клетками.
Теперь предположим, что в любых двух строчках и любых двух столбцах не более 9 чёрных клеток. Тогда:
1) Не может быть строки или столбца с 6 и более клетками чёрного цвета, так как тогда по принципу Дирихле найдётся строка с 4 и более клетками чёрного цвета.
2) Не может быть двух строк или двух столбцов с 5 чёрными клетками. Следовательно, набор количества чёрных клеток в строках/столбцах может быть либо 54444443, либо 44444444 чёрных клеток, то есть существует не менее 6 строк, в которых ровно 4 чёрных и 4 белых.
Пусть во всех столбцах по 4 чёрных клетки. Рассмотрим три любые строки из 6, в которых по 4 белых клетки. Найдутся две строки, в двух столбцах которых только белые клетки (так как в противном случае белые клетки есть минимум в 4+3+2 = 9 столбцах). Так как в этих столбцах по 4 черных клетки, то суммарно в выбранных строчках и этих столбцах найдутся 16 черных клеток. Аналогично поступим, если во всех строках по 4 черные клетки.
Если же и в строках, и в столбцах количества чёрных клеток равны 54444443, то выберем строчку и столбец, в которых по 5 чёрных клеток, то есть суммарно не менее 9. Среди 7 остальных столбцов есть не менее двух, которые пересекаются с выбранной строкой по белой клетке, и среди этих двух есть не менее одного столбца, в котором ровно 4 чёрных клетки. Точно так же среди остальных 7 строк найдется хотя бы одна такая, в которой ровно 4 чёрных клетки, а с первым выбранным столбцом она пересекается по белой. Выбранная строка может пересечься по чёрной клетке со вторым выбранным столбцом, поэтому она добавит не более чем 3 чёрные клетки. Добавим эти строку и столбец к выбранным. Итого в них не менее 
черных клеток. В итоге мы доказали, что Вася может гарантированно выбрать 16 клеток одного цвета.
Примером того, что выбрать больше 16 клеток у Васи не всегда получится, является шахматная раскраска. В каждой строке и в каждом столбце ровно по 4 белых и 4 чёрных клетки, значит, в любых 2 столбцах и 2 строках суммарно будет выбрано не более, чем 
одноцветных клеток.
Ответ: 16.