Az A. 715. feladat (2018. január)

A. 715. Legyenek \(\displaystyle a\) és \(\displaystyle b\) pozitív egész számok. Egy \(\displaystyle a\times b\) méretű téglalapot olyan négyzetekkel fedünk le hézagmentesen és átfedések nélkül, melyek oldalhossza \(\displaystyle 2\)-hatvány, vagyis a lefedéshez \(\displaystyle 1\times 1\)-es, \(\displaystyle 2\times 2\)-es, \(\displaystyle 4\times 4\)-es, \(\displaystyle \ldots\) méretű négyzeteket használhatunk fel. Jelölje \(\displaystyle M\) azt, hogy egy ilyen fedéshez minimálisan hány négyzetet kell felhasználnunk. Az \(\displaystyle a\) és \(\displaystyle b\) számok egyértelműen felírhatók különböző kettőhatványok összegeként: \(\displaystyle a=2^{a_1}+\ldots+2^{a_k}\), \(\displaystyle b=2^{b_1}+\ldots +2^{b_\ell}\). Mutassuk meg, hogy

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

(5 pont)

A beküldési határidő 2018. február 12-én LEJÁRT.

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\).

Statisztika:

12 dolgozat érkezett.
5 pontot kapott:	Bukva Balázs, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Nagy Nándor, Schrettner Jakab.
3 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2018. januári matematika feladatai