Всесиб 2026, 10 класс, задача 3
( баллов) Отрезок разделен точками на частей. Каждый из отрезков разбиения нужно сделать стрелкой так, чтобы стрелок, указывающих налево, было столько же, сколько указывающих направо, и для каждой стрелки количество других стрелок, на которые она указывает, отличалось от аналогичного количества у остальных стрелок.
Например, в такой расстановке стрелок они показывают соответственно на других стрелок, и она не удовлетворяет условиям. Найти количество всех расстановок стрелок, удовлетворяющих условиям.
Ответ. Количество хороших расстановок равно .
Решение. Будем называть -ой -ую слева направо стрелку, . Произвольная стрелка может указывать на других, всего возможных значений, и все эти числа должны различаться у всех стрелок, поэтому числа, на которые указывают последовательно первая, вторая, , двадцатая стрелки - это некоторая перестановка чисел . Заметим, что числа и могут стоять только на крайних местах этой перестановки, так как не указывать ни на одну или указывать сразу на все остальные стрелки могут только крайние стрелки. При этом возможны два варианта: первая и -ая стрелки обе указывают налево, или наоборот, первая и -ая стрелки обе указывают направо. Далее берём числа и , они могут стоять в перестановке только на местах и , перед крайними с соответствующих концов, причём снова, обе стрелки либо одновременно указывают направо, либо одновременно указывают налево. Продолжая так далее, мы разобьём все стрелки на пар: -ая и -ая, -ая и -ая, -я и -ая, , -я и -я, стрелки в парах согласованно указывают в любую из двух возможных сторон, в -ой паре одна стрелка указывает на стрелок, а вторая - на стрелок, . Кроме того, по условию, налево и направо указывают по стрелок, поэтому ровно в пяти парах стрелки указывают направо, и в пяти - налево. Таким образом, общее число всех расстановок стрелок, удовлетворяющих условию, равно количеству выборок пяти из десяти пар, указывающих направо, то есть .
Замечено, что количества стрелок, на которые указывают другие стрелки, это перестановка чисел
Замечено, что числа и могут стоять только на крайних местах этой перестановки и как ориентированы там стрелки (ещё 1)
Указано разбиение на пары
Указана одинаковая ориентация стрелок в парах
Подсчитано число возможных ориентаций всех стрелок при условии того, что налево и направо указывают по стрелок