Главная » Четыре гостя при входе в ресторан отдали швейцару..
22:24

Четыре гостя при входе в ресторан отдали швейцару..


Задача. Комбинаторика.

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

Решение.

Занумеруем гостей цифрами 1, 2, 3, 4 и так же занумеруем их шляпы. Считаем, что шляпа с данным номером принадлежит гостю с этим же номером (то есть, например, шляпа 2 принадлежит гостю 2). Тогда каждый вариант получения шляп обозначается четырёхзначным числом, составленным из цифр 1, 2, 3 и 4, в котором номер позиции цифры есть номер гостя, а сама цифра есть номер полученной им шляпы (номера позиций будем считать слева направо). Например, комбинация 4132 означает, что первый гость получил четвёртую шляпу, второй — первую, третий — третью, а четвёртый — вторую. Такой вариант не годится по условию, поскольку третий получил свою шляпу. Теперь понятно, что нужно сделать — выписать по возрастанию все четырёхзначные числа, содержащие по одной цифре 1, 2, 3 и 4, такие, что никакая цифра не стоит на позиции со своим номером. Эти числа выписаны ниже под чертой. Красные цифры над чертой — номер позиции (номер гостя), с которым не должна совпадать цифра в соответствующем столбце (номер шляпы). 

1 2 3 4
2 1 4 3
2 3 4 1
2 4 1 3
3 1 4 2
3 4 1 2
3 4 2 1
4 1 2 3
4 3 1 2
4 3 2 1

Как видим, всего имеется 9 вариантов нужной раздачи шляп. Вариантов может быть довольно много, но в некоторых случаях, тем не менее, самый быстрый способ решения задачи — разумно организованный перебор. 


Похожие материалы:
Нашли ошибку на сайте? Напишите в комментариях!
Категория: Перебор слов, комбинаторика | Просмотров: 187 | Добавил: Ученик | Рейтинг: 5.0/1