Задачка по математике

[bravchick]

А вот еще замечательная задачка по математике. Скорее всего хорошо известная. Но я почему-то ее в свое олимпиадное детство пропустил:  на листе бумаги поставили кляксу сложной формы, площадь которой меньше 1 кв. см.  Доказать, что можно нарисовать на бумаге сетку из квадратов размером 1х1 см. так, что ни одна вершина сетки не попадет на кляксу. 

Comments

[southwest]

мне кажется, будет верным более сильное утверждение: любую заранее нарисованную сетку из квадратов 1х1 можно будет перенести параллельно (без поворотов) так, что выполнится это условие

[bravchick.livejournal.com]

Ну да, это тоже верно

[southwest]

кстати, не обязательно также иметь кляксу сложной формы, для клякс простой формы это тоже верно :)

[kramian.livejournal.com]

Да, и так проще! Потому что такие сетки а)однозначно соответствуют точкам в единичном квадратике и б) у них нет общих узелков. Если узелок какой-нибудь сетки попал на кляксу, то можно зачернить соотв. точку в единичном квадратике. И раз у разных сеток разные узелки, то таких зачерненных точек будет не больше, чем точек в кляксе.

Я даже не знаю, как прямо доказать исходное утверждение, не доказывая сперва вот это более сильное.

[bravchick.livejournal.com]

Я имел ввиду немного другое решение, которое тоже дает решетку параллельную данной: просто рисуем любую решетку, выбираем один квадратик и заштриховываем на нем все те точки, которые запачканы хотя бы в одном квадратике (по науке: факторизуем плоскость по действию группы Z_2 и на полученном торе отмечаем образ кляксы). Заштрихованная площадь будет не больше исходной площади кляксы, т.е. меньше площади квадратика. Значит в квадратике найдется незаштрихованная точка. Ее и выбираем в качестве узла новой решетки.

[shkrobius.livejournal.com]

Это хорошо, если клякса конечного размера, что не оговорено в условии. Представим, что клякса - звезда с экспоненциально сходящимися на бесконечности N лучами и общей площадью 1-1/N, и устремим N к бесконечности. Конструктивно найти эту точку подобной процедурой уже будет невозможно. Мало того, я не уверен, что можно будет сказать в общем случае, лежит или не лежит искомая "точка" на границе, по которой сшивается тор. По-моему, конечность размера должна быть необходимым условием задачи, иначе возможны патологические случаи.

[(Anonymous)]

Nevazhno: glavnoe, chto klyaksa imeet ploshchad'.
V. Hinich

[kramian.livejournal.com]

Да, так все аккуратно. А то в моем решении все же то ли дырка, то ли неясность
http://bravchick.livejournal.com/63179.html?thread=1759435#t1759435