100 Degree Function

[Note: I believe that $P$ should be $f$ . - Calvin]

We utilize the useful lemma that $(a-b)|(P(a) - P(b))$ for all integers $a,b$ . The proof is trivial and will be skipped. Let $\deg P = n$ . Suppose $P(P(a)) = a$ and $P(a) = b$ , $P(P(c))=c$ and $P(c)=d$ . Then $(a-c)|(b-d)$ and $(b-d)|(a-c) \implies a-c = \pm (b-d)$ . One also knows $(a-d)|(b-c)$ and $(b-c)|(a-d)$ , which implies that $a-d = \pm(b-c)$ . By doing a little casework on the signs of the $\pm$ and utilizing $a \neq b$ , one quickly deduces $a+b = c+d$ . [Note: This is the main equation, that $n+m$ is a constant. - Calvin]

Now let $a$ be a solution to $P(P(a)) = a$ . Then any $z$ such that $P(P(z)) = z$ is a root of $x + P(x) - a - P(a)$ , which has at most $n$ roots so $P(P(n)) = n$ has at most $100$ solutions when $\deg P = 100$ . When we enforce $n < m$ for $P(n) = m$ and $P(m) = n$ there are at most $50$ solutions then.

Choose $f(x) = 100 - x + \prod_{i=0}^{99} (x-i)$ . Note that for $0 \le i \le 100$ we have $f(i) = 100 - i, f(100 - i) = i$ . Clearly this is an integer polynomial and satisfies the problems conditions to yield $50$ pairs (namely, $(i, 100-i)$ for all $0 \le i \le 49$ ). As we previously proved there are at most $50$ solutions, it follows $50$ is the maximum number of pairs as we showed it was obtainable and thus we are done. [Note: There are of course many such polynomials. The one I prefer is $f(x) = -x + \prod_{i=1}^{50} (x^2-i^2)$ . - Calvin]

Recall that for all integers $a$ and $b$ the number $a-b$ divides $f(a)-f(b)$ . Suppose the pairs are $(n_1,m_1), (n_2,m_2),...,(n_k,m_t)$ . Then $n_i-n_j$ divides $m_i-m_j$ for all $i\neq j$ and vice versa, thus $n_i-n_j=\pm(m_i-m_j)$ . For any three distinct $i,j,k$ , we have $0=(n_i-n_j)+(n_j-n_k)+(n_k-n_i)=\pm(m_i-m_j)\pm(m_j-m_k)\pm(m_k-m_i)$ It is easy to see that this is only possible if either all signs on the right are pluses or all signs are minuses. Doing this for all possible triples of indices (under the assumption that we have more than two pairs) we get that either for all $i\neq j$ we have $n_i-n_j=m_i-m_j$ or for all $i\neq j$ we have $n_i-n_j=m_j-m_i.$

In the first case, we get $m_i-n_i=m_j-n_j$ for all $i$ and $j$ . Suppose $m_i=n_i+c$ for all $i$ . Take any $i\neq j$ and note that $n_i-m_j$ must divide $m_i-n_j$ and vice versa. So $n_i-m_j=\pm(m_i-n_j)$ . If the sign is plus, then we get $c=0$ , which is impossible. If the sign is minus, then we get $n_i=n_j$ , which is also impossible.

In the second case, $n_i+m_i$ is the same for all $i$ . Thus the polynomial $f(x)+x$ takes the same values at $n_1,n_2,...,n_t; m_1,m_2,...,m_t$ . Because $\deg (f(x)+x)=100,$ this implies that $2t\leq 100,$ so $t\leq 50$ .

To show that $50$ is possible, consider $f(x)=1-x-\prod \limits_{i=-49}^{50} (x-i)$ Note that for all $n=-49,-48,...,0$ we have $f(n)=1-n$ and $f(1-n)=n.$

Therefore the answer is $50$ .

Let f(x)= a {0}x^100+a {1}x^99+...+a {100} (1)_ For any non-constant polynomial,there is not exist a function that f[f(x)]=x for all x is a real number. Hence, the some number of x will be the solutions. By substituting the (n {1},m {1}) until (n {50},m {50}) into (1) , we can form 100 equation by using f(n)=m and f(m)=n . When (n {51},m {51}) , we can form 102 equation. It will be a contradiction for non-constant polynomial because a {0}-a {100} just have 101 unknown only.Therefore,the number of pairs (n,m) have maximum of 50 .

from the fact that f(n) = m and f(m) = n, we can deduce that (f(n)-f(m))/(n-m) = -1, which means, if we connect the points (n,f(n)) and (m,f(m)), we will end up with a straight line of gradient -1. hence we can try to find the maximum number of intersections between the line y = -x and the graph of y = f(x). we can easily deduce that the maximum number of intersections is 100, which implies there's a maximum of 50 pairs. then we can construct the function that satisfies this property, and conclude that 50 is the answer.

For each pair (m,n) that satisfies the conditions of the problem we have that f(f(n))=f(m)=n. Similarly f(f(m))=m. Also, if f(f(n))=n then n can be in a pair, namely (n,f(n)) or (f(n),n), whiever satisfies the conditions of the question. Now since f(f(n))-n cannot be the zero polynomial, it must be a polynomial of degree 200 with integer coefficients. Therefore these n are eligible to be in a pair. But, the question says that n<m, so n cannot equal f(n). So since f(n)-n cannot be the zero polynomial, it must be a polynomial of degree 100 with integer coefficients. Therefore there are only 100 integers that are eligible to be in pairs. Since each pair contains two numbers and each number can only be in one pair there are at most 50 pairs that satisfy the conditions of the question.