4
1

Найти, какое наибольшее количество кругов единичного радиуса можно расположить на плоскости так, что бы выполнялось два условия :

  1. Для каждого круга существует прямая, которая этот круг оставляет в одной полуплоскости, а все остальные круги в другой.
  2. При этом не должно быть двух кругов, расстояние между центрами которых превышает 10.

задан 27 Окт '13 18:44

1

@Urt: продолжу здесь, так как внизу исчерпано место для ответа. Я проверил свои вычисления и понял, что 15-угольник не имеет отношения к делу: там круги вписаны были так, что друг от друга прямыми не отделялись. Видимо, что Ваш 6 верен. Вокруг правильного 6-угольника можно разместить 6 кругов с расстоянием $%\le8$% между их центрами. Но рассуждение надо скорректировать. Я уже указывал на то, что попадание центров в круг радиусом 5 совершенно не гарантировано. Можно при помощи теоремы Хелли получить чуть более слабую оценку $%10/\sqrt3$%. Но тогда в оценке для $%N$% выходит 7 с чем-то.

(28 Окт '13 1:29) falcao

@Falcao, я поздно увидел Ваш комментарий - рисунок и добавление написал раньше. В ответе использовано более слабое (по отношению к Вашему примеру) утверждение - попадание центров кругов в некоторый круг радиуса 5. Справедливость утверждения 1 обусловлена тем, что диаметр множества центров равен 10 (или я где-то не домысливаю?). При этом условие по п.2 (перемещение кругов) остается справедливым.

(28 Окт '13 3:53) Urt

@Urt: у Вас условие более сильное, а не более слабое. Рассмотрим, как я уже говорил, три точки в вершинах равностороннего треугольника. Диаметр (максимум попарных расстояний) равен 10, но покрыть эти точки кругом радиуса 5 нельзя -- только $%10/\sqrt3$%.

(28 Окт '13 4:02) falcao

Да, почему-то делил сторону треугольника пополам... Придется не спать, а как-то править

(28 Окт '13 4:08) Urt

Вчерне скорректировал доказательство. Займусь оформлением после перерыва.

(28 Окт '13 5:47) Urt

@Urt: мне кажется, аргумент сведения задачи к случаю правильного многоугольника пока что носит "эвристический" характер. Дело в том, что при "раздутии" расстояния между точками увеличиваются, и может так оказаться, что изначально имело место какое-то несимметричное расположение кругов, а после "раздутия" произошло увеличение расстояний, и всё испортилось. Для сравнения я хочу сослаться на известную задачу про пять кругов, покрывающих круг максимального радиуса. Там оптимальное расположение несимметрично. Вот ссылка.

(28 Окт '13 18:59) falcao

@Falcao, симметрирование (перевод в вершины правильного N-угольника) в нашей задаче не нарушает ее условия, т. е. для любой существующей системы N кругов можно построить систему N кругов с центрами в вершинах правильного N-угольника радиуса R, соответствующую условиям задачи. Так, если $% a_i $%, i=0,...,N-1 – угол от i-й вершины до i+1-й (mod N), то $% \sum a_i=2 \pi $% и $% \min a_i \le 2 \pi /N $%. Из несуществования симметричной N-системы вытекает несуществование N-системы вообще. В задаче по Вашей ссылке (кстати, весьма интересная) такой симметрирующий фактор отсутствует.

(28 Окт '13 19:55) Urt

@Urt: здесь есть ещё вот какая проблема: без уточнения того, чему равно $%N$%, и каков центр "накрывающего" круга, нельзя "разносить" круги вдоль радиусов. Ведь точка может быть выбрана где-то далеко, и тогда при "разнесении" происходит нарушение основного условия, относящегося к полуплоскостям. То есть, я считаю, что Ваше решение ухватывает какие-то существенные вещи, но при этом оно нуждается в доработке. По-видимому, нужно рассматривать $%n$%-угольник как пересечение полуплоскостей, и уже после этого передвигать прямые (по перпендикулярным направлениям).

(28 Окт '13 20:07) falcao

@IvanOne, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(26 Апр '14 15:15) Angry Bird
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
1

Можно 6 и не более. Идея решения (поправлено с учетом замечаний и пояснений @Falcao)) основана на следующих моментах. 1) Пусть центры всех кругов (N - число кругов) находятся в некотором "большом" круге радиуса R. 2) Как бы ни были расположены центры кругов, их можно раздвинуть по радиусам от центра большого круга, переместив их центры на окружность большого круга (при новом расположении условия задачи также будут выполняться). 3) Поскольку минимальное расстояние между центрами кругов (равное L=10) не превышает среднего расстояния между центрами соседних кругов, то эти центры можно разместить в вершинах правильного N-угольника. При таком перемещении новая система N кругов также будет соответствовать условиям задачи. С учетом отмеченного будем рассматривать систему кругов, расположенных в вершинах правильного N-угольника. Ход решения следующий. 1) Определяем радиус большого круга R (описанного вокруг правильного N-угольника). 2) Находим величину угла : $% \alpha $% , на который должны быть разнесены центры кругов (вершины N-угольника) для того, чтобы каждый круг можно было отсечь примой. Из геометрических построений (см. рис. http://www.picshare.ru/view/3207801/ ) находим: $% \alpha = 2 \arctan ( 1/ \sqrt {R-1}). $% 3) Из условия $% \beta = 2 \pi /N \ge \alpha, $% которое принимает вид $$ (1) \;\;\;\;\;\;\;\;\;\; N \le \pi / \arctan ( 1 / \sqrt {R-1}) , $$ делаем вывод о возможности (невозможности) построения такой системы. Случаи четных и нечетных N рассматриваются отдельно.

a). N – четно. R=L/2. Тогда для заданных исходных данных условие существования требуемой системы кругов (1) выполняется при $% N \le 6,777 $% ($% \alpha \approx 0,927 рад., \beta \approx 1,0473, $% при этом округление обеспечивает корректность проверки необходимых и достаточных условий).

b). N – нечетно. $% R=L/(2 \sin ( \pi (N-1)/2N)), $% Положив N=7, получим $% R \approx 5,128, $% и из (1) $% N \le 6,869 $% – противоречие ($% \alpha \approx 0,9147 $% рад., $% \beta \approx 0,898 $% рад, т. е. условие (1) не выполняется и требуемой системы кругов не существует.

Поскольку существование системы N кругов влечет существование системы с меньшим числом кругов, то, объединяя полученные выводы для четных и нечетных N заключим, что требуемой системы кругов не существует при N > 6.

Далее я привожу исходное «решение», чтобы показать, как и когда оно могло привести к ошибочному ответу. «Можно 6 и не более. Идея решения основана на двух моментах. 1) Все круги должны находиться в круге радиуса 6. 2) Как бы ни были расположены круги, их можно раздвинуть по радиусам от центра большого круга до касания с его окружностью (при новом расположении условия задачи также будут выполняться). Далее из геометрических построений можно получить, что на каждый круг должно отводиться не менее 0,927 рад» Как видно, при L=10 замеченная @Falcao некорректность не повлияла на результат оценки Nmax=6. Для случая L=11, проводя расчеты по представленным выше формулам, получим $% R \approx 5,641, N \le 7,230 ((\alpha \approx 0,869). $% Если в этом случае положить R’=L/2=5,5, то получим оценки $% N \le 7,133 (( \alpha \approx 0,881), $% т. е. выводы опять одинаковые.

Но если положить, например, L=10,5, то будем иметь: $% R \approx 5,385, N \le 7,052 ((\alpha \approx 0,891), $% откуда следует правильный вывод о существовании такой системы кругов. В то время как для R’ = L/2= 5,25 получим соответствующие оценки $% N \le 6,957 ((\alpha \approx 0,903), $% которые приводят к ошибочному выводу о несуществовании системы с 7-ю кругами.

Добавление как комментарий (т. к. возможность комментировать не предоставлена) к замечанию @Falcao, о необходимости доработки решения в части построения «накрывающего» круга радиуса R. Действительно, в приведенном решении «подразумеваются» определенные свойства такого круга. Идея его построения, как будто, ясна, есть варианты... Довести решение в этом направлении, конечно, необходимо...

ссылка

отвечен 27 Окт '13 21:14

изменен 28 Окт '13 21:15

1

@Urt: как Вы пришли к первому условию? Ведь если взять три круга с центрами на расстоянии 10 друг от друга, то радиус описанной окружности будет равен $%10/\sqrt{3}$%. С другой стороны, этой оценки, увеличенной на 1, уже хватает: с учётом теоремы Хелли достаточно рассматривать тройки вершин. Но я не знаю, как это влияет на ответ.

(27 Окт '13 21:38) falcao

@Falcao, спасибо за поправку. Конечно нужно было сказать, что "центры всех кругов должны находиться в круге радиуса 5". Именно на этом основано решение. Хотел более просто описать - получилась некорректность.

(27 Окт '13 21:45) Urt

@Urt: так ведь это практически то же самое! Если центры находятся в круге радиуса 5, то сами единичные круги попадают в круг радиуса 6. Я имел в виду, что если центры трёх кругов расположены в вершинах правильного треугольника со стороной 10, то их уже таким способом не покрыть: радиус должен быть увеличен.

(27 Окт '13 21:56) falcao

@Falcao, эту мысль я понял сразу после того, как внес поспешную и бессмысленную правку. Отмеченную Вами некорректность нужно осмыслить.

(27 Окт '13 22:04) Urt

@Urt: у меня там при подсчёте получается довольно маленький угол. При таком расположении влезает вроде бы 21 круг. Но они там не могут быть расположены слишком плотно, потому что должны ещё и касательными отделяться. Честно говоря, у меня при разного рода неточных прикидках получалось где-то порядка 15. Я рассматривал правильные $%n$%-угольники (при чётных и нечётных $%n$%), и круги симметрично вписывались с внешней стороны. Но я эти вычисления как следует пока не проверил, и рассуждения в обратную сторону тоже не было.

(27 Окт '13 22:20) falcao

@Falcao, угол на круг, действительно, маленький, но там нужно учесть еще отсекаемый сегмент (до касания с другим кругом). Может быть, удастся сделать рисунок - попробую.

(27 Окт '13 22:25) Urt

@Urt: мне всё-таки кажется, что там не 6, а больше. Надо будет ещё раз пересчитать расстояния для правильного 15-угольника.

(27 Окт '13 22:43) falcao

@Falcao Сейчас, перепроверю расчеты. У меня ошибки - явление частое (буду работать над этим).

(27 Окт '13 22:56) Urt
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
1

Чтобы не было неясностей по вопросу о существовании искомой системы, состоящей из 7 кругов, решил выложить имеющееся доказательство несуществования такой системы.

Для краткости систему, удовлетворяющую определенным условиям и состоящую из N кругов, будем называть N- системой, а центры кругов – точками. Выпуклая оболочка множества точек N-системы представляет собой выпуклый N-угольник. То, что это действительно N-угольник (не вырожден) непосредственно следует из условия 1 задачи (каждая точка отделима прямой).

На рис. представлен фрагмент 7-системы, состоящий из точек A, B, C, D, где $% \beta_1, \beta_2 , \beta_3 $% - углы между соответствующими прямыми (обозначенными как векторы) и прямой UV ($%\beta_0=0$%). При заданных $% \alpha_i, i=1, 2, 3 $% (можно и далее) определим величины $% \beta_i, x_i, y_i, X_i , Y_i $% и $%F_i$% рекуррентными соотношениями: $%\alpha_0=\beta_0=0$%, $%X_0=Y_0=F_0=0$%, $%\beta_i=\beta_{i-1}+\alpha_{i-1}+\alpha_i$%; $%x_i= 2\sin( \beta_i)/\sin( \alpha_i)$%, $%y_i = 2\cos( \beta_i)/ \sin( \alpha_i)$%, $%X_i = X_{i-1} + x_i$%, $%Y_i = Y_{i-1} + y_i$%, $%F_i= (X_i^2 + Y_i^2 )/4$%.

При этом $% L_1= 2 \sqrt{F_1 }=|AB|$%, $%L_2 = 2 \sqrt{F_2}= |AC|$%, $%L_3 = 2 \sqrt{F_3 }= |AD|$%.

В явном виде величина $%F_3$% имеет вид: $$ (1) \ \ \ \ \ \ \ \ F_3 =1/ \sin^2(\alpha _1) +1/ \sin^2 (\alpha _2) +1/\sin^2 (\alpha _3) + 2 \cos(\alpha _1+\alpha _2) /\sin(\alpha _1) \sin(\alpha _2) + $$

$$ + 2\cos(\alpha _1+2\alpha _2 +\alpha _3)/\sin(\alpha _1) \sin(\alpha _3) + 2 \cos(\alpha _2+\alpha _3) /\sin(\alpha _2) \sin(\alpha _3). $$ Поскольку сумма всех внутренних углов 7-угольника равна $% S=5 \pi $%, то в 7-угольнике найдутся два соседних угла, сумма которых не менее $% 2S/7=10 \pi /7. $% Пусть $% \angle ABC $% и $% \angle BCD $% – такие углы, тогда $% \alpha _1 + 2 \alpha _2 + \alpha _3 \le 4\pi /7. $% Найдем минимум величины (1) при этом условии. В силу выпуклости функционала $% F_3 $% и симметричности области оптимизации относительно перестановки переменных $% \alpha _1, \alpha _3 $% следует принять $% \alpha _1= \alpha _3 $% и $% \alpha _1 + \alpha _2 \le 2\pi /7 \approx 0,898$%.

Оптимальная точка соответствует значениям $% \alpha _1^o = \alpha _3^o \approx 0,473, \alpha _2^o \approx 0,425, F_3^{min} \approx 26.67, L_3^{min} \approx 10,33, $% откуда следует несуществование 7-системы.

Примечания.

  1. Попутно я посмотрел задачи с ограничениями на длину стороны $% (L_1 \le 10), $% а также на удаленность соседних точек $% (L_2 \le 10). $% Результаты совпадают с соответствующими оценками для равносторонних многоугольников.

  2. Продолжая описанную выше рекуррентную процедуру, по-видимому, можно на основе индукции придти (?) к оптимальности равносторонней N-конструкции в общем случае. Конечно, хотелось бы иметь обоснование оптимальности равносторонней N-конструкции на основе фундаментальных положений (выпуклость, симметричность, сходимость к неподвижной точке...).

P.S. Подскажите, пожалуйста, как вставлять рисунки непосредственно в текст. Имеется ли возможность просматривать вставленный рисунок в процессе подготовки (редактирования) текста?

ссылка

отвечен 3 Ноя '13 4:19

изменен 4 Ноя '13 0:56

@Urt: спасибо за добавление к доказательству! Я завтра почитаю внимательно. Текст я слегка отредактировал, чтобы не было искажений: здешний редактор плохо реагирует на подчёркивания.

Как вставлять картинки, к сожалению, я не знаю (ни разу ничего не рисовал).

Хотя я пока внимательно не читал текст, но у меня возник такой вопрос: в каком смысле функция $%F_3$% от трёх переменных может быть названа выпуклым функционалом, и в силу чего можно заключить, что $%\alpha_1=\alpha_3$%? Симметрия понятна, но ведь точки максимума могут быть симметричны друг другу с неравными координатами.

(3 Ноя '13 4:57) falcao

@Falcao, спасибо за редакцию - я помучился корректировать. По поводу выпуклости - вторые производные не меняют знак. Функционал симметричен по a1 и a3 в том смысле, что он инвариантен относительно их перестановки (при оптимизации я выразил a2=(sum-a1-a3)/2). Для уверенности, кроме того, провел оптимизацию по двум параметрам при имеющемся ограничении. Результат тот же.

(3 Ноя '13 5:17) Urt

@Urt: у меня складывается ощущение, что Ваше решение верно в своей основе, но хотелось бы лучше понять технические детали. Из вида функции ясно, что она убывает по каждой переменной, а также что она симметрична относительно $%a_1$%, $%a_3$%. Из каких фактов тогда следует, что наименьшее значение достигается при $%a_1=a_3$%?

(3 Ноя '13 17:36) falcao

@Falcao, я рассуждал так. Вторые производные от F по каждому аргументу положительны в области определения A. Следовательно, область $% F(A)= \{(a,f), a \in A, f \ge F(a)\}(a=(a_1,a_2,a_3))$% и ее сечение плоскостью $% a_1+2a_2+a_3=c $% выпуклы, Крайняя (снизу по f) область Fmin(A) также выпукла, поэтому $% (a_1^o,a_2^o,a_3^o) \in Fmin(A) \Rightarrow (a_3^o, a_2^o, a_1^o) \in Fmin(A) $% - в силу симметрии и $% (a_1^1,a_2^o,a_1^1) \in Fmin(A) $% , где $% a_1^1=(a_1^o+a_3^o)/2 $% – в силу выпуклости. У нас F(A) строго выпукло, Fmin(A) одноточечное множество, симметричное решение единственно.

(3 Ноя '13 22:09) Urt

@Urt: да, похоже, что этих аргументов достаточно, хотя в целом задача оказалась весьма сложной технически. Если ещё добавить первоначальное исследование конфигурации (что получится именно выпуклый 7-угольник), то всё выходит ещё сложнее. Интересно, какого рода решение имели в виду авторы?

(3 Ноя '13 22:22) falcao

@Falcao, действительно, процесс был технически трудоемкий. Но если идею с выпуклостью провести по индукции, то соотношение типа (1) для $% F_7 $% превратится в тождество $% F_7 \equiv 0 $%. При этом задача примет вид $% \max_{i,j} [(\sum x_k)^2+(\sum y_k)^2] \Rightarrow \min_a$% (подбираются подходящие суммы для пар (i,j)) . Тогда свойства выпуклости и инвариантности относительно циклических перестановок позволяют (?) провести аналогичные рассуждения, обосновывающие оптимальность равносторонних N-систем. Да, что имели в виду авторы, узнать интересно.

(3 Ноя '13 22:54) Urt

@Urt: я имел в виду несколько другое. Обобщить Ваше рассуждение и получить при этом случай правильного $%n$%-угольника в качестве оптимальной конфигурации, судя по всему, возможно. Однако мной имелся в виду изначальный анализ, когда мы заранее не знаем, в какой форме всё это дело расположено. Там нужны некие рассуждения (не слишком сложные), чтобы показать существование самого выпуклого $%n$%-угольника, вокруг сторон которого расположены круги. Это нужно, в частности, для того, чтобы задать выбор точек A, B, C, D в решении.

(3 Ноя '13 23:02) falcao

@Falcao, (исправил свой путаный комментарий - привел в соответствие с текстом ответа, новый выложить нет возможности). Рассматриваемый многоугольник – это выпуклая оболочка исходного множества N точек. То, что это действительно N-угольник (не вырожден) непосредственно следует из условия 1 задачи (каждая точка отделима прямой).

(3 Ноя '13 23:18) Urt
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
0

Комментарии писать уже некуда, поэтому придётся продолжить здесь. Просьба не считать написанное решением задачи!

@Urt: в решении так или иначе используется тот факт, что сами прямые, задающие полуплоскости, отделяющие круги, формируют выпуклый $%n$%-угольник. Здесь я вижу некоторую тонкость: с одной стороны, многоугольник и есть пересечение полуплоскостей, но здесь требуется обоснование того, что оно непусто, а также то, что не получится многоугольник с меньшим числом сторон. Доказательство достаточно простое, но мне кажется, о нём стоило бы упомянуть, так как изначальная конфигурация, вообще говоря, "хаотична", и её надо сначала "приручить".

В принципе, я допускаю, что при рассмотрении только центров кругов рассуждение может быть оформлено и проще.

ссылка

отвечен 3 Ноя '13 23:47

@Falcao, мы писали почти одновременно и пришли к одинаковому заключению (я модифицировал свой предыдущий комментарий).

(3 Ноя '13 23:53) Urt
10|600 символов нужно символов осталось
0

Пускай на плоскости размещено $%n$% кругов единичного радиуса, удовлетворяющих условиям задачи. Центры этих кругов образуют выпуклый $%n$% - угольник $%A_1A_2\dots A_n$% (если $%n$%- угольник не выпуклый, то для круга, центр которого внутри выпуклой оболочки, не буде разделяющей прямой).

Рассмотрим треугольник $%A_{k-1}A_kA_{k+1}$% (считаем, что $%A_0=A_n, A_{n+1}=A_1$%). Введем обозначения: $%\angle A_kA_{k - 1}{A_{k + 1}} = \alpha_k$%, $%\angle A_kA_{k + 1}A_{k - 1} = {\beta_k}$%, $%h_k$% - высота треугольника, опущенная на сторону $%A_{k-1}A_{k+1}$%. Заметим, что $%h_k\ge 2$%, иначе не найдётся разделяющей прямой для кругов с центрами в $%A_{k-1}$% и в $%A_{k+1}$%.

Тогда $%{A_{k - 1}}{A_k} = \frac{{{h_k}}}{{\sin {\alpha_k}}} \ge \frac{2}{{\sin {\alpha_k}}},{A_k}{A_{k + 1}} = \frac{{{h_k}}}{{\sin {\beta_k}}} \ge \frac{2}{{\sin {\beta_k}}} $%. Сложив $%n$% пар таких неравенств, получим неравенство $$2P \ge 2\sum\limits_{k = 1}^n {\left( {\frac{1}{{\sin {\alpha _k}}} + \frac{1}{{\sin {\beta _k}}}} \right)},$$ где $%P$% - периметр $%n$% - угольника $%A_1A_2\dots A_n$%.

Используем неравенство Иенсена для функции $%f(x) = \frac{1}{{\sin x}}$%: $$P \ge \sum\limits_{k = 1}^n {\left( {\frac{1}{{\sin {\alpha_k}}} + \frac{1}{{\sin {\beta_k}}}} \right) \ge \frac{{2n}}{{\sin \left( {\frac{{\sum\nolimits_{k = 1}^n {({\alpha _k} + {\beta _k})} }}{{2n}}} \right)}}} = \frac{{2n}}{{\sin \left( {\frac{\pi }{n}} \right)}}.$$ Воспользуемся такими фактами:

Длина кривой постоянной ширины $%d$% равна $%\pi d$% (теорема Барбье).

Любую плоскую фигуру диаметра $%d$% можно покрыть фигурой постоянной ширины $%d$%.

Среди всех фигур диаметра $%d$% наибольший периметр имеет кривая постоянной ширины.

Диаметр $%n$% - угольника $%A_1A_2\dots A_n$% не превышает $%10$%, поэтому его периметр $%P$% не превышает длины кривой постоянной ширины $%10$%, то есть не превышает $%10\pi$%, но из неравенства $%P \ge \frac{{2n}}{{\sin \left( {\frac{\pi }{n}} \right)}}$% для $%n=7$% получим $%P \ge \frac{{2 \cdot 7}}{{\sin \left( {\frac{\pi }{7}} \right)}} \approx 32,27$%. Значит $%n<7$%.

ссылка

отвечен 12 Ноя '14 14:51

изменен 12 Ноя '14 21:02

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,394

задан
27 Окт '13 18:44

показан
1705 раз

обновлен
12 Ноя '14 21:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru