The Biggest Degree

Let $f(x) = p(x) - x$ . The system given is equivalent to:
1. $\ f(i) = 0$ for every integer $i$ with $1 \leq i \leq n$
2. $\ f(-1) = 1672$
$3.\ f(0)$ is an integer.

From (1) and the Remainder-Factor Theorem it follows that $f(x) = A\prod_{i = 1}^n (x - i)$ . The degree of $\prod_{i = 1}^n (x - i)$ is $n$ , which is same as the degree of $f(x)$ , so $A$ is a constant.
(3) is equivalent with " $An! = k$ , where $k$ is an integer."
(2) is equivalent with $A(n+1)!(-1)^n = 1672$ , or $k(n+1)(-1)^n = 1672$ .

From here it follows that $(n+1)\ |\ 1672$ . The biggest such $n$ that is smaller than $1000$ is $835$ , so $n \leq 835$ . $f(x) = \frac{-2\prod_{i = 1}^{835} (x - i)}{n!}$ is a solution, which proves that $n = 835$

Since $p(i) = i$ for every integer $i$ with $1 \leq i \leq n$ ,

roots of $p(x) - x = 0$ will be all integers between $1$ and $n$ .

$\therefore p(i) - x$ will take the form:

$C(x-1)(x-2)(x-3) \ldots (x-n)$ , where $C$ is a constant.

This leads to: $p(-1) - (-1) = C(-2)(-3)(-4) \ldots [-(n+1)]$

Since $p(-1) = 1671$ ,

$1672 = C (n+1)!$ when $n$ is even, $1672 = -C (n+1)!$ when $n$ is odd.

Solving for $C$ ,

$C = \frac {1672}{(n+1)!}$ when $n$ is even, and $C = -\frac {1672}{(n+1)!}$ when $n$ is odd.

$p(0) = C(-1)(-2)(-3)\ldots(-n)$

Substituting $C$ into the equation, we get:

$p(0) = \frac {1672}{(n+1)!} \times n!$ when $n$ is even,

$p(0) = -\frac {1672}{(n+1)!} \times -(n!)$ when $n$ is odd.

For both cases, $p(0) = \frac {1672}{(n+1)!} \times n! = \frac {1672}{n+1}$

Since $p(0)$ is an integer, $n+1$ must be a factor of $1672$

The largest value of $n+1$ when $n \leq 1000$ is $836$ .

$\therefore n = 836-1 = 835$

Define the function q(i) as:

$q(i) = p(i) - i$

So, for all $i=1...n$ , $q(i) = 0$ . This means that $q(i)$ has roots for all $i$ , so we can more generally define it as:

$q(i) = A(i-1)...(i-n)$

Looking at the case where $i=-1$ :

$p(-1)-(-1)=q(-1)$

$q(-1)=1672=(-1)^n \cdot A \cdot (n+1)!$

$\rightarrow A=\frac {1672}{(-1)^n \cdot (n+1)!}$

But looking at $i=0$ :

$p(0)=q(0)=(-1)^n \cdot A \cdot n!$ is an integer

So we know that $\frac {1672 \cdot n!}{(n+1)!}$ is also an integer, so

$\frac {1672}{n+1}$ is also an integer

One acceptable solution to this would be 1672, but this, of course, is >1000. The next solution would thus be:

$n+1=836$

$n=835$

First, we try to construct the polynomial from the given conditions. As per condition (1), the polynomial will be of the form $p(x) = k(x-1)(x-2) \ldots (x-n) + x$ because value of polynomial at n points is given, which implies polynomial is completely known except for a constant.

From condition (2), we have $k (-2)(-3) \ldots (-1-n) - 1 = 1671$ . This can be re-written as $k (-1)^n (n+1)! = 1672$ .

From condition (3), we have $k (-1) (-2) \ldots (-n) + 0 = Integer, c$ . This can be re-written as $k (-1)^n n!= c$ .

By dividing the above two equations, we have $\frac{1672}{n+1} =c$ . The largest integer $n+1 \, (n \le 1000)$ which divides 1672 is 836. This implies $n = 836-1= 835$ .

Let q(x)=p(x)-x, so q(x) vanish for x=1, 2, …, n. That means that has the form q(x) =a (x-1) (x-2) (x-3) … (x-n). Since p(-1)=1671 we get 1672=a (-2) (-3) (-4) … (-n-1), so we have an even number of negative factors and a=1672/(n+1!). But p(0) is an integer and p(0)=q(0)=a n! . In other words (1672/(n+1!)) n! =1672/(n+1) is an integer, so n+1 divides 1672. Since the divisors of 1672 are: 1, 2, 4, 8, 11, 19, 22, 38, 44, 76, 88, 152, 209, 418, 836, 1672. We have that n<=1000, so the maximum value for n+1 is 836, so the maximum possible degree of p(x) is 835.

At first, I define a polynomial $r(x):= p(x)-x$ Of course $r(i) = 0 \quad \forall 1\leq i \leq n$ thus, for Ruffini's theorem, $\displaystyle r(x) = a_0 \prod_{i=1}^{n}(x-i) = p(x) -x$ with $a_0 \in \mathbb{Q}$ and so $\displaystyle p(x) = x+a_0 \prod_{i=1}^{n}(x-i)$ . Then $p(-1) = a_0 (-1)^n (n+1)! -1 = 1671$ $a_0(-1)^n (n+1)! = 1672$ and $p(0) = a_0 (-1)^n n!$ Thus $\displaystyle p(0) = \frac{1672}{n+1}$ Now, because $836$ is the gratest divisor of $1672$ we must have that $n+1 = 836$ and so $n= 835$

the first conditon says p(i)=i for 1<=i<=n,so the polynomial could be

p(x) = x + ((1-x)(2-x)(3-x)----------(i-x)--------(n-x)/c)

                              or

p(x) = x + ((x-1)(x-2)----------(x-i)-------(x-n)/c)

where c is a constant ( sign to be determined later)

because polynomial gets the value 'i' when we put x=i as the term containing (i-x) becomes zero

now by second condition,

p(-1) = -1 + ((1-(-1))(2-(-1))--------(n-(-1))/c) =1671 eqn (1)

so,by eqn (1)

1.2.3.4.-------n.(n+!)/c =1672

c = (n+1)!/1672 eqn (2)
thus for 1st polynomial c is a +ve constant ( as RHS is +ve )

where as for second polynomial it could be -ve or +ve acc. to ((-1)^n)c now from given 3rd condition

p(0) = 0 + ((1-0)(2-0)-------(n-0)/c) = m where m is an integer

m = n!/c

but c = (n+1)!/1672 from eqn (2)

thus, m = n!/((n+1)!/1672)

          m  =  n!.1672/(n+1)!

          m  =  1672/(n+1)

But m is an integer so (n+1) must be the divisor of 1672

also 1672 = 8.11.19

as the degree os polynomial is dependent on the value of n and will be max when n is max thus maximum value for (n+1) is 4.11.19 (biggest divisor of 1672 which is < 1000)

n+1 = 836

n = 835

thus largest possible degree of the polynomial with given conditions is 835

If $p(x)$ is a polynomial of degree $n$ satisfying all of the conditions, then the polynomial $q(x) = p(x) -x$ is a polynomial of degree $\le n$ and $q(x)$ has roots at every integer $i$ with $1 \le i \le n$ . Thus, $q(x) = c(x-1)(x-2) \cdots (x-n)$ for some constant $c$ . To find $c$ , note that since $p(-1) = 1671$ , we get $1671 = p(-1) = q(-1) + (-1) = c(-1)^n(n+1)! - 1,$ so $c = \frac{1672}{(-1)^n(n+1)!} .$ Now since $p(0)$ is an integer, the value $p(0) = q(0) = c(-1)^n n! = \frac{1672}{n+1}$ must be an integer. Hence, $n+1$ must be a divisor of 1672. Since $1672 = 2 \times 836$ , the largest possible value of $n+1 \leq 1001$ which is a divisor of 1672 is 836. Therefore, the degree we are looking for is $n =$ 835.

I actually found it rather simple for Level 5 From given P(x)=x+z(x-1)(x-2).................(x-n) where z is some constant Because p(x)-x has its roots 123........n For p(0) to be integer z×n! Must be an integer Also. P(-1)=-1+z×(n+1)!
When n is even which it should be for p(-1) to be positive Therefore z×(n+1)!=1672

Let z×n!=k where kis an integer Z=k/n!

So k(n+1)=1672 So for n<1000 n= 835. k=2

First take, $A(x)=p(x)-x$ .Further,for every integer $i$ satisfying $1 \leq i \leq n$ ,we see that $A(x)$ vanishes i.e. $A(x)=0$ which implies that $A(x) =k(x-1)(x-2)(x-3)…(x-n)$ .

Then we are given that $p(-1)=1671$ .Then, If both those the above conditions are satisfied,then putting $1$ in the above derived equation, $k(-2)(-3)...............(-1-n)-1=1672$ . $k(-1)^n (n+1)=1672$ .

But then comes the third condition,whereby putting $0$ in the equation, we see that $k(-1)(-2).................(-n)+0 \in \mathbb{Z}$ (let's say $c$ ).Then $k(-1)^n n!= c$ .

Note further that $(n+1)|1672$ .Checking out with its divisors of 1672 ,we see that,the maximum value satisfying the upper limit $n\leq 1000$ is $n \leq 835$ . So the maximum possible degree of $n$ is $835$ .Further, $A(x) = \frac{-2(x-1)(x-2)..............(x-835)}{n!}$ being a solution also verifies our assumptions.

Thus we conclude that $\fbox{ n=835 }$