Kvant Math Problem 352
Write
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m05s
Source on kvant.digital
Problem
Let $n$ be an integer for which $$n\lt(45+\sqrt{1975})^{30}\lt n+1.$$. Prove that $n$ is odd.
D. K. Faddeev
Exploration
Write
$$\alpha=45+\sqrt{1975}=45+5\sqrt{79},\qquad \beta=45-5\sqrt{79}.$$
Then
$$\alpha+\beta=90,\qquad \alpha\beta=45^2-1975=50.$$
The number $\beta$ is positive and
$$0<\beta=45-\sqrt{1975}<1,$$
because $44^2=1936<1975<2025=45^2$.
Since $\alpha$ and $\beta$ are roots of
$$x^2-90x+50=0,$$
the sequence
$$u_k=\alpha^k+\beta^k$$
satisfies the recurrence
$$u_{k+2}=90u_{k+1}-50u_k,$$
with $u_0=2$ and $u_1=90$. Hence every $u_k$ is an integer.
The quantity we seek is
$$n=\lfloor \alpha^{30}\rfloor.$$
Because $0<\beta<1$, we have $0<\beta^{30}<1$. Since
$$u_{30}=\alpha^{30}+\beta^{30}$$
is an integer and $\alpha^{30}$ is not an integer, it follows that
$$n=u_{30}-1.$$
Thus the parity of $n$ is opposite to the parity of $u_{30}$. It remains to determine $u_{30}\pmod 2$. Reducing the recurrence modulo $2$,
$$u_{k+2}\equiv 0\cdot u_{k+1}-0\cdot u_k\equiv 0 \pmod 2.$$
From $u_0=2$ and $u_1=90$, both even, every $u_k$ with $k\ge 0$ is even. Hence $u_{30}$ is even and $n=u_{30}-1$ is odd.
The only delicate point is justifying $n=u_{30}-1$; this uses $0<\beta^{30}<1$.
Problem Understanding
We are given the unique integer $n$ satisfying
$$n<(45+\sqrt{1975})^{30}<n+1.$$
Thus $n$ is the integer part of $(45+\sqrt{1975})^{30}$. We must prove that $n$ is odd.
This is a Type B problem, a pure proof.
The core difficulty is to connect the irrational quantity $(45+\sqrt{1975})^{30}$ with an integer sequence whose parity can be controlled. The conjugate number $45-\sqrt{1975}$ is positive and less than $1$, which suggests adding the two conjugate powers and using the resulting recurrence.
Proof Architecture
Let
$$\alpha=45+\sqrt{1975},\qquad \beta=45-\sqrt{1975}.$$
First claim: $0<\beta<1$. This follows from $44<\sqrt{1975}<45$.
Second claim: $u_k=\alpha^k+\beta^k$ is an integer for every $k\ge0$. Since $\alpha,\beta$ are roots of $x^2-90x+50=0$, the sequence satisfies the recurrence $u_{k+2}=90u_{k+1}-50u_k$ with integer initial values.
Third claim: $u_{30}$ is even. Reducing the recurrence modulo $2$ shows that every term is even.
Fourth claim: $n=u_{30}-1$. Since $0<\beta^{30}<1$ and $u_{30}=\alpha^{30}+\beta^{30}$ is an integer, $\alpha^{30}$ lies strictly between $u_{30}-1$ and $u_{30}$.
The hardest step is the fourth claim, because it converts the floor of $\alpha^{30}$ into an explicit integer.
Solution
Let
$$\alpha=45+\sqrt{1975},\qquad \beta=45-\sqrt{1975}.$$
Since
$$44^2=1936<1975<2025=45^2,$$
we have
$$44<\sqrt{1975}<45.$$
Hence
$$0<\beta=45-\sqrt{1975}<1.$$
The numbers $\alpha$ and $\beta$ are the roots of
$$x^2-90x+50=0,$$
because
$$\alpha+\beta=90,\qquad \alpha\beta=50.$$
Define
$$u_k=\alpha^k+\beta^k.$$
Since each of $\alpha$ and $\beta$ satisfies $x^2=90x-50$, we obtain
$$\alpha^{k+2}=90\alpha^{k+1}-50\alpha^k,$$
$$\beta^{k+2}=90\beta^{k+1}-50\beta^k.$$
Adding these equalities gives
$$u_{k+2}=90u_{k+1}-50u_k.$$
The initial values are
$$u_0=2,\qquad u_1=\alpha+\beta=90.$$
Since the recurrence has integer coefficients and integer initial values, every $u_k$ is an integer.
Now reduce the recurrence modulo $2$:
$$u_{k+2}\equiv 90u_{k+1}-50u_k\equiv 0 \pmod 2.$$
Because
$$u_0=2\equiv0\pmod2,\qquad u_1=90\equiv0\pmod2,$$
it follows that every $u_k$ is even. In particular,
$$u_{30}$$
is even.
Next,
$$u_{30}=\alpha^{30}+\beta^{30}.$$
Since $0<\beta<1$,
$$0<\beta^{30}<1.$$
Therefore
$$u_{30}-1<\alpha^{30}<u_{30}.$$
Because $u_{30}$ is an integer, the integer part of $\alpha^{30}$ equals
$$u_{30}-1.$$
The problem states that
$$n<\alpha^{30}<n+1,$$
so
$$n=\lfloor\alpha^{30}\rfloor=u_{30}-1.$$
Since $u_{30}$ is even, $u_{30}-1$ is odd. Hence $n$ is odd.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is proving $0<\beta<1$. From
$$1936=44^2<1975<45^2=2025,$$
we obtain
$$44<\sqrt{1975}<45.$$
Subtracting from $45$ yields
$$0<45-\sqrt{1975}<1.$$
The positivity is essential. If $\beta$ were negative, the sign of $\beta^{30}$ would require separate analysis.
The second delicate step is identifying the floor. Since $u_{30}$ is an integer and
$$u_{30}=\alpha^{30}+\beta^{30},$$
with
$$0<\beta^{30}<1,$$
we have
$$u_{30}-1<\alpha^{30}<u_{30}.$$
This places $\alpha^{30}$ in a unit interval whose endpoints are consecutive integers. Hence its integer part is exactly $u_{30}-1$. Replacing $0<\beta^{30}<1$ by the weaker statement $|\beta^{30}|<1$ would not suffice without checking the sign.
The third delicate step is the parity argument. The recurrence
$$u_{k+2}=90u_{k+1}-50u_k$$
becomes
$$u_{k+2}\equiv0\pmod2.$$
Thus every term from index $2$ onward is even regardless of previous values. Together with the even initial values $u_0=2$ and $u_1=90$, this confirms that all terms are even, especially $u_{30}$.
Alternative Approaches
Instead of using the recurrence explicitly, one may expand
$$(45+\sqrt{1975})^{30}+(45-\sqrt{1975})^{30}$$
by the binomial theorem. All irrational terms cancel, leaving an integer. Every surviving term contains a factor $2$, so the resulting integer is even. Since $0<45-\sqrt{1975}<1$, the floor of $(45+\sqrt{1975})^{30}$ is one less than this even integer, hence odd.
The recurrence method is preferable because it isolates the arithmetic structure immediately from the quadratic equation $x^2-90x+50=0$. The parity computation then reduces to a single congruence argument rather than a lengthy binomial expansion.