Окрашенные вершины

[wpoms.]

Пусть `m` и `n` - целые числа, большие `1`. Рассмотрим `m xx n` прямоугольную сетку точек на плоскости. `k` из этих точек окрашены в красный цвет, при этом никакие три точки не являются вершинами прямоугольного треугольника, две стороны которого параллельны сторонам сетки. Найдите наибольшее возможное значение `k`.

@темы: Комбинаторика

Comments

[Дилетант]

У меня получилось k=max(m,n), но это как-то очень простецки... ((

[Adjirranirr]

Дилетант, по меньшей мере `k = m + n - 2`. Больше пока не получилось, но и как доказать — не знаю =)

[Дилетант]

Adjirranirr, да вчера поняла, что дурость написала...

[Adjirranirr]

Для `m = n = 2`, очевидно, расположить можно только две точки, т.е. `k = m + n - 2`.

Предположим, что для всех `m, n > 1`, удовлетворяющих `m + n < s` для некоторого `s`, выполняется `k = m + n - 2`, и пусть `m_1 + n_1 = s`. Рассмотрим `m_1 xx n_1`-сетку и предположим, что в ней закрашено максимальное количество узлов.
Если `m_1 = 2` или `n_1 = 2`, то закрасить можно не больше `m_1 + n_1 - 2 = [m_1 \vee n_1]` узлов. Предположим `m_1 > 2` и `n_1 > 2`.
Выберем произвольный закрашенный узел; если в его строке и в его столбце располагаются хотя бы по одной закрашенной точке, то они составляют прямоугольный треугольник. Тогда или в его столбце, или в его строке этот узел является единственным закрашенным. Вычеркнем такую строку (столбец), и тем самым уменьшим сумму размерностей сетки до `s - 1`, а количество закрашенных точек до `k - 1`. Для полученной сетки выполняется предположение, и в ней закрашено максимальное количество узлов (так как в противном случае раскраска исходной сетки не была бы максимальной). Но тогда `k - 1 = (m_1 + n_1 - 1) - 2 = s - 3` и `k = s - 2`. По теореме о полной индукции, `AA m,n:\ k = m + n - 2`.