?

Log in

No account? Create an account
Записки на полях шпаргалок
Из лимона надо сделать лимонад!
Математика в кафе. S2E3. 
29th-Mar-2010 12:24 am
flower
От имени, так сказать, и по поручению _zif'а.

В этот раз присутствовали: _zifЛёша, yashunskyВолодя, smagenСаша и cat_katrinКатя (то бишь я).

Рассматривалось обобщение задачи о каплях, предложенное smagenСашей. Первоначальная задача формулируется следующим образом: на бесконечный белый лист падает капля чернил (тут_zifЛёша выразительно капал какао на лист бумаги) и превращается во множество разбросанных по бумаге пятен неправильной формы. Суммарная площадь всех капель меньше 1. Необходимо доказать или опровергнуть утверждение, что всегда можно разлиновать этот лист квадратной сеткой со стороной 1 таким образом, чтобы ни один узел сетки не попал на чернильное пятно.

Для этой задачи существует алгоритм, который позволяет нарисовать сетку, обладающую нужными нам свойствами:
1. Нарисуем любую сетку с шагом 1. Если она не попадает ни одним узлом на капли, то заканчиваем, если нет, тогда переходим к 2.
2. Мысленно разрезаем всю нашу плоскость на квадратики 1х1 по сетке и собираем все клетки, в которых есть брызги, в одну стопочку. Посмотрим получившуюся стопку на просвет, считая, что плоскость прозрачная, а капли – нет. При этом обязательно найдётся хотя бы одна прозрачная точка. Переходим к 3.
3. Сдвигаем узел нашей сетки в белую точку, которую нашли в п.2. После этого возвращаем все наши квадратики на свои места на плоскости из стопки. Построенная таким образом сетка будет обладать требуемым свойством.

Обобщённая же задача звучит так: предположим, что капли обладают суммарной площадью не 1, а S. Каким образом можно оценить, в каких случаях точно можно построить сетку 1х1, обладающую указанными свойствами, а в каких – нет? Если мы опишем круг вокруг квадрата 1х1, то, очевидно, его площадь будет π/2 и для такого круга нельзя нарисовать сетку 1х1, которая будет удовлетворять условиям. Для S < 1, как было показано, всегда можно построить такую сетку. А вот что происходит в том случае, когда 1 ≤ S < π/2? Именно выяснению этого и было посвящено очередное заседание.

Видимо, задача оказалась слишком сложной для того, чтобы существенно продвинуться за один вечер. Несмотря на это, мне представляется интересным описать те разнообразные подходы, которые предлагались и прорабатывались.

_zifЛёша предложил рассматривать «пиксельное» отображение нашей задачи и пятна. То бишь считаем, что у нас есть S «пикселей» пятна. Как количество пикселей S соотносится с той сеткой, которую можно нарисовать в этом случае?

yashunskyВолодя высказал идею, не будет ли треугольник Рело более «удачной» фигурой, чем круг. То есть, что он, возможно, будет препятствовать нарисовать сетку, занимая меньшую площадь, чем вышеозначенный круг. Впоследствии это утверждение было опровергнуто.

smagenСаша прорабатывал идею о том, что для пятен, чья площадь равна 1, тоже можно построить сетку с правильным размещением. Для её подтверждения была предложена идея «концентрических окружностей». Для каждой точки пятна построить окружности с последовательно увеличивающимися на 1 радиусами, и смотрим, пройдёт ли какая-то окружность через другую точку пятна. Если пройдёт, то мы можем при совмещении разрезанных квадратиков сетки поворотом совместить эти две точки, и за счёт этого где-то появится пустая точка. В эту-то точку и можно поместить узел новой сетки. Было высказано предположение о том, что если ни одна из таких концентрических окружностей не проходит через другие точки, то для данного размещения пятна суммарной площади 1, нельзя построить сетку.

ЗатемyashunskyВолодей было предложено рассмотреть противоположную задачу: как нарисовать пятна таким образом, чтобы точно нельзя было нарисовать сетку. Появилась гипотеза о том, что чем пятна удалённее друг от друга, тем больше должна быть их площадь. Соответственно, чем кучнее они расположены, тем меньше «краски» требуется, чтобы сетка не была построена. Тут на сцену опять вышел круг с площадью π/2.

Кроме того, smagenСаша предложил рассматривать множество всех возможных решёток в 3D, откладывая по оси Oz угол между «направляющей» сетки и осью Ox. Тогда каждая точка в пространстве задаёт сетку. Затем среди всех точек пространства выделяем множество тех точек, каждая из которых задаёт уникальную сетку. А потом уже среди этого множества ищем те сетки, которые нам подходят.
Comments 
29th-Mar-2010 07:26 pm (UTC)
Не совсем так. Выделять "несовместимые" решетки не планировалось. Для начала нужно выделить множество точек пространства, которое задаст нам все уникальные решетки. А далее рассматривать, какие расположения решеток будет блокировать расположение пятен на плоскости.
29th-Mar-2010 08:56 pm (UTC)
"Блокировать раположение пятен" = "правильно нарисованная сетка для данного набора пятен"?
30th-Mar-2010 07:03 am (UTC)
Anonymous
Да. Я тут недавно подумал, а не является ли пятно в виде прямоугольника 1 на sqrt(2) блокирующем для всех расположений решеток? У меня вроде, что да. Если так, то это прорыв, потому что удалось подвинуть вниз верхнюю границу.
Идея такого прямоугольника пришла мне ещё в кафе, но тогда я почему-то подумал, что он больше чем круг. Но дома я обнаружил, что sqrt(2) < pi/2.
30th-Mar-2010 07:04 am (UTC)
Как можно было догадаться, анонимный коммент - мой.
This page was loaded Jan 24th 2018, 9:33 am GMT.