Pierwiastkowy lejek. Rozwiązanie zagadki

https://xpil.eu/rkf8 📋

Zagadka z lejkiem liczbowym, do którego "wlewamy" pierwiastki z liczb naturalnych, okazała się dla Czytelników bardziej skomplikowana, niż można było przypuszczać.

Przypomnę, chodzi o to, że mamy następujący lejek liczbowy:

Cztery różne liczby naturalne A, B, C, D nie są kwadratami (a więc odpada 0, 1, 4, 9, 16 itd). Każda liczba poniżej górnego rzędu jest iloczynem swoich dwóch sąsiadów z góry. X jest liczbą naturalną. Celem zagadki było znalezienie takiej czwórki A, B, C, D, która da w wyniku możliwie najmniejsze X.

Algebraicznie mamy więc:

Drugi rząd: \(\sqrt{AB}, \sqrt{BC}, \sqrt{CD}\)

Trzeci rząd: \(\sqrt{ABBC}, \sqrt{BCCD} = B\sqrt{AC}, C\sqrt{BD}\)

Wreszcie na samym dole, w dzióbku lejka: \(BC\sqrt{ABCD}\)

Widać więc, że powinniśmy starać się minimalizować B oraz C (bo to są mnożniki przed pierwiastkiem, więc wpływają na wynik bardziej niż A czy D) oraz znaleźć takie A, B, C, D, żeby ich iloczyn był kwadratem. Najmniejsze B i C spełniające warunki zadania to 2 i 3, więc pewnie warto od nich zacząć...

Dalej mi się nie chciało kombinować i napisałem sobie prosty skrypt w Pythonie:

from itertools import permutations

maks = 100
najlepszy_wynik = maks**4
niekwadraty = [x for x in range(2, maks+1) if x**0.5 != int(x**0.5)]

for a, b, c, d in permutations(niekwadraty, 4):
    if int((a*b*c*d)**0.5) == (a*b*c*d)**0.5:
        wynik_lejka = int((a*b*c*d)**0.5 * b * c)
        if najlepszy_wynik > wynik_lejka:
            najlepszy_wynik = wynik_lejka
            szczegóły = (a, b, c, d)
print(najlepszy_wynik, szczegóły)

W wyniku dostałem:

(8, 2, 3, 12) 144

Czyli wychodzi na to, że najmniejsza wartość, jaką można uzyskać w dzióbku lejka, to 144, dla A, B, C, D równych odpowiednio 8, 2, 3, 12. Widać przy okazji, że B i C wyszły takie same jak przewidziałem na samym początku.

Ale to tylko symulacja, nie gwarancja. Może jednak istnieje lepsze rozwiązanie, dla większych A, B, C, D? Intuicyjnie widać, że większe A, B, C, D dadzą na wyjściu większe liczby, ale a nuż jakaś kombinacja okaże się kwadratem mniejszym od tego tutaj?

W sukurs przychodzi nam odrobina logicznego kombinowania. Skoro już mamy potencjalnego kandydata na zwycięzcę (144), możemy teraz spróbować ustalić górną granicę wartości zmiennej maks, powyżej której będziemy mieć gwarancję braku lepszego rozwiązania.

Wiemy, że B i C mają większy wpływ na wynik, niż A i D, ponieważ są w potędze półtora (a A i D tylko pół). Dlatego powinniśmy je minimalizować.

Skoro zatem przyjmiemy B i C = 2, 3, a jedną z A, D (dajmy na to, A - problem jest symetryczny) ustawimy na 5 (kolejna najmniejsza dozwolona wartość), spróbujmy teraz znaleźć takie D, którego wartość zagwarantuje, że wynik końcowy będzie większy niż 144.

Mamy zatem:

$$6 \sqrt{6AD} > 144$$

co po uproszczeniu daje:

$$ AD > 96 $$

Przyjmując A=5, mamy:

$$ 5D > 96 => D > 19.2 $$

A więc ustawiając wartość zmiennej maks na 20 mamy gwarancję, że wynik będzie nie mniejszy od 144, z czego wynika, że znaleziona czwórka (A, B, C, D) = (8, 2, 3, 12) jest optymalna globalnie, a nie tylko lokalnie.

A jak Wam poszło?

Najpierw odezwał się Cichy, który kombinował nawet nieźle, ale niestety zapomniało mu się, że jedynka jest kwadratem. Przesłał potem korektę, ale do całkiem innego błędu, więc nadal z jedynką. Nie zaliczam.

Potem był Rozie, który napisał skrypt całkiem podobny do mojego, tylko błędnie założył A < B < C < D - nie zaliczam.

Wreszcie przyszło pierwsze poprawne rozwiązanie od Rzasta, który niczego nie symulował, tylko wziął szarą komórkę, podłączył ją do drugiej i trzeciej, i wykoncypował poprawną odpowiedź na piechotę, bez żadnego kodu. Szacun 🙂

x=bc√y gdzie y=abcd. y musi być kwadratem liczby naturalnej, czyli musi być iloczynem par liczb np. 2*2*5*5. W tym przypadku jeżeli przyjmę za b i c najmniejsze niekwadratowe liczby - odpowiednio 2 i 3, to y=2*3*a*d, czyli a*d=2*3*z². Pasuje tu kolejna liczba naturalna z= 4, a że mnożenie jest przemienne i łączne to można zgrupować a=2*4, a d=3*4. Mniejsze "z" spowoduje, że któraś z liczb będzie kwadratem.

Rzast, 2023-02-27

Nie zawiódł też Waldek, który przesłał poprawną odpowiedź wraz z całkiem szczegółową analizą:

Po krótkiej refleksji mamy zadanie:
x=bc √abcd , gdzie a , b , c , d , x∈ℕ i a , b , c , d to cztery różne liczby bezkwadratowe.
Szukamy x=x_min
---=---
Pierwiastek √abcd musi być liczbą naturalną, stąd abcd=k² .
k=2^w₁ 3^w₂ 5^w₃ … , czyli k²=2^2w₁ 3^2w₂ 5^2w₃ … , czyli suma wykładników jest parzysta.
Szukamy minimum, więc może na początek:

Wariant 1: k²=2^2w₁
Przy tym założeniu a , b , c , d mogą przyjmować tylko takie minimalne wartości: 2¹ , 2³ , 2⁵ , 2⁷ (parzyste wykładniki odpadają, gdyż są kwadratami). Iloczyn powyższego to 2¹⁶=65636 , a pierwiastek 2⁸=256 . Dla b=2¹=2 oraz c=2³=8 otrzymamy x=2⋅8⋅256=4096 . Dużo…

Wariant 2: k²=2^2w₁ 3^2w₂
Przypadek optymalny, to w²=1 , czyli dwie trójki, najlepiej jedna z nich samodzielnie, a druga w iloczynie z dwójką, np: 2 , 3 , 2⋅3 , 2⋅2⋅2 . Niestety, tu mamy nieparzystą liczbę dwójek. Należy dodać jedną dwójkę tak, aby uniknąć kwadratu i powtórzenia: 2 , 3, 2⋅2⋅3, 2⋅2⋅2 , tzn: a=12 ,b=2 , c=3,d=8 (b i c muszą być najmniejsze), √abcd=√576=24, ostatecznie x_min=2⋅3⋅24=144 .

I to jest moja ostateczna odpowiedź. Chyba, że zmienię zdanie i napiszę program, który to sprawdzi…

Waldek, 2024-02-29

Jako ostatni odezwał się Krzysiek, który okazał się minimalistą i po prosu wysłał poprawną odpowiedź, bez żadnych objaśnień ani komentarzy.

https://xpil.eu/rkf8 📋