|
|
 |
Условие
В клетках таблицы размером 10×20 расставлено 200 различных чисел. В каждой строчке отмечены два наибольших числа красным цветом, а в каждом столбце отмечены два наибольших числа синим цветом. Доказать, что не менее трёх чисел отмечены в таблице как красным, так и синим цветом.
Решение
Если все отмеченные числа – двухцветные, то их по крайней мере 40.
Пусть есть одноцветные отмеченные числа. Рассмотрим наибольшее из них число A. Пусть оно синее (для красного рассуждения аналогичны). Тогда два красных числа в той же строке больше A и, следовательно, двухцветны.
Рассмотрим отмеченные числа, не лежащие с A в одной строке. Если среди них есть двухцветное, то все доказано. В противном случае расмотрим наибольшее среди них число B.
Если B – синее, то два красных числа в одной строке с B двухцветны.
Если B – красное, то два синих числа в одном столбце с B двуцветны. При этом одно из них не лежит в одной строке с A и, поэтому не совпадает с двумя ранее найденными двухцветными числами.
Замечания
Обобщение см. в задаче 73615.
