Какое наибольшее число точек можно отметить на единичном квадрате (внутри или на сторонах), чтобы расстояние между любых двух точек было не меньше 0,5. задан 10 Фев '14 1:09 ASailyan |
У меня такое решение сегодня возникло. Ясно, что 9 точек расположить можно в вершинах квадратной сетки со стороной 1/2. Покажем, что 10 точек расположить нельзя. Разобьём квадрат на 9 равных квадратиков со стороной 1/3. По принципу Дирихле, какие-то две точки попадут в одну из 9 клеток (то, что части пересекаются, только помогает). Тогда расстояние между точками не превосходит длины диагонали квадратика, равной $%\sqrt2/3$%, а это меньше $%1/2$%. отвечен 14 Фев '14 4:40 falcao @falcao, замечательное доказательство, не требующее дополнительных рассуждений. У меня по этой задаче возник такой вопрос. А что если в условии нестрогое неравенство $% r \ge 1/2 $% заменить на строгое: $% r >1/2 $%. Тогда, пожалуй, 9 точек уже не разместить (?), а 8, легко размещаются.
(14 Фев '14 14:10)
Urt
|
Все-таки 9. Пусть $% r =1/4; K_2, K_6 $% – вложенные друг в друга квадраты с совпадающими центрами и параллельными сторонами, длины которых соответственно равны $% 2r, 6r; R= K_6 \setminus K_2 $% (так называемая рамка ширины $% 2r $% ); $%S_i $% - круги радиуса r с центрами в выбранных точках. Максимальная площадь покрытия кругами $% S_i $% рамки $% R $% равна $% 8\pi r^2$%. Поскольку круги не выходят за пределы квадрата $% K_6 $% , то общая покрываемая площадь не более $% Q= (8 \pi +4)r^2. $% При этом, учитывая, что круги $% S_i $% не пересекаются, получим оценку числа точек $% N \le Q/\pi r^2= (8+4/\pi) < 9,3 $% и, следовательно, $% N=9 $% (такие точки легко найти). отвечен 10 Фев '14 3:11 Urt @Urt: а можно пояснить утверждение насчёт рамки? Я не понял, откуда взялось $%8\pi r^2$%.
(10 Фев '14 3:28)
falcao
@falcao, на рамке размещается максимально 8 кругов по периметру исходного квадрата. Любое смещение квадратов (возможно внутрь квадрата) приводит к уменьшению общей покрываемой области этими кругами. Здесь нужно было более корректно оговорить общую зону покрытия (рамка выходит на r за квадрат и имеет ширину 2r).
(10 Фев '14 3:42)
Urt
@Urt: у меня пока не созрело чёткого решения Вашего варианта задачи. Я имею в виду случай замены нестрого неравенства на строгое. Тут надо перепробовать разные подходы. Скажем, иногда помогает учёт длины периметра какого-либо квадрата, покрываемой кругами. Мне известны примеры таких задач.
(14 Фев '14 23:49)
falcao
|
Квадрат имеется в виду единичный?
Да, единичный. Уже исправила.