Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4934. (February 2018)

B. 4934. For any positive integers \(\displaystyle n\) and \(\displaystyle k\), let \(\displaystyle f(n,k)\) denote the number of unit squares cut in two by a diagonal of an \(\displaystyle n\times k\) lattice rectangle. How many number pairs \(\displaystyle n\), \(\displaystyle k\) are there such that \(\displaystyle n\ge k\), and \(\displaystyle f(n,k)=2018\)?

(4 pont)

Deadline expired on March 12, 2018.


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

Megoldás. Először határozzuk meg, hogy az \(\displaystyle n\times k\)-as rácstéglalap átlója hány egységnégyzet belsején halad keresztül. Képzeljük úgy, hogy a rácstéglalap csúcsai \(\displaystyle (0,0),(k,0),(0,n),(k,n)\), és vegyük a \(\displaystyle (0,0)\) és \(\displaystyle (k,n)\) csúcsokat összekötő átlót. (Világos, hogy a másik átló ugyanannyi egységnégyzet belsején halad keresztül.) Legyen \(\displaystyle k\) és \(\displaystyle n\) legnagyobb közös osztója \(\displaystyle d\), és legyen \(\displaystyle k=dk',n=dn'\), ekkor \(\displaystyle k'\) és \(\displaystyle n'\) relatív prímek. Az átlón lévő egész koordinátájú rácspontok:

\(\displaystyle (0,0),(k',n'),(2k',2n'),\dots,(dk',dn').\)

Azon egységnégyzetek, amelyek belsején az átló áthalad, azon \(\displaystyle d\) darab \(\displaystyle n'\times k'\) méretű téglalapon belül helyezkednek el, melyek két szemköztes csúcsa \(\displaystyle (ik',in'),((i+1)k',(i+1)n')\) valamely \(\displaystyle 0\leq i<d\) mellett, és oldalai párhuzamosak a koordináta-tengelyekkel.

Azt kell tehát meghatároznunk, hogy egy \(\displaystyle n'\times k'\) méretű téglalap átlója hány egységnégyzet belsején halad keresztül, majd az eredményt \(\displaystyle d\)-vel kell szoroznunk.

A \(\displaystyle (0,0)\) és \(\displaystyle (k',n')\) pontokat összekötő szakasz (a végpontjain kívül) nem tartalmaz egész koordinátájú rácspontot, hiszen \(\displaystyle (k',n')=1\). Az átló csak úgy tud belépni (kilépni) valamely egységnégyzetbe (egységnégyzetből), hogy áthalad egy függőleges vagy vízszintes rácsegyenesen, és ez a két lehetőség egyszerre nem tud bekövetkezni (hiszen az átló nem halad át rácsponton). összesen \(\displaystyle k'-1\) függőleges és \(\displaystyle n'-1\) vízszintes egyenesen kell áthaladnia, így azon egységnégyzetek száma, amelyek belsején keresztülhalad \(\displaystyle k'+n'-1\). (Az átlót ez az \(\displaystyle n'+k'-2\) egyenes \(\displaystyle n'+k'-1\) szakaszra osztja, melyek mindegyike az átló valamelyik egységnégyzet belsejébe eső szakasza.)

így az \(\displaystyle n\times k\) méretű téglalap esetében az ilyen egységnégyzetek száma \(\displaystyle d(k'+n'-1)\).

A 2018 szám prímtényezős felbontása \(\displaystyle 2018=2\cdot 1009\), így \(\displaystyle d\) értéke \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle 1009\) vagy \(\displaystyle 2018\) lehet.

Ha \(\displaystyle d=1\), akkor az olyan \(\displaystyle n',k'\) párok számát keressük, ahol \(\displaystyle n',k'\) relatív prím pozitív egészek, \(\displaystyle n'\geq k'\) és \(\displaystyle n'+k'-1=2018\), azaz \(\displaystyle n'+k'=2019\). Világos, hogy \(\displaystyle n'\) és \(\displaystyle k'=2019-n'\) pontosan akkor relatív prím, ha \(\displaystyle (n',2019-n')=(n',2019)=1\). Vagyis azon 2019/2-nél nagyobb egészek számát keressük, amelyek relatív prímek 2019-hez. Ez az Euler-féle \(\displaystyle \varphi\)-függvény és 2019 prímtényezős felbontása segítségével a következőképpen határozható meg:

\(\displaystyle \varphi(2019)/2=\varphi(3\cdot 673)/2=(3-1)(673-1)/2=672,\)

hiszen minden \(\displaystyle a\) számra \(\displaystyle (a,2019)=(2019-a,2019)\), így a 2019-hez relatív prím nála kisebb pozitív egészeknek éppen a fele nagyobb 2019/2-nél.

Ha \(\displaystyle d=2\), akkor ehhez hasonlóan azon egymáshoz relatív prím \(\displaystyle n',k'\) számpárok számát keressük, melyekre \(\displaystyle n'\geq k'\) és \(\displaystyle n'+k'= 1010\). Ezek száma

\(\displaystyle \varphi(1010)/2=\varphi(2\cdot 5 \cdot 101)/2=(2-1)(5-1)(101-1)/2=200.\)

Ha \(\displaystyle d=1009\), akkor \(\displaystyle n'+k'=3\), és így egyetlen lehetőség van: \(\displaystyle n'=2,k'=1\).

Végül, ha \(\displaystyle d=2018\), akkor \(\displaystyle n'+k'=2\), így ismét egyetlen lehetőség van: \(\displaystyle n'=k'=1\).

Tehát \(\displaystyle f(n,k)=2018\) összesen \(\displaystyle 672+200+1+1=874\) számpárra teljesül.


Statistics:

96 students sent a solution.
4 points:Baski Bence, Beke Csongor, Csépányi István, Csiszár Zoltán, Deák Bence, Dobák Dániel, Döbröntei Dávid Bence, Fekete Richárd, Fleiner Zsigmond, Fraknói Ádám, Fülöp Anna Tácia, Füredi Erik Benjámin, Gáspár Attila, Geretovszky Anna, Győrffi Ádám György, Győrffy Ágoston, Győrffy Johanna, Hervay Bence, Jánosik Áron, Jánosik Máté, Kántor András Imre, Kerekes Anna, Kiss Gergely, Kocsis Anett, Kószó Máté József, Kovács 129 Tamás, Lorcan O'Connor, Mátravölgyi Bence, Miszler Levente, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Németh Ciprián, Pituk Gábor, Reimann Kristóf, Saár Patrik, Sárvári Tibor, Schrettner Jakab, Schweitzer Ádám, Sebestyén Pál Botond, Shuborno Das, Szabó 417 Dávid, Terjék András József, Tóth 827 Balázs, Tóth-Rohonyi Iván, Vári-Kakas Andor, Weisz Máté, Zsigri Bálint.
3 points:21 students.
2 points:20 students.
1 point:7 students.

Problems in Mathematics of KöMaL, February 2018