но предполагам, че като си написала поредната програмка си забелязала тази зависимост. Това, разбира се, в рамките на шегата.
Трябва, разбира се, да се отбележи, че в нашият случай при взаимно прости p и q, p+q-1 e най-малкият брой. В общия случай на трансп. задача планът в някой момент може да се "изроди" и да съдържа по-малко от p+q-1 ненулеви.
Това може да стане, ако .....как да го формулирам....абе ако сборовете по няколко хоризонтала и верикала съвпаднат преди края. В нашият случай това няма как да стане. Ако p и q имат НОД>1, плана ще се изроди точно НОД-1 пъти (последното не е израждане), така че ще получим най-малък брой
p+q-1-(НОД-1). Или с други думи голямата таблица може да се раздели на НОД независими таблици с размери p/НОД и q/НОД. Тогава пак общият брой ненулеви става
НОД*(p/НОД+q/НОД-1)=p+q-НОД