Maths Olympiad Prep

Library / /266 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

8748 \cdot 74 Find the value of the smallest term in the following sequence:
a1=199319941995,an+1={12an, if an is even, an+7, if an is odd. a_{1}=1993^{1994^{1995}}, a_{n+1}=\left\{\begin{array}{ll} \frac{1}{2} a_{n}, & \text { if } a_{n} \text { is even, } \\ a_{n}+7, & \text { if } a_{n} \text { is odd. } \end{array}\right.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

[Solution] Clearly, all terms of the sequence are positive integers.
Since when nn is even,
an+1=12an<ana_{n+1}=\frac{1}{2} a_{n}<a_{n}

Therefore, the smallest term of the sequence must be odd.
Let the smallest term of the sequence be apa_{p}, then apa_{p} is odd, and
ap+1=ap+7ap+2=12ap+1=12(ap+7)\begin{array}{l} a_{p+1}=a_{p}+7 \\ a_{p+2}=\frac{1}{2} a_{p+1}=\frac{1}{2}\left(a_{p}+7\right) \end{array}

By the minimality of apa_{p}, we have
apap+2a_{p} \leqslant a_{p+2}

That is,
ap12(ap+7)ap7\begin{array}{l} a_{p} \leqslant \frac{1}{2}\left(a_{p}+7\right) \\ a_{p} \leqslant 7 \end{array}

Noting that apa_{p} is odd. Therefore, apa_{p} has only 4 possible values:
1,3,5,71,3,5,7

Since
19941(mod3)1994 \equiv-1(\bmod 3)

Therefore
19941995(1)1995=12(mod3)1994^{1995} \equiv(-1)^{1995}=-1 \equiv 2(\bmod 3)

That is, there exists a positive integer tt, such that
19941995=3t+21994^{1995}=3 t+2

Since 1994 is even, tt is even, let t=2st=2 s, we get
19941995=6s+21994^{1995}=6 s+2

Here ss is a positive integer.
Thus, we have
a1=199319941995=19936s+2=(19936)s199321s(2)2(mod7)4(mod7)\begin{aligned} a_{1} & =1993^{1994^{1995}}=1993^{6 s+2} \\ & =\left(1993^{6}\right)^{s} \cdot 1993^{2} \\ & \equiv 1^{s} \cdot(-2)^{2}(\bmod 7) \\ & \equiv 4(\bmod 7) \end{aligned}

From a14(mod7)a_{1} \equiv 4(\bmod 7), we know that the remainders of the terms of this sequence when divided by 7 can only be 4,2,14,2,1. Therefore, apa_{p} cannot be 3,5,73,5,7, the value of the smallest term of the sequence
ap=1a_{p}=1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.