Стопка из 5 монет. Комбинаторика.Неужели в лоб перебор?

[bitcoin]

Цитата:

Банкир Александр Иванович, увидев, что 5 монет стоят в стопке друг на друге не в порядке возрастания номинала, указал на это своей новой ассистентке Елене. В ответ она заявила: "Каждая монета либо находится на своем месте, либо на соседнем". Сколько способов расставить монеты в соответствии с этим условием Елены?

У меня есть некоторые соображения, но мне кажется, что задача как-то проще может решаться, сможете помочь разобраться, пожалуйста?

Давайте договоримся, что речь идет о монетах $1,2,3,4,5$ рублей. Требование Банкира в том, чтобы они были расположены именно в таком порядке.

Идея №1

Для монеты 1 рубль может быть 2 места, для монеты 2 рубля - 3 места, для монеты 3 рубля - 3 места, для монеты 4 рубля - 3 места, а для для монеты 5 рублей - 2 места. Но ответ $2\cdot 3\cdot 3\cdot 3\cdot 2$ мне кажется заведомо неверным, так как тут нельзя сказать, что эти комбинации независимы друг от друга (не знаю - правильно ли я аргументировал - почему этот вариант не подходит).

Идея №2

А давайте просто в лоб выпишем все варианты:

Сначала первые 2 монеты не будем трогать.

1) $1,2,3,4,5$

2) $1,2,3,5,4$

3) $1,2,4,3,5$

4) $1,2,4,3,5$

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

5) $1,3,2,4,5$

6) $1,3,2,5,4$

Теперь еще варианты, когда двигаем монету 1 рубль.

7) $2,1,3,4,5$

8) $2,1,3,5,4$

9) $2,1,4,3,5$

Больше вариантов не вижу (но при таком переборе, я вполне мог что-то потерять). Наверняка же есть вариант решения поинтереснее? Ведь если монет станет 10, то мозг взорвется все перебирать=)

[realeugene]

Не понял условие. Что значит "сколько монет можно раставить"?

[bitcoin]

realeugene в сообщении #1611835 писал(а):

Не понял условие. Что значит "сколько монет можно раставить"?

Извините, пожалуйста, исправил условие, теперь все верно в нем) При быстром наборе немного затупил)

[dgwuqtj]

Вы не пробовали вручную посчитать ответы для маленьких количеств монет? Мне кажется, будет что-то в духе чисел Фибоначчи.

[realeugene]

Все монеты разные? Место монеты определяется её положением в строго возрастающей последовательности?

-- 30.09.2023, 14:56 --

Разумеется, это простейшая программистская задача на рекурсивные функции.

Добавляем ещё одну монету. Она может либо стать на последнее место, и тогда число таких вариантов равно полному числу вариантов предыдущей расстановки монет. Либо она может опуститься на предыдущее место. Дальше расписывать не буду, чтобы не приводить полное решение.

[Yadryara]

dgwuqtj в сообщении #1611838 писал(а):

Мне кажется, будет что-то в духе чисел Фибоначчи.

И без всякого духа.

bitcoin, у вас ошибка вот здесь:

bitcoin в сообщении #1611834 писал(а):

3) $1,2,4,3,5$

4) $1,2,4,3,5$

[bitcoin]

Спасибо большое за помощь!

$$ \begin{array}{cc} 1 & 2 \\ 2 & 1 \\ \end{array} $$

$$ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \\ 1 & 3 & 2 \\ \end{array} $$

$$ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \\ 1 & 2 & 4 & 3 \\ 1 & 3 & 2 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \\ $$

Про лишний дубль - понял, спасибо.

Но почему здесь Фиббоначи появляется?) Я думал количество монет уменьшить, но показалось, что 5 монет - это итак уже мало.

Но здесь в любом случае только перебор, да?

[dgwuqtj]

Вам же уже предложили взять и доказать рекуррентное соотношение. То есть построить взаимно-однозначное соответствие между расстановками для $n$ монет и расстановками для $n - 1$ и $n - 2 $ монет. Никакого перебора, кроме случаев $n = 0$ и $n = 1$.

[bitcoin]

realeugene в сообщении #1611839 писал(а):

Либо она может опуститься на предыдущее место

Кажется я понял, спасибо.

Можно сказать, что у нас была предыдущая расстановка

Пусть $p(a_n)$ - какая-то перестановка $a_1a_2....a_n$

Если у нас была такая расстановка $p(a_n)b_1$, то добавить $b_2$ можно так $p(a_n)b_2b_1$ или $p(a_n)b_1b_2$

Количество способов поставить так $p(a_n)b_2b_1$ равно количеству перестановок $p(a_n)$, а количество способов поставить так $p(a_n)b_1b_2$ равно количеству перестановок $p(a_n)b_1$ (что тоже самое, что и $p(a_{n+1})$.

Наверное, как-то так. Но может немного кривовато расписал)

-- 30.09.2023, 15:44 --

Тут наверное, как-то по индукции как раз это доказывается)

-- 30.09.2023, 15:45 --

bitcoin в сообщении #1611834 писал(а):

Идея №1

Для монеты 1 рубль может быть 2 места, для монеты 2 рубля - 3 места, для монеты 3 рубля - 3 места, для монеты 4 рубля - 3 места, а для для монеты 5 рублей - 2 места. Но ответ $2\cdot 3\cdot 3\cdot 3\cdot 2$ мне кажется заведомо неверным, так как тут нельзя сказать, что эти комбинации независимы друг от друга (не знаю - правильно ли я аргументировал - почему этот вариант не подходит).

А вот здесь я правильно объяснил - почему идея №1 не сработает, подскажите, пожалуйста?

[TOTAL]

Для пяти монет полный перебор быстрее Фиббоначи. Третья монета
1) на своем месте (4 варианта)
2) ниже (2 варианта)
3) выше (тоже 2 варианта)

А для $n$ штук монет можно объединить их в пары (внутри которых они поменялись местами) и получить $\sum_{k=0}^{[n/2]}C_{n-k}^k$

[dgwuqtj]

bitcoin в сообщении #1611847 писал(а):

А вот здесь я правильно объяснил - почему идея №1 не сработает, подскажите, пожалуйста?

Потому что у второй монеты не 3 варианта, а в зависимости от того, где первая монета.

[realeugene]

TOTAL в сообщении #1611848 писал(а):

Для пяти монет полный перебор быстрее Фиббоначи.

В смысле "быстрее"?

[Yadryara]

Быстрее решить задачу, чем правильно написать знаменитое слово

[TOTAL]

realeugene в сообщении #1611850 писал(а):

TOTAL в сообщении #1611848 писал(а):

Для пяти монет полный перебор быстрее Фиббоначи.

В смысле "быстрее"?

В том смысле, что задумываться о Фиббоначи Фибоначчи не надо, сразу ответ получил.

-- Сб сен 30, 2023 21:08:19 --

Yadryara в сообщении #1611851 писал(а):

Быстрее решить задачу, чем правильно написать знаменитое слово

Я сначала написал правильно. Но потом посмотрел, как у них, и исправил на неправильно. Тьфу на них.

[svv]

Банкир Александр Иванович, увидев, что 5 монет стоят в стопке друг на друге не в порядке возрастания номинала, вежливо указал на это своей новой ассистентке Елене. В ответ она заявила:
— Не надо меня учить! Каждая монета должна находиться либо на своем месте, либо на соседнем.
Сколько способов расставить монеты в соответствии с этим условием Елены?