Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4907. feladat (2017. november)

B. 4907. Bizonyítsuk be, hogy egy \(\displaystyle a\times b\) méretű téglalapon legfeljebb \(\displaystyle [a] \cdot [b]\) darab olyan \(\displaystyle 1\times 1\)-es négyzet helyezhető el átfedés nélkül, melyek oldalai párhuzamosak a téglalap oldalaival (ahol \(\displaystyle [x]\) az \(\displaystyle x\) szám egész részét jelenti).

(5 pont)

A beküldési határidő 2017. december 11-én LEJÁRT.


Megoldás. Először is megjegyezzük, hogy \(\displaystyle [a]\cdot [b]\) kisnégyzetet könnyen elhelyezhetünk a táblán: a téglalap bal alsó \(\displaystyle [a]\cdot [b]\) méretű részét - hívjuk ezt a téglalapot \(\displaystyle T\)-nek a továbbiakban - hézagmentesen lefedhetjük velük.

Megmutatjuk, hogy minden lefedés átrendezhető úgy, hogy a kisnégyzetek ezen a \(\displaystyle T\) téglalapon belül legyenek.

Szemléletesen azt csináljuk, hogy minden kisnégyzetet addig mozgatunk ,,lefelé'', amíg csak lehet (amíg a téglalap alsó oldalának, vagy egy másik kisnégyzet felső oldalának nem ,,ütközik''). Ha már egyik kisnégyzet sem mozgatható lefelé, akkor mindegyiket balra toljuk ,,ütközésig'', majd ha már egyik kisnégyzet sem mozgatható balra, megmutatjuk, hogy mindegyik kisnégyzet \(\displaystyle T\)-n belül lesz. Az egyetlen olyan lépés, ami komolyabb indoklásra szorul majd az lesz, hogy a tologatós rész miért ér mindenképpen véget véges sok lépésben. Most ezt a gondolatmenetet kidolgozzuk precízen.

Először válasszuk ki azokat a kisnégyzeteket, melyeknek van belső pontja a nagy téglalap alsó 1 széles sávjában. Ezek ,,alatt'', a téglalap (alsó) széléig már egyik kisnégyzetnek sem lehet belső pontja (hiszen akkor átfedés lenne köztük), így ezeket a kisnégyzeteket letolhatjuk a nagy téglalap alsó széléig. Ezután a lépés után az alsó 1 széles sáv felső határa egyik kisnégyzetet sem metszi belső pontban. Következő lépésben tekintsük azokat a kisnégyzeteket, melyeknek van belső pontja az alulról számított második 1 széles sávban. Ezek csak felfelé ,,lóghatnak ki'', és a korábbi gondolatmenetet megismételve letolhatók úgy, hogy teljesen a második sávon belül helyezkedjenek el. és így tovább, folytatjuk a harmadik, negyedik, majd végül az \(\displaystyle [a]\)-adik sávval. Ha mindegyikkel végeztünk, akkor már mindegyik kisnégyzet ezen \(\displaystyle [a]\) sáv valamelyikében helyezkedik el. Most tehát van \(\displaystyle [a]\) darab \(\displaystyle b\) hosszú 1 széles sávunk, mindegyikben néhány kisnégyzettel. Világos, hogy minden sávon belül legfeljebb \(\displaystyle [b]\) darab kisnégyzet van, sávon belül balra tologathatjuk a kisnégyzeteket úgy, hogy a sáv bal szélső \(\displaystyle 1\cdot [b]\) méretű részén legyenek. A tologatás végén minden kisnégyzet \(\displaystyle T\)-n belülre kell hogy essen, így mivel \(\displaystyle T\) területe \(\displaystyle [a]\cdot [b]\), következik, hogy legfeljebb ennyi lehet a kisnégyzetek száma is.


Statisztika:

117 dolgozat érkezett.
5 pontot kapott:Alexy Milán, Beke Csongor, Busa 423 Máté, Csányi Dávid, Csertán András, Csizmadia Viktória, Deák Bence, Dobák Dániel, Döbröntei Dávid Bence, Fraknói Ádám, Fuisz Gábor, Füredi Erik Benjámin, Gáspár Attila, Gyimesi Péter, Hervay Bence, Jánosik Máté, Janzer Orsolya Lili, Kántor András Imre, Kerekes Anna, Kiss Gergely, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Noszály Áron, Pituk Gábor, Saár Patrik, Schrettner Jakab, Sebestyén Pál Botond, Soós 314 Máté, Szabó 417 Dávid, Szemerédi Levente, Terjék András József, Tóth 827 Balázs, Vári-Kakas Andor, Weisz Máté, Zsigri Bálint.
4 pontot kapott:17 versenyző.
3 pontot kapott:18 versenyző.
2 pontot kapott:1 versenyző.
1 pontot kapott:15 versenyző.
0 pontot kapott:30 versenyző.

A KöMaL 2017. novemberi matematika feladatai