Maths Olympiad Prep

Library / /10 of 18

Algebra Difficulty 6.4 National olympiad Prove it Argentina

Evaluate the sum
113+313+3213++310113. \left\lfloor \frac{1}{13} \right\rfloor + \left\lfloor \frac{3}{13} \right\rfloor + \left\lfloor \frac{3^2}{13} \right\rfloor + \dots + \left\lfloor \frac{3^{101}}{13} \right\rfloor.

Here [][\dots] denotes the integer part of a number.

Solution

Ignore the integer parts of three consecutive summands with numerators 33k3^{3k}, 33k+13^{3k+1}, 33k+23^{3k+2}. The sum of three such fractions is an integer; moreover it equals 33k3^{3k}:
33k13+33k+113+33k+213=3k(1+3+32)13=33kfor 0k33. \frac{3^{3k}}{13} + \frac{3^{3k+1}}{13} + \frac{3^{3k+2}}{13} = \frac{3^k(1+3+3^2)}{13} = 3^{3k} \quad \text{for } 0 \le k \le 33.

Let x0,x1,x2x_0, x_1, x_2 be the fractional parts of 33k13,33k+113,33k+213\frac{3^{3k}}{13}, \frac{3^{3k+1}}{13}, \frac{3^{3k+2}}{13}. The remainders of 33k,33k+1,33k+23^{3k}, 3^{3k+1}, 3^{3k+2} modulo 1313 are 1,3,91, 3, 9 since 331(mod13)3^3 \equiv 1 \pmod{13}. Hence x0=113,x1=313,x2=913x_0 = \frac{1}{13}, x_1 = \frac{3}{13}, x_2 = \frac{9}{13} and so
33k13+33k+113+33k+213=33k13+33k+113+33k+213+(x0+x1+x2)=33k13+33k+113+33k+213+1. \begin{aligned} \frac{3^{3k}}{13} + \frac{3^{3k+1}}{13} + \frac{3^{3k+2}}{13} &= \left\lfloor \frac{3^{3k}}{13} \right\rfloor + \left\lfloor \frac{3^{3k+1}}{13} \right\rfloor + \left\lfloor \frac{3^{3k+2}}{13} \right\rfloor + (x_0 + x_1 + x_2) \\ &= \left\lfloor \frac{3^{3k}}{13} \right\rfloor + \left\lfloor \frac{3^{3k+1}}{13} \right\rfloor + \left\lfloor \frac{3^{3k+2}}{13} \right\rfloor + 1. \end{aligned}
Therefore the given sum is equal to i=033(33k1)=273412634\sum_{i=0}^{33} (3^{3k} - 1) = \frac{27^{34}-1}{26} - 34.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.