Математическое и загадочное

[Рогожников Евгений]

Нашёл более максимальное решение

Изменено 24 февраля пользователем Рогожников Евгений

[E.K.]

On 22.02.2024 at 16:58, _Иван said:

Фанклубни собрались в поход! Да вот только не любят далеко уходить.

На первый взгляд - ничего особо сложного. Все вышли, потом первый (на позиции 10) остаётся на месте, а остальные возвращаются в офис. Девять клубней встают на позиции 11-19. Средние 8 вернулись в офис. Потом эти 8 встают на позиции 20-27. Ну и так далее. Значит, в задачке есть какая-то закавырка...

[_Иван]

Так они дойдут до n^2/2, а хотят уйти заметно дальше. Но смогут ли?

[E.K.]

8 hours ago, _Иван said:

Так они дойдут до n^2/2

Ну, если он один, то дойдёт до позиции 1, а не 1/2. Если двое - то позиции 3. Трое до 6. Функция Туризм() =

 

Туризм(1) = 1.

Туризм(n) = Туризм(n-1) + n.

 

То есть, (n+1)*n/2

 

Дальше думать не могу, поскольку я в Барселоне после напряжённого дня на MWC...

[E.K.]

On 24.02.2024 at 11:15, Рогожников Евгений said:

Нашёл более максимальное решение

Как? Я сдаюсь...

[_Иван]

Если бы их было трое, то до куда они могли бы дойти? 6 --- очевидно, но не смогут ли они пройти дальше каким-нибудь хитрым образом?

 

Хорошая задачка, честное слово. Я долго думал

[E.K.]

Ааа! Действительно. +1.

Но над случаями >3 что-то мозг пока совершенно не готов работать.

[E.K.]

Ничего себе меня закрутило! Аж на три месяца забыл про эту задачку (и про эту ветку). Надеюсь, что сейчас будет немного досуга - надо её додумать...

[E.K.]

Реально так закрутило, что вот только что было полчаса свободного времени и свежая утренняя голова. Посему, поскольку за 3 месяца никто так и не удосужился выложить решение, то у меня примерно вот так получилось:

 

Надо максимально далеко поставить одного клубня. Делаем так: от двери "||" ставим n-1 клубней "**...**":

 

||**...**___

 

Потом n-2 клубня идут в офис, самый крайний остаётся на месте:

 

||__.._*___

 

Затем все оставшиеся клубни (n-2 и ещё один) встают за самым крайним, который n-1:

 

||__.._***...*__

 

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

 

Итого, функция Туризм(n) = 2n-2+Туризм(n-1)

 

Туризм(n) = n*(n-1)+1

 

10 клубней уйдут на 91 шаг от офиса. То есть, примерно на 50-60 метров. Недалеко получилось...

[E.K.]

6 hours ago, E.K. said:

Туризм(n) = n*(n-1)+1

10 клубней уйдут на 91 шаг от офиса.

Но как доказать, что это максимальное значение?...

[_Иван]

11.06.2024 в 03:54, E.K. сказал:

Недалеко получилось...

Недалеко  По такой формуле, четыре фанклубня могут отойти на 13 шагов. Максимум ли это?

 

Подсказка:

Спойлер

Мы выяснили, что один фанклубень может уйти на 1 шаг, вдвоём --- на 3 шага, втроём --- на 7 шагов.

 

[E.K.]

On 13.06.2024 at 13:53, _Иван said:

Подсказка:

  Hide contents

Мы выяснили, что один фанклубень может уйти на 1 шаг, вдвоём --- на 3 шага, втроём --- на 7 шагов.

 

xx_

_xxx_

_x_x_

xx_x_

___xxx_

___x_xx

 

И что? Туплю...

[E.K.]

On 13.06.2024 at 13:53, _Иван said:

По такой формуле, четыре фанклубня могут отойти на 13 шагов. Максимум ли это?

Сдаюсь. У меня больше 13 для 4х не получается..

[E.K.]

Да, согласен. 4 клубня могут добраться до позиции 15. Трое по максимуму встают вот так: 0001011, добавляем ещё одного:

00010111

00011101

11010001

01110001

00000001 - позиция 8, он становится "дверью" для троих оставшихся. 8+7=15. Каждый новый примерно удваивает дальность похода:

 

Туризм(n) = n^2 - 1

 

10 клубней уйдут на 1023 шага, то есть на примерно 700-800 метров.

[_Иван]

Верно! Я не знаю, как доказать, что это максимум, но похоже, что дальше уйти не получится.

 

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