Cztery liczby, parami względnie pierwsze

[atimor]

Wyznacz takie cztery różne, parami względnie pierwsze liczby całkowite dodatnie, że suma dwóch dowolnych jest dzielnikiem lub wielokrotnością sumy dwóch pozostałych, a suma tych czterech liczb jest możliwie najmniejsza.

Podaj ilość rozwiązań.

[Artist]

5,7,11,409. Znalazłem metodą prób błędów algorytm.
Szukay trzech liczb, z których żadne dwie nie są dzielnikami ani wielokrotnościami trzeciej (np. 3,5,11)
I korzystamy z chińskiego tw. nt. reszt.
I tak liczba numer 4 musi być postaci 144k+121
np. 121; 265( ale te nie są względnie pierwsze z pozostałymi), 409 etc.
Trzeba tylko znależć układ trech liczb złożony z możliwie najmniejszych liczb, a dalej szukać czwartj.

EDIT: Poprawiono błędy stwierdzone przez BettyBoo. Dzięki.

[BettyBoo]

Niestety, 3+11 nie jest dzielnikiem (ani tym bardziej wielokrotnością) 5+61...

Pozdrawiam.

[bosa_Nike]

@Artist - Formalnie jedynka jest względnie pierwsza z każdą liczbą całkowitą, więc \(\displaystyle{ (1,5,7,11)}\) daje mniejszą sumę.
Postaram się wieczorem napisać rozwiązanie, o ile wcześniej się nie pojawi.

EDIT: Próbowałam ujarzmić to, co rano napisałam w zeszycie, ale tym razem chyba przehandlowałam zwięzłość za prostotę.

Po pierwsze jasne jest, że jeżeli liczba \(\displaystyle{ A}\) jest dzielnikiem liczby \(\displaystyle{ B}\), to liczba \(\displaystyle{ B}\) jest wielokrotnością \(\displaystyle{ A}\). Dalej więc będziemy rozpatrywać tylko takie ułamki \(\displaystyle{ \frac{A}{B}}\), że \(\displaystyle{ A\ge B}\), gdzie \(\displaystyle{ A,B}\) są sumami par liczb zgodnie z warunkami zadania. Oznaczmy te liczby \(\displaystyle{ a,b,c,d}\). Najpierw udowodnimy, że wszystkie one muszą być nieparzyste:

Ukryta treść:    

Załóżmy, że jest inaczej. Oczywiście tylko jedna z liczb może być parzysta, bo inaczej nie byłyby one parami względnie pierwsze. Niech to będzie \(\displaystyle{ a}\). Wobec tego \(\displaystyle{ b,c,d}\) są nieparzyste i bez straty ogólności \(\displaystyle{ b<c<d}\). Ponieważ sumy, w których występuje \(\displaystyle{ a}\) są nieparzyste, a liczba parzysta nie dzieli nieparzystej, więc w mianownikach muszą być sumy z \(\displaystyle{ a}\). Mamy więc:

\(\displaystyle{ a+b<c+d\\ a+d<b+c\\ a+c<b+d}\)

Ale \(\displaystyle{ b+c>a+d>a+c\ \Rightarrow\ b>a}\), więc mamy \(\displaystyle{ a<b<c<d}\). Porządkujemy wobec tego ułamki - największy to \(\displaystyle{ \frac{c+d}{a+b}}\), bo dzielimy największą sumę przez najmniejszą.

Dodatkowo, ponieważ \(\displaystyle{ \frac{b+d}{a+c}-\frac{b+c}{a+d}=\frac{(d-c)(a+b+c+d)}{(a+c)(a+d)}>0}\), to \(\displaystyle{ \frac{c+d}{a+b}>\frac{b+d}{a+c}>\frac{b+c}{a+d}}\).

Wobec tego mamy:

\(\displaystyle{ \begin{cases}\frac{b+c}{a+d}\ge 2\\ \frac{b+d}{a+c}\ge 3\\ \frac{c+d}{a+b}\ge 4\end{cases}\ \Rightarrow\ \begin{cases}b+c\ge 2a+2d\\ b+d\ge 3a+3c\\ c+d\ge 4a+4b\end{cases}}\)

To po zsumowaniu i uporządkowaniu daje \(\displaystyle{ 0\ge 9a+2b+c}\) - sprzeczność.

Wobec tego wszystkie szukane liczby muszą być nieparzyste. Bez straty ogólności zostawiamy poprzedni porządek tzn. \(\displaystyle{ a<b<c<d}\), stąd od razu jest \(\displaystyle{ a+b<c+d}\) oraz \(\displaystyle{ a+c<b+c<b+d\ \Rightarrow\ a+c<b+d}\).

Rozpatrujemy dwa przypadki:

1:    

\(\displaystyle{ a+d\le b+c}\) - nierówność jest nieostra!

Wtedy, identycznie jak w poprzedniej sytuacji \(\displaystyle{ \frac{c+d}{a+b}>\frac{b+d}{a+c}>\frac{b+c}{a+d}}\), ale mamy wówczas:

\(\displaystyle{ \begin{cases}\frac{b+c}{a+d}\ge 1\\ \frac{b+d}{a+c}\ge 2\\ \frac{c+d}{a+b}\ge 3\end{cases}\ \Rightarrow\ \begin{cases}b+c\ge a+d\\ b+d\ge 2a+2c\\ c+d\ge 3a+3b\end{cases}}\)

Po zsumowaniu i uporządkowaniu: \(\displaystyle{ d\ge 6a+b}\) oraz \(\displaystyle{ 1\le\frac{b+c}{a+d}\le\frac{b+c}{7a+b}\ \Rightarrow\ c\ge 7a}\), stąd \(\displaystyle{ 2\le\frac{b+d}{a+c}\le\frac{b+d}{8a}\ \Rightarrow\ b+d\ge 16a}\), ale \(\displaystyle{ b+d\ge b+6a+b}\). Po zsumowaniu dwóch ostatnich nierówności i uporządkowaniu mamy \(\displaystyle{ d\ge 11a}\). Dalej mamy \(\displaystyle{ 2(b+c)\ge 2(a+d)}\) oraz \(\displaystyle{ b+d\ge 2a+2c}\), co po zsumowaniu i uporządkowaniu daje \(\displaystyle{ 3b\ge 4a+d\ge 4a+11a\ \Rightarrow\ b\ge 5a}\).

Spójrzmy na sumę liczb: \(\displaystyle{ a+b+c+d\ge a+5a+7a+11a=24a}\) - oczywiście równość w tym oszacowaniu może zachodzić jedynie wtedy, gdy \(\displaystyle{ d=11a,\ c= 7a,\ b=5a}\) i \(\displaystyle{ a=1}\), bo inaczej liczby nie byłyby względnie pierwsze. To daje "działającą" czwórkę \(\displaystyle{ (a,b,c,d)=(1,5,7,11)}\) i dowód, że mniejszej sumy nie da się w tym przypadku osiągnąć.

2:    

\(\displaystyle{ a+d>b+c}\) - nierówność jest ostra!

Wtedy \(\displaystyle{ \frac{a+d}{b+c}<\frac{b+d}{a+c}<\frac{c+d}{a+b}}\), ale mamy wówczas:

\(\displaystyle{ \begin{cases}\frac{a+d}{b+c}\ge 2\\ \frac{b+d}{a+c}\ge 3\\ \frac{c+d}{a+b}\ge 4\end{cases}\ \Rightarrow\ \begin{cases}a+d\ge 2b+2c\\ b+d\ge 3a+3c\\ c+d\ge 4a+4b\end{cases}}\)

Po zsumowaniu i uporządkowaniu: \(\displaystyle{ 3d\ge 6a+5b+4c\ge 6\cdot 1+5\cdot 3+4\cdot 5=41>39\ \Rightarrow\ d>13\ \Rightarrow\ d\ge 15}\).
Przyjmijmy teraz jako podstawowe kryterium minimum sumy.
Weźmy \(\displaystyle{ d=15,\ a=1}\) - ale wtedy \(\displaystyle{ b,c}\) nie mogą być równe \(\displaystyle{ 3,5}\), a dla \(\displaystyle{ b=7,\ c=9}\) suma jest większa niż \(\displaystyle{ 24}\).
Dla \(\displaystyle{ d=17,\ a=1,\ b=3,\ c=5}\) mamy \(\displaystyle{ a+b+c+d=26>24}\) i dalej nie ma już co sprawdzać.

Tak więc, jeżeli nie popełniłam jakiegoś logicznego błędu (mógłby ktoś zerknąć?), to czwórka \(\displaystyle{ (1,5,7,11)}\) jest (z dokładnością do permutacji) jedynym minimalnym (w sensie sumy) rozwiązaniem.

[atimor]

Cudownie, dziękuję bardzo