Minimum związane z algorytmem Euklidesa

[nobuddy]

Wskazać wartość lub sposób wyznaczania minimalnej niezerowej wartości wyrażenia \(\displaystyle{ |ka+lc|+|kb+ld|}\) dla ustalonych \(\displaystyle{ a,b,c,d}\) oraz \(\displaystyle{ k,l}\) przyjmujących wartości całkowite. Rzuca w oczy się że jest to pewne uogólnienie rozszerzonego algorytmu Euklidesa który to minimalizuje sumę \(\displaystyle{ kx+ly}\) jako \(\displaystyle{ NWD(x,y)}\). Tutaj m.in. ta minimalna wartość będzie nie mniejsza od \(\displaystyle{ \max \left( \min \left( NWD \left( a,c \right) , NWD \left( b,d \right) \right) , NWD \left( a+b,c+d \right) \right)}\), ale to raczej nie jest rozwiązanie...

[torus]

Tutaj m.in. ta minimalna wartość będzie nie mniejsza od \(\displaystyle{ \max \left( \min \left( NWD \left( a,c \right) , NWD \left( b,d \right) \right) , NWD \left( a+b,c+d \right) \right)}\), ale to raczej nie jest rozwiązanie...

Dla \(\displaystyle{ a=2,c=3,b=2,d=5}\) oraz \(\displaystyle{ k=2,l=-1}\) mamy:

\(\displaystyle{ |ka+lc|+|kb+ld|=|2\cdot 2-1\cdot 3|+|2\cdot 2-1\cdot 5|=2}\)

ale \(\displaystyle{ NWD(a+b,c+d)=NWD(4,8)=4}\). Tak więc to oszacowanie nie jest prawdziwe.

[nobuddy]

Rzeczywiście, po prostu napisałem te ograniczenia na szybko, i tak nic by nie wniosły.

[Kartezjusz]

Nierówność trójkąta i użyj pogrupowania otrzymasz \(\displaystyle{ |k(a+b)+ l(c+d)|}\) Teraz zadziała algorytm euklidesa, który poda ograniczenie dolne

[nobuddy]

Właśnie nie zadziała, tak napisałem moje ograniczenie na początku, które jest źle, jak już torus wskazał. Chodzi o to że dostaniemy ograniczenie \(\displaystyle{ WYRAZENIE \ge OSZACOWANIE}\) i potem z Euklidesa że OSZACOWANIE jest niemniejsze niż \(\displaystyle{ NWD(a+b,c+d)}\) jeśli jest niezerowe, problem w tym że OSZACOWANIE może być zerowe, a WYRAZENIE niezerowe ale mniejsze od \(\displaystyle{ NWD(a+b,c+d)}\). Czyli ten sposób odpada.

[torus]

Co do oszacowania przez \(\displaystyle{ \min(NWD(a,c),NWD(b,d))}\), opiera się ono na tym, że szacujemy że \(\displaystyle{ |ka+lc|\geq NWD(a,c)}\) lub jest równe 0 i analogicznie \(\displaystyle{ |kb+ld|\geq NWD(b,d)}\) lub jest równe 0, przy czym przynajmniej jedna z tych liczb jest niezerowa. Przyjrzyjmy się temu dokładniej. Załóżmy, że rzeczywiście dla jednej pary liczb wychodzi nam 0, powiedzmy że dla \(\displaystyle{ a}\) i \(\displaystyle{ c}\). Mamy: \(\displaystyle{ ka+lc=0}\), a stąd \(\displaystyle{ k=-ct}\) i \(\displaystyle{ l=at}\) dla pewnej liczby całkowitej \(\displaystyle{ t}\). Stąd współczynniki \(\displaystyle{ k,l}\) dzielą się przez \(\displaystyle{ NWD(a,c)}\), w związku z czym \(\displaystyle{ |kb+ld|\geq NWD(a,c)\cdot NWD(b,d)}\). Nie musi nam to dawać dobrego oszacowania - na ogół oszacowanie przez \(\displaystyle{ NWD(a,c)+NWD(b,d)}\) będzie lepsze. Można za to wywnioskować, że minimalna wartość wyrażenia \(\displaystyle{ |ka+lc|+|kb+ld|}\) jest równa 1 wtedy i tylko wtedy, gdy \(\displaystyle{ \begin{vmatrix}a&b\\c&d\end{vmatrix}=\pm 1}\).

[nobuddy]

Mamy: \(\displaystyle{ ka+lc=0}\), a stąd \(\displaystyle{ k=-ct}\) i \(\displaystyle{ l=at}\) dla pewnej liczby całkowitej \(\displaystyle{ t}\).

Dla \(\displaystyle{ a=2}\), \(\displaystyle{ c=4}\), \(\displaystyle{ k=2}\), \(\displaystyle{ l=-1}\) nie zachodzi \(\displaystyle{ l=at}\)... tak czy inaczej to tylko dodatkowe oszacowania, a zadanie nie powinno być trudne. Jest to matematyczny zapis zadania ze starych Potyczek Algorytmicznych gdzie trzeba było własnie wyznaczać to minimum. Zadanie można znaleźć tutaj

niestety ten konkurs nie udostępnia wzorcówek do zadań, ale widać że sporo osób zrobiło je. Pewnie to jakaś sprytna modyfikacja rozszerzonego algorytmu Euklidesa...

[nobuddy]

Ponawiam prośbę o pomoc, nie doszedłem wciąż do niczego konstruktywnego w tym zadaniu...