2018 клеток

[Ktina]

На клетчатой бумаге произвольным образом отметили 2018 клеток. Какое наибольшее количество клеток, не имеющих общих точек, можно гарантированно отыскать?

[svv]

505 (раскраска в 4 цвета)

[Ktina]

svv
А как доказать, что 505 - наибольшее? Можете привести пример, когда 506 не найдётся?

[svv]

Надо отметить $504$ квадратика $2\times 2$, и ещё прямоугольник $1\times 2$. Всего тут $505$ фигур и $2018$ клеток. В каждой фигуре можно выбрать лишь одну клетку.

[Ktina]

svv
Большое спасибо!

[wrest]

Ktina
Можете пояснить условие? Допустим, отметили 2018 клеток в виде одного ряда (прямоугольника 1х2018). Какое количество клеток, не имеющих общих точек, можно отыскать?
Теперь отметили клетки через одну (то есть опять все в одном ряду, скажем на четных местах). Какое количество клеток, не имеющих общих точек, можно отыскать в этом случае?

[svv]

wrest
Для какого максимального $n$ справедливо утверждение: «Как бы ни были отмечены на клетчатой плоскости 2018 клеток, из них всегда можно выбрать $n$ клеток, не имеющих общих точек»?

Если я заявляю, например, что ответ 505, я должен обосновать, что:
1) 505 клеток можно выбрать всегда, как бы ни были отмечены 2018 клеток.
2) 506 клеток можно выбрать не всегда.

[wrest]

svv
Допустим я выбрал 2018 клеток которые все в одном ряду, через одну. Т.е. выбрал 1, 3, 5 и т.п. Ни одна не имеет общих точек ни с одной другой.
Теперь я выбрал клетки которые идут в ряд сплошняком, т.е. 1,2,3,4... И тогда каждая имеет общие точки с какой-то другой выбранной.

И где тут ваши 505?

Я не понимаю условие, очевидно. Или что такое "клетчатая бумага" или что такое "клетка" или что значит "не имеют общих точек" . И, соответственно, прошу мне условие растолковать.

[mihaild]

wrest
В вашей конфигурации 505 клеток найти можно (например, 1, 3, 5, ..., 1009). Более того, в любой конфигурации 505 клеток найти можно.
Существуют конфигурации, в которых 506 (и соответственно больше) клеток найти нельзя.
Формально - находим [минимум по всем способам отметить 2018 клеток] (максимальное число попарно непересекающихся клеток в данном наборе)