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

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

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

чё курил?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

*длины

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

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

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

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

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

(29) см (18)

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

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

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

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

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

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

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

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

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

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

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

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

(43)половинится.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0.5=  0,1(0) в двоичной
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 - периодическая

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

по двоичной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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