Problem A. 715. (January 2018)

A. 715. Let \(\displaystyle a\) and \(\displaystyle b\) be positive integers. We tile a rectangle with dimensions \(\displaystyle a\) and \(\displaystyle b\) using squares whose side-length is a power of \(\displaystyle 2\), i.e. the tiling may include squares of dimensions \(\displaystyle 1\times 1\), \(\displaystyle 2\times 2\), \(\displaystyle 4\times 4\) etc. Denote by \(\displaystyle M\) the minimal number of squares in such a tiling. Numbers \(\displaystyle a\) and \(\displaystyle b\) can be uniquely represented as the sum of distinct powers of \(\displaystyle 2\): \(\displaystyle a=2^{a_1}+\cdots+2^{a_k}\), \(\displaystyle b=2^{b_1}+\cdots +2^{b_\ell}\). Show that

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

(5 pont)

Deadline expired on February 12, 2018.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először megmutatjuk, hogy \(\displaystyle M\) darab olyan négyzettel (amelynek oldalhossza \(\displaystyle 2\)-hatvány) le tudjuk fedni a téglalapot. Osszuk fel az \(\displaystyle a\) hosszúságú oldalt \(\displaystyle k\) részre, melyek hossza rendre \(\displaystyle 2^{a_1},2^{a_2},\dots,2^{a_k}\), és a \(\displaystyle b\) hosszúságú oldalt \(\displaystyle \ell\) részre, melyek hossza rendre \(\displaystyle 2^{b_1},2^{b_2},\dots,2^{b_\ell}\). Az így kapott osztópontokon keresztül párhuzamosokat húzva a téglalap oldalaival azt \(\displaystyle k\ell\) kisebb téglalapra osztjuk fel, melyek mérete \(\displaystyle 2^{a_i}\times 2^{b_j}\) (ahol \(\displaystyle 1\leq i\leq k, 1\leq j\leq \ell\)). Ha \(\displaystyle s\le t\), akkor egy \(\displaystyle 2^s\times 2^t\) méretű téglalap lefedhető \(\displaystyle 2^{t-s}\) darab \(\displaystyle 2^s\times 2^s\) méretű négyzettel. Tehát a \(\displaystyle 2^{a_i}\times 2^{b_j}\) méretű rész lefedhető \(\displaystyle 2^{|a_i-b_j|}\) darab \(\displaystyle 2\)-hatvány oldalhosszúságú négyzettel. Ily módon a teljes téglalap lefedéséhez felhasznált négyzetek száma éppen \(\displaystyle M\).

Most belátjuk, hogy \(\displaystyle M\)-nél kevesebb négyzettel a kért lefedés nem valósítható meg. Tekintsünk egy tetszőleges fedést, ennél a \(\displaystyle 2^i\times 2^i\) méretű négyzetek számát jelölje \(\displaystyle n_i\). Ha \(\displaystyle i>N=\max_{i,j}(a_i,b_j)\), akkor \(\displaystyle n_i=0\), vagyis \(\displaystyle 2^i\times 2^i\) méretű négyzetet egyáltalán nem használhatunk, hiszen akkor \(\displaystyle 2^i>\max(a,b)\), vagyis a négyzet oldalhossza nagyobb lenne a téglalap valamelyik oldalánál.

Legyen most \(\displaystyle 0\leq d\leq N\) tetszőleges. Tekintsük azokat a négyzeteket a lefedésben, melyek oldalhossza legalább \(\displaystyle 2^d\), és képzeletben bontsuk fel őket \(\displaystyle 2^d\times 2^d\) méretű négyzetekre. Egy \(\displaystyle 2^t\times 2^t\) méretű négyzetnél (ahol \(\displaystyle t\ge d\)) éppen \(\displaystyle 4^{t-d}\) darab \(\displaystyle 2^d\times 2^d\)-es négyzetet kapunk, így összesen

\(\displaystyle \sum_{t=d}^N 4^{t-d}n_t\)

darab \(\displaystyle 2^d\times 2^d\)-es négyzetet találtunk az \(\displaystyle a\times b\)-s téglalapban, melyek közül semely kettőnek nincs közös belső pontja. A B.4907. feladatot a téglalap \(\displaystyle \frac1{2^d}\)-szeres kicsinyítésére alkalmazva kapjuk, hogy legfeljebb \(\displaystyle \left[\frac{a}{2^d} \right]\cdot \left[\frac{b}{2^d} \right]\) darab \(\displaystyle 2^d\times 2^d\)-es négyzet helyezhető el átfedés nélkül, tehát minden \(\displaystyle 1\le d\le N\)-re

Ebben a becslésben pedig egyenlőség áll a fenti konstrukciónk esetén, ugyanis ott az \(\displaystyle a\times b\)-s téglalapnak egy \(\displaystyle 2^d\left[\frac{a}{2^d} \right]\times 2^d\left[\frac{b}{2^d} \right]\) méretű részét parkettáztuk legalább \(\displaystyle 2^d\) oldalhosszú négyzetekkel.

Felírjuk \(\displaystyle (*)\)-ot \(\displaystyle d=0,1,\dots,N\)-re, majd összeadjuk:

\(\displaystyle \begin{matrix} n_0+&4n_1+&4^2 n_2+&\dots+&4^N n_N & \le \left[\frac{a}{2^0} \right]\cdot \left[\frac{b}{2^0} \right] \\ &n_1+&4n_2+&\dots+&4^{N-1}n_N&\le \left[\frac{a}{2^1} \right]\cdot \left[\frac{b}{2^1} \right]\\ &&\vdots&& & \vdots \\ &&&&n_N&\le \left[\frac{a}{2^N} \right]\cdot \left[\frac{b}{2^N} \right] \end{matrix}\)

\(\displaystyle \implies \sum_{d=0}^N \frac{4^{d+1}-1}{3} n_d\le \dots,\)

ahol \(\displaystyle \dots\) olyan (\(\displaystyle a,b\) által meghatározott) konstans, melyre a becslésben a fenti konstrukcióra egyenlőség áll. Azonban a négyzetek összterületére pedig

\(\displaystyle \sum_{d=0}^N 4^d n_d=ab,\)

amit a becslésbe helyettesítve

\(\displaystyle \sum_{d=0}^N n_d\ge \dots\)

adódik, ahol \(\displaystyle \dots\) helyére olyan konstans írható, amely a fenti konstrukció esetén egyenlőséget ad. Mivel ez a konstans éppen \(\displaystyle M\), ezért ezzel bebizonyítottuk, hogy a felhasznált négyzetek számának minimális értéke \(\displaystyle M\).

Statistics:

12 students sent a solution.
5 points:	Bukva Balázs, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Nagy Nándor, Schrettner Jakab.
3 points:	3 students.
1 point:	1 student.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2018