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

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

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

Решение.

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

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