2023 SSMO Tiebreaker Round Problems/Problem 3

Problem

For $n\geq4,$ let $a_n$ be the maximum possible value of $P(n+1)$ given that $P(x)$ is a $n$ degree monic polynomial that satisfies $P(i)\in\{1,2,3\dots,n\}$ for $1\leq i \leq n.$ If $\frac{m}{n} = \sum_{n=4}^{\infty}\frac{a_n-n!}{3^n},$ for relatively prime positive integers $m$ and $n,$ find $m+n.$

Solution