Maths Olympiad Prep

Library / /4 of 4

Number theory Difficulty 4.9 AIME Prove it Hong Kong

Let x\lfloor x \rfloor denote the greatest integer not exceeding xx. Find the last two digits of
13+23+223++222143 \left\lfloor \frac{1}{3} \right\rfloor + \left\lfloor \frac{2}{3} \right\rfloor + \left\lfloor \frac{2^2}{3} \right\rfloor + \cdots + \left\lfloor \frac{2^{2^{2^{14}}}}{3} \right\rfloor

Solution

Note that the remainder when 2n2^n is divided by 33 is 11 when nn is even, and 22 when nn is odd.
Hence [2n3]=2n13\left[\frac{2^n}{3}\right] = \frac{2^n-1}{3} when nn is even, and [2n3]=2n23\left[\frac{2^n}{3}\right] = \frac{2^n-2}{3} when nn is odd. It follows that
S=[13]+[23]+[223]++[220143]=0+(2323+22323)+(23323+24323)++(22013323+22014323)=(23+2231)+(233+2431)++(220133+2201431)=(23+223+233++220143)1007=22015231007 \begin{align*} S &= \left[\frac{1}{3}\right] + \left[\frac{2}{3}\right] + \left[\frac{2^2}{3}\right] + \dots + \left[\frac{2^{2014}}{3}\right] \\ &= 0 + \left(\frac{2}{3} - \frac{2}{3} + \frac{2^2}{3} - \frac{2}{3}\right) + \left(\frac{2^3}{3} - \frac{2}{3} + \frac{2^4}{3} - \frac{2}{3}\right) + \dots + \left(\frac{2^{2013}}{3} - \frac{2}{3} + \frac{2^{2014}}{3} - \frac{2}{3}\right) \\ &= \left(\frac{2}{3} + \frac{2^2}{3} - 1\right) + \left(\frac{2^3}{3} + \frac{2^4}{3} - 1\right) + \dots + \left(\frac{2^{2013}}{3} + \frac{2^{2014}}{3} - 1\right) \\ &= \left(\frac{2}{3} + \frac{2^2}{3} + \frac{2^3}{3} + \dots + \frac{2^{2014}}{3}\right) - 1007 \\ &= \frac{2^{2015} - 2}{3} - 1007 \end{align*}
The last two digits of powers of 22 are listed as follows:
02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04, 08, ...
The pattern repeats when the exponent is increased by 2020. So the last two digits of 220152^{2015} are the same as those of 2152^{15}, i.e. 6868.
Now write 220152=100k+662^{2015} - 2 = 100k + 66. Since 2201523\frac{2^{2015}-2}{3} is an integer, kk is a multiple of 33, and so we write k=3mk = 3m. Thus the last two digits of SS are the same as those of 100m+227100m + 22 - 7, i.e. 1515.

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.