Олимпиадная задача о разнице длин на клетчатой плоскости — комбинаторная геометрия, 10–11 класс

  Лемма. Раскрасим клетки плоскости в два цвета: нечётные столбцы в зелёный цвет, а чётные – в жёлтый. Тогда для любого отрезка, параллельного прямой l, разность сумм длин его зелёных и жёлтых участков не превосходит некоторого числа D, зависящего только от l.

  Доказательство. Прямая l разбивается вертикальными сторонами клеток на отрезки одинаковой длины; обозначим эту длину через L. Тогда для любого отрезка длины 2L, параллельного l, суммы длин его зелёных и жёлтых частей равны L. Любой отрезок, параллельный l, разбивается на такие отрезки и остаток длины, меньшей 2L; поэтому разность сумм длин его зелёных и жёлтых частей не превосходит 2L.   Раскрасим все чёрные клетки в розовый и голубой цвета так, чтобы розовые клетки были в тех же столбцах, что и красные, а голубые – в тех же, что и синие (см. рис.).

  Рассмотрим любой отрезок, параллельныйl, и обозначим черезr, b, r', b'суммы длин его красных, синих, розовых и голубых частей, соответственно. Тогда по лемме существуют такие числаD₁,D₂, зависящие только отl, что  |(r + r') – (b + b')| ≤D₁,  |(r + b') – (r' + b)| ≤D₂.  Значит, 2|r – b| = |(r + r') – (b + b') + (r + b') – (r' + b)| ≤ |(r + r') – (b + b')| + |(r + b') – (r' + b)| ≤D₁+D₂.

Ответ задачи отсутствует