Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 01:26 
Не в сети
Оракул
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 795
Cпасибо сказано: 47
Спасибо получено:
139 раз в 129 сообщениях
Очков репутации: 25

Добавить очки репутацииУменьшить очки репутации
При чём тут преподаватель? Мы знаем формулировку в версии ученика.

И я не понимаю вашего непонимания. С поправкой на стилистику - всё прозрачно. Всегда найдётся искомый круг, содержащий 12 (и 15, вероятно) точек. Но не всегда - содержащий 26 (это я уже от себя добавляю).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 02:03 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
16 июн 2016, 16:38
Сообщений: 1358
Откуда: Калининградская область
Cпасибо сказано: 119
Спасибо получено:
78 раз в 77 сообщениях
Очков репутации: 10

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
Всегда найдётся искомый круг.

Ну так и нужно было формулировать:
Доказать, что при любом фиксированном расположении 10000 точек на плоскости, ограниченной квадратом со стороной 2017 всегда найдётся произвольно расположенный круг диаметром 100, который перекроет своей плоскостью часть из данных точек в количестве не менее:
а) 12-ти
б) 15-ти
штук.
С Уважением. Целую. Преподаватель.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 03:04 
Не в сети
Оракул
Зарегистрирован:
02 дек 2016, 23:55
Сообщений: 795
Cпасибо сказано: 47
Спасибо получено:
139 раз в 129 сообщениях
Очков репутации: 25

Добавить очки репутацииУменьшить очки репутации
3axap писал(а):
Ну так и нужно было формулировать:Доказать, что при любом фиксированном расположении 10000 точек на плоскости, ограниченной квадратом со стороной 2017...

Это избыточно, хотя бы по отношению к 12 точкам, как следует из док-ва swan'а. Если эти точки даже будут плавать по квадрату, то в любой момент времени как минимум в одном из явно построенных и зафиксированных внутри квадрата кругов будет не менее 12 точек.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 10:37 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
По моим прикидкам, можно так расположить 10000 точек внутри указанного квадрата, что НЕ НАЙДЁТСЯ круга радиусом 100, внутри которого окажется не менее 26 точек. Вероятно, можно уменьшить это количество, но я пока не знаю как.


Та же идея.
Разобьем исходный квадрат на [math]28\times 28[/math] квадратиков. Сторона маленького квадрата будет чуть больше 72 и соответственно диагональ квадратика больше 100. Теперь на полученной сетке, начиная с левого нижнего узла пометим узлы в "шахматном" порядке. Если не ошибся, то их будет [math]15\cdot 15 + 14 \cdot 14 = 421[/math].
Расстояние между любыми двумя помеченными узлами будет, очевидно, больше 100. И если в достаточно малой окрестности каждого узла поместить 24 точки, то всего будет более 10000 точек и ни в каком круге диаметра 100 не будет лежат 25 точек.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 10:48 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
Тут я даже перемудрил.
Разбиваем сетку на [math]20\times 20[/math] квадратиков. И отмечаем все узлы. Их будет 441. Тогда, помещая в каждый узел 23 точки, получаем всего [math]441\cdot23 = 10143[/math] точек.
И оценку можно уменьшить до 24.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 11:47 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
А нет. Не перемудрил. Забыл только до ума довести.
В моем первом способе расстояние между "соседями" по стороне более 140, что очень не оптимально.
Можно "прибить" к ста, если разбивать не на квадраты, а на прямоугольники.
То есть, если разбить исходный квадрат на [math]40\times 23[/math] прямоугольников, то в шахматном порядке можно отметить уже [math]41\times12=492[/math] узла, положив в каждый узел 21 точку. И оценка сверху уменьшается до 22.

А если еще немного подумать, то можно заметить, что прямоугольная сетка не самый лучший вариант. И паркет можно укладывать не только прямоугольниками... Именно на эту мысль я и хотел вывести вчера ТС, но он (она) чего-то молчит. Ну да ладно.

Upd. По грубым расчетам оценка сверху уменьшается до 20 точек (точнее, если смотреть исходную задачу, то до 19. 20 точек в круге уже точно может не быть).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 13:27 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
16 июн 2016, 16:38
Сообщений: 1358
Откуда: Калининградская область
Cпасибо сказано: 119
Спасибо получено:
78 раз в 77 сообщениях
Очков репутации: 10

Добавить очки репутацииУменьшить очки репутации
Доказывается от противного. Положим, круг не может перекрыть 12, а только 11 точек. Это возможно только тогда, когда группы по 11 точек находятся друг от друга на расстоянии больше диаметра круга. Имеем: [math]10000 \,\colon 11[/math], то есть, 909 групп по 11 и ещё одну точку.
Расположение групп по квадратной сетке не оптимально, так как получается сетка [math]2017 \,\colon 100[/math], то есть, 20х20. Итого узлов получаем: [math](20+1) \cdot (20+1)=441[/math], что явно меньше, чем 909. Так что, группы в узлах нужно располагать чаще, иначе круг перекрывает.
Более оптимальной будет сетка, если узлы с группами точек будут в вершинах равносторонних треугольников.
Тогда получаем пропорцию:
[math]100 - 1[/math]

[math]x - \frac{ \sqrt{3} }{ 2 }[/math]

[math]x=50\sqrt{3}[/math]

Квадрат со стороной 2017 можно разбить на равностороннюю сетку 20х23. Получаем количество узлов: [math](11 \cdot (19+1) + (12 \cdot (20+1)=472[/math] узла, что тоже меньше 909.
Поэтому нужно узлы заполнять чаще, но тогда круг перекрывает.
Итак, делаем вывод, что найдётся такой круг, который перекроет не менее более 11 точек, то есть, не менее 12.

Количество точек делим на количество узлов: [math]10000 \,\colon 472[/math] получаем, что найдутся группы по 21 точке и ещё группы с большим количеством точек (ещё 88 групп по 22 точки). Поэтому найдётся такой круг, который перекроет не менее 21 точки. И даже найдётся круг, который перекроет 22 точки в одной из 88 групп.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 16:05 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3194
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
3axap писал(а):
Квадрат со стороной 2017 можно разбить на равностороннюю сетку 20х23. Получаем количество узлов: (11⋅(19+1)+(12⋅(20+1)=472
узла


Кол-во узлов в квадрате на треугольной сетке равно 492.

Ну и вывод неверный. Для конкретной расстановки да, найдется такой круг. Но гарантии, что не будет для другой расстановки нет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Октагон в квадрате

в форуме Геометрия

Abbas

7

359

05 окт 2012, 11:03

Клетки в квадрате

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

5

488

10 ноя 2012, 17:08

Дед Мороз в квадрате

в форуме Интересные задачи участников форума MHP

chebo

36

644

06 янв 2017, 13:40

X в квадрате равно 1

в форуме Алгебра

NewSp

12

914

27 июл 2015, 19:07

Минусы и плюсы в квадрате

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

8

213

16 янв 2017, 02:38

Моноид на декартовом квадрате

в форуме Дискретная математика, Теория множеств и Логика

BAIN

0

219

06 июн 2013, 13:08

Вычислить вычет тангенса в квадрате

в форуме Комплексный анализ и Операционное исчисление

Samuil_Adam

3

398

04 фев 2014, 10:38

Все варианты расположения отрезков в квадрате

в форуме Комбинаторика и Теория вероятностей

AikoYogurt

1

250

02 апр 2014, 18:55

Расстояние каждой точки от начала координат и от точки (5;0)

в форуме Аналитическая геометрия и Векторная алгебра

Joshua

1

763

26 дек 2011, 16:13

Вычислить интеграл по отрезку от точки до точки

в форуме Интегральное исчисление

MurZ

8

463

03 ноя 2012, 21:51


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved