Call a polynomial $f(x)$ excellent if its coefficients are all in [0, 1) and $f(x)$ is an integer for all integers $x$. a) Compute the number of excellent polynomials with degree at most 3. b) Compute the number of excellent polynomials with degree at most $n$, in terms of $n$. c) Find the minimum $n\ge3$ for which there exists an excellent polynomial of the form $\frac{1}{n!}x^n+g(x)$, where $g(x)$ is a polynomial of degree at most $n-3$.
Problem
Source:
Tags: Comc, algebra, polynomial
Mathloveguy12
16.12.2024 16:33
Did anyone manage to get an idea or hint to this problem? If yes, what was the initial hint? Could you share your idea with me?
Magnetoninja
17.12.2024 06:05
An attempt... Please let me know what to fix: Let $f(x)=a_3x^3+a_2x^2+a_1x+a_0$. $f(0)=a_0$ so $a_0 \in {\mathbb{Z}}$. Similarly, for integers $x$, $a_3x^3+a_2x^2+a_1x \in {\mathbb{Z}}$. Clearly, $a_1, a_2, a_3$ are rational. Let $a_s=\frac{p_s}{q_s}$ in simpliest form. Note that if $x\nmid{q_s}$ for all $s$, then the expression will not be an integer. Therefore $q_1=q_2=q_3$. Additionally, this implies $x\nmid{q}$, $p_3x^2+p_2x+p_1 \equiv 0\pmod{q}$. Now, we need $q\leq{3}$ since there are 3 variables of $p$, and to solve the system with all residues $x$ mod $q$, we can have at most $4$ scenarios. Before proceeding, I want to check what I have so far?
Mathloveguy12
19.12.2024 08:08
I like your idea to part A, I would highly use the hint below Try letting f(x)=ax^3+bx^2+cx Step1. find f(1) and f(-1), then add f(1) and f(-1) together to find all possible value of b. Step 2. Find f(1) minus f(-1) to find all possible value of a+c. I hope this helps.
MortemEtInteritum
19.12.2024 10:52
Mathloveguy12 wrote: Did anyone manage to get an idea or hint to this problem? If yes, what was the initial hint? Could you share your idea with me?
$f(x)$ is an integer for all $x$ if and only if $c_n{x\choose n}+c_{n-1}{x\choose n-1}+\dots+c_0{x\choose 0}$ where $c_i$ are integers
Pick the values $c_i$ above in the order $c_n, \dots, c_1$.
It's well known and can be proven by induction that a polynomial takes on integer values for integers $x$ iff it's of the form $c_n{x\choose n}+c_{n-1}{x\choose n-1}+\dots+c_0{x\choose 0}$ for integers $c_i$. That implies the answer to part $b$ is $n!\cdot (n-1)!\cdot\dots 1$, as there are $k!$ choices for $c_k$ if we choose for $k=n, n-1, \dots, 1$ in that order.
For part $c$, we need $c_n=1$. Note ${x\choose n}=x^n/n!-x^{n-1}(1+2+\dots+n)/n!$, so we need $c_{n-1}=(1+2+\dots+n)/n=(n+1)/2$, and if this is an integer then $n$ is odd. Then the coefficient of $x^{n-2}$ in ${x\choose n}+c_{n-1}{x\choose n-1}$ evalutes to $$\frac{n(n+1)(3n^2-n-2)/24+(n+1)(1+2+\dots+(n-1))/2}{n!}=\frac{(n+1)(3n+8)}{24(n-2)!}$$so $c_{n-2}=(n+1)(3n+8)/24$. If this is an integer then we can see $n\equiv 8, 23\pmod{24}$, so since it is odd the smallest $n$ is $\boxed{n=23}$.
Interesting problem, but I think a large part of the difficulty is determined by if you know about integer-valued polynomials or not.