elementary number theory - Tiling rectangle with squares using Euclid's algorithm

Is there a proof that tiling an n*m rectangle with squares using Euclid's algorithm (that is always choose the biggest square that fits in the remaining space) results in a minimum sum of the sizes (length of one side) of the resulting squares?

Answer

Let's call "sum of the sizes (length of one side)" as SS. And we assume that $m < n$ as for a square all is clear.

1. It's not hard to prove that SS(m,n) of euclidean algo is $m + n - gcd(m,n)$


2. We are to prove that it's the minimum of SS(m,n). We'll succeed in it if we prove that the biggest size of tiles for optimum tiling is $m$.


3. If it's not true we can assign 4 distinctive squares for every corner correspondingly.


4. Let's now count the perimeter of the rectangle. We consider only those squares which are adjacent to the border:

$$2(m+n) = \sum_{agjacent}l_i + \sum_{corner}l_j,$$

last sum contains the sizes of 4 squares assigned to the corners. Ok, then we get:

$$2(m+n) \le \sum_{all~ squares}l_i + \sum_{corner}l_j \le \sum_{all ~squares}l_i + 2m, $$

as "corneric" squares are paired and every pair have total size $\le m$

$$\sum_{all~ squares}l_i \ge 2n \ge n+m-gcd(n.m).$$

The covering is not optimal. Contradiction.