Кузнечик хочет попасть в лунку #621918

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

что такое "вершина" в данном случае??

вершина квадрата, который луг ))

чё курил?

мощно завернул, по полюк конопли наверное прыгает

размер лунки? вписана в квадрат?

Пусть у кошек учится - они делают лунку и никуда потом уже не прыгают.

Если лунка расположена в середине луга ,а прыгать начинает с вершины, то после первого прыжка он неизбежно там.

Снаряд в одну воронку дважды не попадает! :)))))

если прыгнуть из одного угла по диагонали к другому и лунка в центре, то он сразу там

какая-то, не важно расположение лунки и кузнеца не важно, рассматриваем все случаи сразу

короче есть конфигурация, когда не сможет попасть?

Прыгает По диагоналям куба по сетке с размером ячейки 1/2, 1/4, 1/16, 1/32 и так далее. Поскольку сетка всё время мельчает, то в идеале можно допрыгаться до любой точки квадрата.

Херасе, не важно. Я говорю СРАЗУ и ГАРАНТИРОВАНО. Это лучшее решение. Ты меня понимаешь?

если начинает с угла, а лунка не в центре и не касается середин сторон

если лунка ровно по центру, а кузнечик не в центре и не в вершинах, то он в нее не попадет

Есть,когда лунка за пределами луга. Ему алгоритм не позволит выпрыгнуть за ериметр.

когда лунка в вершине, он будет к ней приближаться, но не допрыгнет, не?

Тоже правильно. Или на любой точке периметра. Можно попасть только во внутренние точки.

Ты не понял, можно прыгать "туда -сюда". Вперед(середина) и сразу назад(четверть)

Опять вперед - (две с половиной четверти или пять восьмых) и так далее

Чтото напоминает писсуар: попаду - не попаду в лунку? :))))))))

Очень просто - по одной диагонали нужную координату напрыгал - допрыгиваешь до другой координаты.

Нужно простейшую программулинку написать с рандомными прыжками, и посмотреть что за фигура нарисуется.

может, внутри квадрата все точки для кузнечика доступны

на каждом шаге кузнечику доступны четыре точки, которые образуют квадрат со стороной 12 от дины стороны луга

*длины

по размещению таких квадратов ограничений нет

какие-то из всех возможных таких квадратов будут иметь вершину в лунке

Может в том случае если лунка не находится в вершине квадрата

Не факт что все точки пройдет. Только за мильенов миллиардов комбинаций. А если за час работы программы брать по 1500 рублей

То получится очень дорогой эксперимент..

см

моментально будет видна нарисованная фигура. Это называется графический метод решения.

Если лунка в вершине квадрата - то в нее попадет точно, просто прыгая постоянно к этой вершине. Так как лунка имеет ненулевой диаметр.

Проблема в некорректной формулировке. Только сейчас понял. Прыгать надо половину до вершины. Можно выпрыгнуть за середину стороны легко.

Прыгаем вперед, потом сразу назад, потом вперед и вперед и влево - гарантированный выход за периметр

С какой точки (внутри квадрата) должен быть соврешен прыжок и к какой вершине чтоб выпрыгнуть за периметр?

Если прыгать влево, то прыгнешь четверть диагонали. Или тогда передвижения кузнечика не только ортогональные... Ага. Тогда тем более можно напрыгать в любую точку.

Вообще не понимаю чего ты пишешь.

Я исходил из того, что прыгать можно только ортогонально. Если прыгать к вершине, то не выпрыгнешь.

Если лунка имеет координаты (e, pi) и является одномерной точкой, то численный эксперимент не поможет)))

Но всё равно с каждым прыжком сетка становится всё мельче. Можно попасть в любую точку последовательным приближением.

не становится сетка меньше

Может он только по рациональным точкам прыгает. Тогда никогда не допрыгнет.

половинится.

прицел на вершины луга идет

тоже хочет попасть в лунку

ты где все это берешь?

а чего? из интернета конечно, много раз писал

Дедушка у него - Никонор Иванович Интернет.

здравая мысль лунка это круг, попасть точно в точку не обязательно, достаточно в окрестность

Лунка имеет диаметр. Так что то что по рациональным - пофик.

Пусть он прыгает в единичном квадрате (00,10,01,11). тогда каждая его координата изменяется х->х/2 или х->1/2+х/2. Разложим каждую координату в бесконечную дробь в двоичной  системе, например, 0.75=0.11(0 в периоде). В условиях задачи каждый ход сдвигает дробную часть на разряд вправо и вставляет в первый разряд 1 или 0. Разложив координаты конечной точки в такие дроби, можно подойти к ним с любой наперед заданной точностью. выбрали е, Выбираем К разрядов каждой координаты конечной точки, разложили, пропрыгали, посмотрели, попали ли в е-окрестность конечной точки, если не попали, увеличили К, повторили. Конечно доказательство нестрогое...

По одной координате ты пришел к нужному значению, но где он при этом окажется по второй координате?

окажемся где захотим, потому в моих обозначениях что мы можем выбрать что нам вставить в первый разряд 1 или 0 одновременно в обоих координатах, мы же можем прыгнуть в 4 угла - как раз все комбинации из 0 и 1. Для примера допустим нам нужно в текущий момент вставить в Х 1, а в У 0 (х=0,****** -> х,1******; у=0,******-> у,0******). Это значит что нам нужно прыгнуть к вершине (1,0), ведь тогда х перейдет в (1+х)/2, а у перейдет в у/2

Кузнечик сидит в (0:0), попасть хотим в (0.5:0.2)

+ но в целом - концепт правильный. Т.е. надо разложить координаты на ряд дробей с дополнительным условием - количество элементов в рядах должно быть одинаковым

ничего не понял, но не окажемся где захотим. Ибо у тебя количество членов разное будет для одной координаты и для другой.

Ок, да. В любую точку может попасть. внутри периметра. Теперь понял решение.

0.5=  0,1 в двоичной 0.2= 0,(0011)в двоичной Допустим берем точность 8 знаков, значит 0.5=0,10000000, 0.2 = 0,00110011. идем с младших разрядов: первый прыжок к вершине (0;1), второй  - к вершине (0;1), третий - (0,0), 4й - к (0,0) итд, последний 8й к вершине (1,0). Итог попали в точку с (0.5,0.2) с точностью 1/2^7. не устроила точность, увеличили число 8. а абсолютно точно не попасть, ибо 0.2 - периодическая

Да, я понял. Начинаем с угла 0,0 и прыгаем по двойной записи начиная с конца.

по двоичной.

Выкладываю красивое решение, не мое Разобьем квадрат на (2^N)*(2^N) равных квадратов Докажем, что кузнечик может попасть в любой из них независимо от N по индукции N=0 - очевидно Пусть это верно для N, докажем для (N+1) возьмем любой из квадратиков (2^(N+1))*(2^(N+1)) и вершину, ближайшую к нему. Из этой вершины сделаем гомотетию этого квадратика с коэффициентом 2. Квадратик превратится в один из разбиения (2^N)*(2^N). Ч.т.д.

Я первый сказал что возможно.

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

Ладно, я не гордый.

Я согласен на медаль...

Медали все Базван забрал.

если лунка не нулего диаметра то допрыгает до любой включая на вершине

если нулевого то однозначно нет ибо множество точек до которых допрыгнет - счетно

Круглая лунка нулевого диаметра - это пять! :)

алгоритм: соединяем лунку с вершиной. прыгаем до вершины (до отрезка - проекции лунки на прямую кузнечик-вершина) прыгаем до лунки

В смысле? Кузнечик может прыгать ровно в точку посередине между своим положением и лункой. Если он находится на прямой от лунки к вершине - он не может по этой прямой допрыгать до лунки.

посередине между своим положением и вершиной.

в пределе он попадает в лунку, а так как лунка ненулевого диаметра то и за конечное чило прыжков

Обалдеть. Лунка на расстоянии 5 от угла. Мы вышли на прямую на расстоянии 15 от угла - и как мы попадем в лунку?

не верно. 1)ошибка в первом шаге индукции 2) при гомотетии вершины "уедут" в 2 раза и ничего не превратится

ты сначала нарисуй, а потом умничай кстати это решение автора задачи

индукция от 0*А=0, значит Х*А=Х - дурной тон. 2. Индукция не верна, т.к. кузнечик после гомотетии не может прыгать по вершинам до гомотетии и повторить последовательность прыжков. То, что автор, считает это решением не мои проблемы Решение: Ф - множество из которого кузнечик прыгает в лунку. Достаточно показать, что Ф(Н) растет с Н. Это довольно просто, особенно если свернуть квадрат в тор.

*площадь, конечно, растет

я вообще ничего не понял, если честно, что ты написал

Он может попасть в лунку только в том случае, если она находится на линии к вершине, которую выбрал кузнечик, но не саму вершину, так как вершины он никогда не достигнет.

допустим есть алгоритм попадания из квадрата к1 в к2 до гомотетии, после гомотетии, т.к. вершины, относительно которых построен алгоритм, сдвинулись - кузнечик попадет ровно в образ к2. никакой индукции

круглая лунка евстественно имеет не нулевой диаметр. Поэтому в лунку если она находится в вершине он допрыгает легко.