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