Maths Olympiad Prep

Library / Final Round of National Olympiad /6 of 27

Final Round of National Olympiad

Number theory Difficulty 5.1 AIME, harder Prove it Estonia

Let a>2a > 2 be an integer. Let
x=(a−1)⋅aa−2+(a−2)⋅aa−3+⋯+2⋅a1+1⋅a0,x = (a-1) \cdot a^{a-2} + (a-2) \cdot a^{a-3} + \dots + 2 \cdot a^1 + 1 \cdot a^0,
y=1⋅aa−2+2⋅aa−3+⋯+(a−2)⋅a1+(a−1)⋅a0.y = 1 \cdot a^{a-2} + 2 \cdot a^{a-3} + \dots + (a-2) \cdot a^1 + (a-1) \cdot a^0.

Prove that x−1x - 1 is divisible by y+1y + 1.

Solution

Note that x+y=a⋅aa−2+a⋅aa−3+⋯+a⋅a1+a⋅a0=aa−1+aa−2+⋯+a1x + y = a \cdot a^{a-2} + a \cdot a^{a-3} + \dots + a \cdot a^1 + a \cdot a^0 = a^{a-1} + a^{a-2} + \dots + a^1.
Hence
x+2y=aa−1+2⋅aa−2+3⋅aa−3+⋯+(a−1)⋅a1+(a−1)⋅a0=a(1⋅aa−2+2⋅aa−3+⋯+(a−1)⋅a0)+(a−1)=ay+(a−1). x + 2y = a^{a-1} + 2 \cdot a^{a-2} + 3 \cdot a^{a-3} + \dots + (a-1) \cdot a^1 + (a-1) \cdot a^0 \\ = a(1 \cdot a^{a-2} + 2 \cdot a^{a-3} + \dots + (a-1) \cdot a^0) + (a-1) \\ = ay + (a-1).
As x+2y=ay+(a−1)x + 2y = ay + (a-1) is equivalent to x−1=(a−2)(y+1)x - 1 = (a-2)(y+1), the claim follows.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.