MathDB

Let

a

and

b

be positive integers. We tile a rectangle with dimensions

a

and

b

using squares whose side-length is a power of

2

, i.e. the tiling may include squares of dimensions

1\times 1, 2\times 2, 4\times 4

etc. Denote by

M

the minimal number of squares in such a tiling. Numbers

a

and

b

can be uniquely represented as the sum of distinct powers of

2

a=2^{a_1}+\cdots+2^{a_k},\; b=2^{b_1}+\cdots +2^{b_\ell}.

Show that

M=\sum_{i=1}^k \;\sum_{j=1}^{\ell} 2^{|a_i-b_j|}.

A. 715