Какое наибольшее число точек можно отметить на единичном квадрате (внутри или на сторонах), чтобы расстояние между любых двух точек было не меньше 0,5.

задан 10 Фев '14 1:09

изменен 10 Фев '14 21:00

Deleted's gravatar image


126

1

Квадрат имеется в виду единичный?

(10 Фев '14 1:53) falcao

Да, единичный. Уже исправила.

(10 Фев '14 19:47) ASailyan
10|600 символов нужно символов осталось
2

У меня такое решение сегодня возникло. Ясно, что 9 точек расположить можно в вершинах квадратной сетки со стороной 1/2. Покажем, что 10 точек расположить нельзя. Разобьём квадрат на 9 равных квадратиков со стороной 1/3. По принципу Дирихле, какие-то две точки попадут в одну из 9 клеток (то, что части пересекаются, только помогает). Тогда расстояние между точками не превосходит длины диагонали квадратика, равной $%\sqrt2/3$%, а это меньше $%1/2$%.

ссылка

отвечен 14 Фев '14 4:40

@falcao, замечательное доказательство, не требующее дополнительных рассуждений. У меня по этой задаче возник такой вопрос. А что если в условии нестрогое неравенство $% r \ge 1/2 $% заменить на строгое: $% r >1/2 $%. Тогда, пожалуй, 9 точек уже не разместить (?), а 8, легко размещаются.

(14 Фев '14 14:10) Urt
10|600 символов нужно символов осталось
2

Все-таки 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

изменен 10 Фев '14 20:15

@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
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,131

задан
10 Фев '14 1:09

показан
1374 раза

обновлен
14 Фев '14 23:49

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

по почте:

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

по RSS:

Ответы

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

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