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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 00:26 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
923 раз в 872 сообщениях
Очков репутации: 131

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 01:03 
В сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 02:04 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
923 раз в 872 сообщениях
Очков репутации: 131

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 09:37 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
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, 09:48 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 10:47 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Точки в квадрате
СообщениеДобавлено: 19 сен 2017, 12:27 
В сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

Добавить очки репутацииУменьшить очки репутации
Доказывается от противного. Положим, круг не может перекрыть 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, 15:05 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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


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

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

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

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

в форуме Размышления по поводу и без

Spirin

46

1313

21 фев 2019, 07:40

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

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

NewSp

12

2343

27 июл 2015, 18:07

5 окружностей в квадрате

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

Iliodor

7

308

26 мар 2020, 22:48

Делимость на 4 в квадрате

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

Poman092309

16

454

29 ноя 2020, 17:34

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

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

chebo

36

1540

06 янв 2017, 12:40

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

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

Xenia1996

8

506

16 янв 2017, 01:38

Две четвертьокружности и окружность в квадрате

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

Iliodor

8

196

17 июн 2020, 02:13

Верблюд в квадрате. Часть 2

в форуме Размышления по поводу и без

Spirin

3

244

06 мар 2019, 18:24

Минимальное кол-во цветов в квадрате 6х6

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

McMurphy

2

118

19 июл 2023, 15:10

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

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

AikoYogurt

1

398

02 апр 2014, 17:55


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



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

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


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

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

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

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