Methods of Proof 32917.We prove both parts by induction onn. For (a), the casen=1 is straightforward.
Assume now that we have found ann-digit numbermdivisible by 2nmade out of the
digits 2 and 3 only. Letm= 2 nkfor some integerk.Ifnis even, then
2 × 10 n+m= 2 n( 2 · 5 n+k)
is an(n+ 1 )-digit number written only with 2’s and 3’s, and divisible by 2n+^1 .Ifkis
odd, then
3 × 10 n+m= 2 n( 3 · 5 n+k)
has this property.
The idea of part (b) is the same. The base case is trivial,m=5. Now if we have
found ann-digit numberm= 5 nkwith this property, then looking modulo 5, one of the
(n+ 1 )-digit numbers
5 × 10 n+m= 5 n( 5 · 2 n+k),
6 × 10 n+m= 5 n( 6 · 2 n+k),
7 × 10 n+m= 5 n( 7 · 2 n+k),
8 × 10 n+m= 5 n( 8 · 2 n+k),
9 × 10 n+m= 5 n( 9 · 2 n+k)
has the required property, and the problem is solved.
(USA Mathematical Olympiad, 2003, proposed by T. Andreescu)
18.We proceed by induction onn. The base case is obvious; the decomposition consists
of just one piece. For the induction step, let us assume that the tiling is possible for
such a 2n× 2 nboard and consider a 2n+^1 × 2 n+^1 board. Start by placing a piece in the
middle of the board as shown in Figure 43. The remaining surface decomposes into four
2 n× 2 nboards with corner squares removed, each of which can be tiled by the induction
hypothesis. Hence we are done.
Figure 4319.The property is clearly true for a single number. Now assume that it is true whenever
we have such a sequence of lengthkand let us prove it for a sequence of lengthk+1:
x 1 ,x 2 ,...,xk+ 1. Call a cyclic shift with all partial sums positive “good.’’