Эту задачу мне прислал мой юный подписчик в Телеграме. Задача с какого-то математического флеш-боя (что бы это ни значило), нечто вроде КВН для математиков, как я понял. И вот там такая задачка.
Назовем число промежуточным, если один из его соседей больше его, а второй — меньше его. Сколько существует способов расставить числа 1, 2, 3, 4 в ряд так, чтобы не было промежуточных чисел?
Условие есть, ответ есть. Вопрос в том, как решить. Попробуйте, пишите в комментариях.
Моё решение
Если у числа один сосед больше его, а другой меньше, то число промежуточное. Нам нужно, чтобы таких чисел не было в перестановке. То есть для внутренних чисел (второго и третьего в ряду из четырех) должно выполняться:
- Либо число больше обоих соседей (локальный максимум),
- Либо меньше обоих соседей (локальный минимум).
Примеры допустимых перестановок:
- Для 1, 3, 2, 4: 3 > 1 и 3 > 2 (максимум), 2 < 3 и 2 < 4 (минимум).
- Для 4, 2, 3, 1: 2 < 4 и 2 < 3 (минимум), 3 > 2 и 3 > 1 (максимум).
Как найти все такие перестановки?
1. Всего перестановок чисел 1, 2, 3, 4: 4! = 24.
2. Нужны только зигзагообразные перестановки:
- - Либо сначала рост, потом падение, потом рост (↑↓↑),
- - Либо сначала падение, потом рост, потом падение (↓↑↓).
3. Для 4-х чисел таких перестановок ровно 10:
- 5 перестановок начинаются с подъема (например: 1,3,2,4; 1,4,2,3; 2,4,1,3; 2,3,1,4; 3,4,1,2),
- 5 перестановок начинаются с падения (например: 4,2,3,1; 4,1,3,2; 3,1,4,2; 3,2,4,1; 2,1,4,3).
Почему именно 10?
Это следует из чисел Эйлера, которые подсчитывают зигзагообразные перестановки. Для 4-х элементов их количество равно 10.
Как вам задача? Напоминаю, что вы можете подписаться на мой Телеграм и присылать свои интересные задачи (не обещаю, что все разберу). Также, если вы скучаете по видео, можете поддержать канал, так как Дзен убрал монетизацию видео. А ниже я подобрал для вас ещё несколько интересных задач: