Олимпиадные задачи из источника «10 класс» - сложность 3 с решениями

Дана бесконечная последовательность многочленов <i>P</i>₁(<i>x</i>), <i>P</i>₂(<i>x</i>), ... . Всегда ли существует конечный набор функций  <i>f</i>₁(<i>x</i>),  <i>f</i>₂(<i>x</i>), ...,  <i>f</i>_<i>N</i>(<i>x</i>), композициями которых можно записать любой из них (например,  <i>P</i>₁(<i>x</i>) =  <i>f</i>₂(<i>f</i>₁(<i>f</i>₂(<i>x</i>))))?

В стране несколько городов, соединённых дорогами с односторонним и двусторонним движением. Известно, что из каждого города в любой другой можно проехать ровно одним путём, не проходящим два раза через один и тот же город. Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога не соединяла два города из одной губернии.

Пусть <i>P</i>(<i>x</i>) – многочлен со старшим коэффициентом 1, а последовательность целых чисел  <i>a</i>₁, <i>a</i>₂, ...  такова, что  <i>P</i>(<i>a</i>₁)= 0,  <i>P</i>(<i>a</i>₂) = <i>a</i>₁,  <i>P</i>(<i>a</i>₃) = <i>a</i>₂  и т. д. Числа в последовательности не повторяются. Какую степень может иметь <i>P</i>(<i>x</i>)?