До­ка­жем сна­ча­ла, что общее число кле­ток, через ко­то­рые про­хо­дит диа­го­наль, равно В самом деле, пря­мо­уголь­ник со­дер­жит m го­ри­зон­таль­ных линий сетки и n вер­ти­каль­ных. Пря­мая пе­ре­се­ка­ет их все и каж­дый от­ре­зок между со­сед­ни­ми ли­ни­я­ми лежит в одной клет­ке. Оста­лось толь­ко узнать, сколь­ко раз она пе­ре­се­ка­ет сразу две линии, то есть про­хо­дит через узел ре­шет­ки.

Пусть пер­вый узел, через ко­то­рый она про­хо­дит, имеет ко­ор­ди­на­ты тогда все осталь­ные узлы имеют ко­ор­ди­на­ты вида (по­сколь­ку у пря­мой, про­хо­дя­щей через на­ча­ло ко­ор­ди­нат, от­но­ше­ние ко­ор­ди­нат по­сто­ян­но). Ясно, что x, y  — вза­им­но про­стые числа, так как если она де­лят­ся на d, то точка тоже лежит на диа­го­на­ли. Тогда k обя­за­но быть целым  — иначе его зна­ме­на­тель не смо­жет це­ли­ком со­кра­тить­ся и с x и с y и точка не будет целой. Итак, она про­хо­дит в точ­но­сти через узлы вида Зна­чит, при­чем x, y  — вза­им­но про­сты. Это и озна­ча­ет, что

Итак, общее число пе­ре­се­че­ний с ли­ни­я­ми со­ста­вит (мы вы­чи­та­ем те, ко­то­рые были по­счи­та­ны два раза и не учи­ты­ва­ем на­чаль­ную вер­ши­ну пря­мо­уголь­ни­ка, но учи­ты­ва­ем ко­неч­ную). Зна­чит, имен­но столь­ко кле­ток и пе­ре­се­ка­ет наша пря­мая.

Пе­рей­дем те­перь к за­да­че.

а)  Число узлов равно

б)  Число ча­стей сов­па­да­ет с чис­лом кле­ток, по ко­то­рым про­хо­дит диа­го­наль. По­это­му ответ

в)  По усло­вию

Число 2020 рас­кла­ды­ва­ет­ся на мно­жи­те­ли та­ки­ми спо­со­ба­ми:

то есть m  =  2, n  =  2021;

то есть m  =  3, n  =  1011, не под­хо­дят, оба числа крат­ны 3;

то есть m  =  5, n  =  506;

то есть m  =  6, n  =  405, не под­хо­дят, оба числа крат­ны 3;

то есть m  =  11, n  =  203;

то есть m  =  21, n  =  102, не под­хо­дят, оба числа крат­ны 3.

Ответ: а) 5; б) 403; в) (2, 2021), (5, 506), (11, 203).