Популярно о науке

Previous Entry Share Next Entry
Решение предотпускной задачки.
ahiin
Условие здесь.

Ответ:

Решение.
Переписав исходное неравенство в следующем виде:

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

Для я даже сварганил картинку. Для удобства нарисован только первый квадрант, обсуждаемый эллипс (обозначим его самого , а его площадь — ) изображен красным, решения — жирные голубые точки.

ell

Если теперь каждой точке-решению сопоставить единичный квадрат, то площадь фигуры, получающейся их объединением, будет в точности равна . На рисунке граница фигуры изображена сиреневым цветом.

Собственно, до идеи, что число решений что-то маленькое, причем вклад этого маленького с ростом все менее и менее значим, додумались почти все. Строгое доказательство этого "очевидного" факта потребует, тем не менее, некоторых усилий.

Очевидно, , или, что то же самое (используя формулу площади эллипса), Неплохо бы иметь аналогичную оценку сверху. Этим мы сейчас и займемся.

UPD. Новое решение, простое и красивое.
Разрежем эллипс на криволинейные отрезки единичной длины (последний из них может быть меньше единицы, это не меняет сути). Очевидно, что любой из таких отрезков может быть вписан в единичный квадрат. Который, в свою очередь, может пересекаться не более, чем с четырьмя квадратмами координатной сетки (показана зеленым).
Отсюда тривиально:


Здесь — длина эллипса . Дабы не возиться с эллиптическими интегралами, просто отметим, что

Окончательно имеем:

Деля почленно на и переходя к пределу, получим, что


Дабы сократить размер портянки, я дальше буду технические действия пропускать. Если кому-то покажется, что ход решения освещен недостаточно — скажите, я распишу подробнее.

Непосредственно из картинки видно, что точки нашей "квадрированной" фигуры не могут отстоять от эллипса дальше, чем на (длину диагонали единичного квадрата). Давайте отступим от эллипса наружу на и поглядим, что за фигура у нас получится.

Исходя из параметрического представления для : тривиальным дифференцированием, поворотом по часовой на прямой угол и нормировкой, получим, что внешняя нормаль к будет иметь вид:
Отсюда, параметрическое представление "кривой отступа" будет следующим:
Мрачновато, как по мне. К счастью, несложно показать, что эта кривая целиком лежит внутри объемлющего эллипса с полуосями и Этот эллипс изображен на картинке синим.


Отвлекаясь от груды формул. Что именно тут произошло? Все просто: мы взяли нормаль к эллипсу , отступили вдоль нее на некоторое расстояние, посмотрели на получившуюся кривую, ужаснулись и для упрощения дальнейшей жизни, обвели ее снаружи еще одним эллипсом, который назвали .

Очевидно, или, что то же самое,
Объединяя левое и правое неравенства, окончательно имеем:

Деля почленно на и переходя к пределу, получим, что

  • 1
не нужно столько формул - нам надо оценить количество квадратиков, которые пересекаются с эллипсом, но не содержатся в нём целиком (про их центры мы не знаем, окажутся они внутри эллипса или снаружи) - их, в сущности, даже можно почти точно посчитать, потому что когда эллипс переходит из одного в другой, он пересекает вертикальную или горизонтальную прямую сетки. Почти - потому что он может проходит через узлы сетки, и тогда надо разбираться, считаем мы за один, за два или как, в любом случае это всё пропорционально ширине и высоте эллипса и пренебрежимо мало по сравнению с площадью...

Ну оно-то сразу ясно, что "прибавка" площади к эллипсу будет как-то пропорциональна его длине. В свое время за немногим более развернутое рассуждение "на пальцах" мне эту задачку зачли.

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

А с отступом решение надежно как лом: отступили вдоль нормали, глянули, что за кривая получилась, ужаснулись делу рук своих и от греха обвели еще одним эллипсом.

А не, все в порядке, это просто я дурак.
См. ниже.

Edited at 2014-08-07 01:25 pm (UTC)

Самокритика избыточна и сильно несправедлива. Клина все хватают (периодически).
А лично я так чаще среднего, похоже.

Думал, очевидно....

Сразу можно сказать, что один криволинейный отрезок эллипса шириной и высотой меньше стороны h пересекается не более чем с 4 квадратиками (думаю это не надо доказывать?).
Соответственно, количество квадратиков полностью покрывающих эллипс (границу) не более чем 4 L / h (оценка сильно завышена, но важно что пропорциональна, с коэффициентом пропорциональности не больше 4.

Re: Думал, очевидно....

Ататай. Апдейтнул.

  • 1
?

Log in

No account? Create an account