Сколькими способами можно расставить 2025 человек разного роста так, чтобы каждый, кроме самого низкого, был выше по крайней мере одного из своих соседей?
Сколькими способами можно расставить 2025 человек разного роста так, чтобы каждый, кроме самого низкого, был выше по крайней мере одного из своих соседей, но при условии, что третий и пятый по росту снизу не должны стоять рядом?
Обозначим n = 2025 и пронумеруем людей по росту от 1 (самый низкий) до n (самый высокий).
Следует заметить, что условие «каждый, кроме самого низкого, был выше по крайней мере одного из своих соседей» оказывается равносильно требованию, чтобы в перестановке не было «локальных минимумов» (то есть таких элементов, которые меньше обоих своих соседей), за исключением элемента 1, который и так является наименьшим.
Важно, что все люди имеют разный рост, и существует следующий способ построения перестановки с требуемым свойством. Начнём с единственного элемента – 1. После...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
