Клетки прямоугольника 9×11 раскрашены в красный и синий цвета. Докажите, что найдётся клетка, для которой в содержащих её строке и столбце найдётся ещё хотя бы 9 клеток того де цвеиа

задан 22 Авг '17 19:24

Подскажите быстрее

(22 Авг '17 23:29) Fok
10|600 символов нужно символов осталось
1

С каждой парой двух различных клеток, расположенных в одной строке или в одном столбце, свяжем число 1 или -1 соответственно, если эти клетки имеют одинаковый или разный цвет. Назовём такое число индексом пары клеток. Рассуждая от противного, предположим, что ни для какой клетки таблицы, не найдутся хотя бы 9 одноцветных с ней клеток в пределах той же строки и того же столбца. Поскольку таких клеток всего 18, это означает, что сумма индексов данной клетки с клетками на одной линии (горизонтальной или вертикальной), будет отрицательной. Более того, сумма индексов при этом не больше -2 (если 1 встречается не более 8 раз, то -1 встретится как минимум 10 раз).

Суммируя все такие суммы индексов для каждой из клеток, мы получим число, не превышающее -198. Теперь оценим его другим способом. Каждая пара клеток в пределах строки или столбца у нас учитывается дважды при суммировании индексов. Рассмотрим строку, в которой имеется 11 клеток. Пусть среди них k красных и m синих, где k+m=11. Сумма индексов по всем (упорядоченным) парам клеток в пределах данной строки равна k(k-1)+m(m-1)-2km=(k-m)^2-11. Ясно, что k не равно m, и наименьшее значение для |k-m| равно 1. Значит, сумма не меньше -10. Так для каждой из 90 строк; итого не меньше -90.

Аналогичный подсчёт для столбцов даст по крайней мере 1-9=-8 для каждого столбца, а в сумме это будет не меньше -88. Итого по строкам и по столбцам получается не меньше -178, что больше -198. Противоречие.

ссылка

отвечен 23 Авг '17 4:10

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,699

задан
22 Авг '17 19:24

показан
733 раза

обновлен
23 Авг '17 4:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru