Есть пять друзей и каждого друга есть своя ручка (все ручки разные ) . То сколькими способами можно раздать ручки так ; что бы ни кто из них не получил свою ручку .
Пронумеруем друзей и их собственные ручки от одного до пяти:
1,2,3,4,5.
Раздаваемые ручки будем располагать по порядку от первого друга к пятому, то есть комбинация цифр 12345 означает, что каждый друг получил собственную ручку.
==============================================
Рассмотрим задачу с точки зрения первого друга.
I ситуация.
Если первый из друзей просто поменяется ручками со вторым другом, то останется распределить три ручки, и это можно сделать только двумя способами, чтобы никто не получил свою ручку:
1 ↔ 2; ⇒ 21453, 21534 - 2 варианта.
⇒ 21345, 21354, 21435, 21543 - не подходят, так как в каждой комбинации хоть одна из цифр 3,4,5 стоит на своём месте.
II ситуация.
Если первый из друзей взял ручку второго друга, а второй взял ручку третьего:
IUV
ответ верный, проверил в экселе метод называется brute force )))
IUV
уточняю - мой метод проверки в экселе называется brute force )))
kamilmatematik100504
Понятно ; спасибо ) А как-то через комбинаторику решить нельзя ?
xERISx
Можно, очень сложной формулой через сложение/вычитание перестановок.
kamilmatematik100504
Ясно ; спасибо !) Просто задача была на олимпиаде ее нужно как можно быстрее решить ; лучше вашего метода нет )
xERISx
Тогда самый быстрый способ другой. Количество перестановок из 5 элементов Р(5)=5!=120. Расписать 120 пятизначных чисел займет минуты три, не больше. Еще максимум минуты две, чтобы вычеркнуть числа, в которых цифры стоят на своих местах. Итого время наглядного решения задачи 5 минут. :-)
kamilmatematik100504
Да ; но ошибок можно понаделать ... Поэтому ваш метод надежней
IUV
Расписать 120 пятизначных - это я и сделал в экселе заняло 5 минут а вот с нерестановками уже час бодаюсь и на могу выловить ошибку
Answers & Comments
Verified answer
Пронумеруем друзей и их собственные ручки от одного до пяти:
1,2,3,4,5.
Раздаваемые ручки будем располагать по порядку от первого друга к пятому, то есть комбинация цифр 12345 означает, что каждый друг получил собственную ручку.
==============================================
Рассмотрим задачу с точки зрения первого друга.
I ситуация.
Если первый из друзей просто поменяется ручками со вторым другом, то останется распределить три ручки, и это можно сделать только двумя способами, чтобы никто не получил свою ручку:
1 ↔ 2; ⇒ 21453, 21534 - 2 варианта.
⇒ 21345, 21354, 21435, 21543 - не подходят, так как в каждой комбинации хоть одна из цифр 3,4,5 стоит на своём месте.
II ситуация.
Если первый из друзей взял ручку второго друга, а второй взял ручку третьего:
1 ← 2; 2 ← 3; ⇒ 23145, 23415, 23541 - не подходят.
⇒ 23154, 23451, 23514 - 3 варианта.
Так как второй друг может взять любую из трёх ручек (3,4,5), то всего будет
3 · 3 = 9 вариантов:
23154, 23451, 23514, 24153, 24513, 24531, 25134, 25413, 25431.
Итак, если первый друг возьмет вторую ручку, то всего возможно
2 + 9 = 11 вариантов.
Так как первый друг может взять любую из четырёх ручек (2,3,4,5), то всего возможно
11 · 4 = 44 способа.
Ответ: 44 способа.
метод называется brute force )))
в экселе заняло 5 минут
а вот с нерестановками уже час бодаюсь и на могу выловить ошибку