liczby
Pyra: Wyznacz wszystkie pary liczb naturalnych (a, b) takich ze 1 ≤a, b ≤ 2000 oraz (a2−ab−b2)2=1.
2 sie 12:08
MilEta:
1 1
2 1
3 2
5 3
8 5
13 8
21 13
34 21
55 34
89 55
144 89
233 144
377 233
610 377
987 610
1597 987
2 sie 12:20
MilEta: Kod w Python jakby co:
for i in range(1,2001):
for j in range(1,2001):
if (i**2−i*j−j**2)**2 == 1:
print(i,j)
2 sie 12:21
Pyra: To zadnie jest z Teorii liczb, a nie programowania.
2 sie 12:24
MilEta: To powodzonka!
Wiesz już czego szukać, i jak widać rozwiązań jest wiele. Gdyby np były 2
rozwiazania
to by było warto pomyśleć, tak można sie domyśleć że będzie sporo przypadków
2 sie 12:53
MilEta: Oczywiście warto zacząć od:
a2−ab−b2 = 1 lub a2 − ab − b2 = −1
2 sie 13:00
MilEta: a2 − ab − b2 = 1 to z tego już wynika że
a2 > ab + b2 (z tego też wynika że a2 > b2 a zatem a > b)
Niech a = b+k, k>0
(b+k)2−(b+k)b−b2 = 1
b2 + 2bk + k2 − b2 − bk − b2 = 1
bk + k2 − b2 =1 z tego wynika że k2 − b2 < 0 a zatem k2 < b2 więc k < b
Zatem już wiemy że warto sprawdzać tylko takie pary (a,b) gdzie a∊(b,2b)
Pobaw sie dalej
2 sie 13:11
MilEta: (oczywiscie prócz przypaku gdy b=k=1 i wtedy a =2)
Do tego a, b nie mogą być równocześnie parzyste. Dlaczego
Wrzuć swoje rozwiązanie to sprawdzimy
2 sie 13:15
2 sie 14:46
MilEta: rzeczwyiście, jak sie tak popatrzy to kolejne a i kolejne b to wyrazy ciagu fibonacciego
2 sie 15:09
MilEta: Czyli można udowodnić takie twierdzenie: Jeżeli a, b spełniają równość to a+b i a też
Z założenia (a2−ab−b2)2 = 1
Sprawdzamy teraz a+b i a
((a+b)2 − (a+b)a − a2)2 = (a2+2ab+b2 − a2 − ab − a2)2 = (b2+ab−a2)2 = (a2−ab−b2)2
i rzeczywiscie jest to równe 1 (z założenia)
Zatem tak, wyrazy ciągu Fibonnaciego spełniają to równanie (w taki rekurencyjny sposob).
czyli 1,1 i potem 2, 1 i potem 3, 2 itd
Pasowaloby pokazac jeszcze, ze to wszystkie (nie ma innych)
2 sie 15:24