Автор Тема: 33 богатыря  (Прочитано 1527 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн fortpost

  • Старожил
  • ****
  • Сообщений: 371
    • Просмотр профиля
    • E-mail
33 богатыря
« : 10 Январь 2018, 07:36:44 »
Тридцать три богатыря едут верхом по кольцевой дороге против часовой стрелки. Могут ли они ехать неограниченно долго с различными постоянными скоростями, если на дороге есть только одна точка, в которой богатыри имеют возможность обгонять друг друга?

Оффлайн South Paw Mary

  • Ветеран
  • *****
  • Сообщений: 628
    • Просмотр профиля
Re: 33 богатыря
« Ответ #1 : 10 Январь 2018, 21:09:08 »
Пусть лучше развернутся!

Оффлайн fortpost

  • Старожил
  • ****
  • Сообщений: 371
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #2 : 13 Январь 2018, 22:23:48 »
Ну так что, сдались все? Решение дать?

Оффлайн Race

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 1155
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #3 : 14 Январь 2018, 00:52:25 »
Единственное что приходит в голову, что если все богатыри стартуют в 1 момент времени, то их скорости должны быть кратны взаимно простым числам. Тогда определенную точку nx они все пересекут в различный момент времени.

Оффлайн fortpost

  • Старожил
  • ****
  • Сообщений: 371
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #4 : 14 Январь 2018, 02:02:23 »
Единственное что приходит в голову, что если все богатыри стартуют в 1 момент времени, то их скорости должны быть кратны взаимно простым числам. Тогда определенную точку nx они все пересекут в различный момент времени.
Да, направление мыслей ваших верное. Богатыри стартуют одновременно, в точке обгона. Попытайтесь найти решение для случая трех богатырей, а затем обобщить по индукции.

Оффлайн Race

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 1155
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #5 : 14 Январь 2018, 14:24:27 »
я уже плохо помню что такое индукция)
И так прикидывал и так, ничего не вышло.



Оффлайн fortpost

  • Старожил
  • ****
  • Сообщений: 371
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #6 : 14 Январь 2018, 21:02:05 »
Еще небольшая подсказка. В точке обгона может быть сколько угодно богатырей - хоть все 33 сразу.

Оффлайн Race

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 1155
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #7 : 15 Январь 2018, 00:27:19 »
Э. Как бы сказать помягче) я решал обратную задачу, а именно что в определенной точке пути может находиться только 1 богатырь)


Для правильного варианта вообще ничего в голову не идет, даже для 2 богатырей.

Оффлайн Леонид

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 6728
    • Просмотр профиля
    • Домашняя страница
Re: 33 богатыря
« Ответ #8 : 15 Январь 2018, 03:10:44 »
Ну для двух-то понятно. Один вдвое быстрее другого.

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1636
    • Просмотр профиля
Re: 33 богатыря
« Ответ #9 : 15 Январь 2018, 12:21:26 »
Для двух богатырей скорости должны соответствовать соотношению:
v2/v1 = (m+1)/m
где m - положительное целое число.

Если богатырей трое, то для каждой пары будет
v2/v1 = (m+1)/m
v3/v2 = (n+1)/n
v3/v1 = (k+1)/k
где m, n, k - положительные целые числа.
Но эти числа уже не произвольные, а между ними должно выполняться соотношение
(k+1)/k = ((m+1)/m) * ((n+1)/n) = (m*n + m + n + 1)/(m*n)
откуда
m*n = k*(m + n + 1)
Это уравнение можно решить следующим образом, задаться произвольным k и произвольным положительным целым p. Получаем m как
m = p*k
n = (p*k + 1)/(p-1)
Отсюда видно, что для p=2, n всегда будет получаться целым и легко получить коэффициенты:
k=1; m=2; n=3;
k=2; m=4; n=5;
k=3; m=6; n=7;
При желании можно и для других p найти, но уже подбором, например при p=3
k=3; m=9; n=5;

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

Оффлайн Race

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 1155
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #10 : 15 Январь 2018, 12:59:23 »
Можно пойти другим путем.
Для начала предположим что стартуют они из одной точки, тогда обязано выполняться равенство:

n1S/V1=n2S/V2

n1/n2=V2/V1

то есть n1/V1=n2/V2=k - некоторый общий делитель.

К примеру n1=4; V1=2, тогда k=2; n2=6; V2=3.

Можно экстраполировать на любое кол-во богатырей, в роли Vn выбирать простые числа, в роли k, так же некоторое простое число.

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

Вся идея в том, что для бесконечно долгого движения, единственный простой вариант, что любое кол-во богатырей попадают в точку обгона (можно назвать её точкой финиша, либо старта) одновременно.
Вот только мучает меня ограничение в скорости, и нужно ли оно, а так же как доказать, что оно нужно, либо не нужно.
Как Петька, я нутром чую, что V1...Vn с k, должны быть взаимно простыми) а доказать не могу.

Вроде бьется, так как общие делители, кроме k, будут отсутствовать, то траектории движения точек уравняются только в моменты равенства, когда все богатыри будут находиться на финише.

Тогда скоростями для богатырей будет ряд простых чисел: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199....
За k можно принять 2.
Но такое решение, лично я бы не принял, так как оно не строго математическое, а частично интуиционное.




« Последнее редактирование: 15 Январь 2018, 13:23:15 от Race »

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1636
    • Просмотр профиля
Re: 33 богатыря
« Ответ #11 : 15 Январь 2018, 13:28:50 »
Рейс, n1 и n2 не могут отличаться больше чем на 1. Фактически эти числа означают сколько кругов проедет каждый из богатырей между двумя встречами в исходной точке. Если разница кругов больше 1, значит они встречались (был обгон) где-то вне допустимой точки.

Оффлайн Головолом

  • Старожил
  • ****
  • Сообщений: 428
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #12 : 15 Январь 2018, 13:30:59 »
Странник, ко второму обгону разница будет уже в 2 круга
А скорости, видимо, должны быть подобраны так, чтобы самого медленного самый быстрый второй раз обгонял тогда, когда предпоследний обгонял самого медленного в первый раз. Т.е. прежде, чем встретиться всем в одной точке, должны будут повстречаться в этой точке попарно, по три, по одиннадцать в разных комбинациях
« Последнее редактирование: 15 Январь 2018, 13:47:46 от Головолом »

Оффлайн Race

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 1155
    • Просмотр профиля
    • E-mail
Re: 33 богатыря
« Ответ #13 : 15 Январь 2018, 13:33:09 »
Странник,
изложите, пожалуйста, данное ограничение языком математики, либо логики, как я уже писал ранее, именно с данным ограничением у меня затык.


Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1636
    • Просмотр профиля
Re: 33 богатыря
« Ответ #14 : 15 Январь 2018, 13:52:31 »
Странник, ко второму обгону разница будет уже в 2 круга
В данном примере Рейса действительно все работает, просто он взял число кругов, соответствующее двум обгонам в исходной точки, то есть их просто можно сократить на 2. Но если бы они не сокращались промежуточный обгон не попал бы в исходную точку.

Странник,
изложите, пожалуйста, данное ограничение языком математики, либо логики, как я уже писал ранее, именно с данным ограничением у меня затык.
Языком математики я излагал уже V2/V1 = (m+1)/m, то есть как у Вас, но не просто 2 целых, а отличающихся на единицу. А по логике, богатыри стартуют из одной точки и едут с разными скоростями. Как только путь пройденный быстрым станет на 1 круг превышать путь медленного произойдет обгон. И он должен по условию в исходной точке произойти. Допустим я взял Вашу формулу и задал
n1 = 3
n2 = 5
Когда первый проедет 3 круга, а второй 5, они действительно встретятся в исходной точке. Но когда первый проедет 1.5 круга, а второй 2.5 они тоже встретятся на противоположном конце круга.