Dzielenie koła
Linia prosta dzieli płaszczyznę na dwie części; dwie proste (nierównoległe) dzielą płaszczyznę na cztery części. Dalej może być różnie, w zależności od tego, czy skrzyżowania będą przecięciami dwóch czy więcej linii. Załóżmy, że zawsze tylko dwóch i zastąpmy płaszczyznę kołem, a linie proste cięciwami. Jeśli ponadto dodamy warunek, że liczba skrzyżowań powinna być maksymalna, to równocześnie koło będzie zawsze podzielone na największą możliwą liczbę części. Jaką?
Jeżeli będziemy przestrzegać podanego wyżej założenia i warunku, to każda n-ta cięciwa przetnie (n – 1) cięciw, czyli pierwsza nie przetnie żadnej, a liczba skrzyżowań (s) dla n = 1 będzie równa zero. Druga przetnie jedną cięciwę, czyli s = 1; po poprowadzeniu trzeciej, która przetnie dwie cięciwy, s będzie równe 3. Ciąg s dla n = 0, 1, 2, 3,… wygląda zatem tak: 0, 0, 1, 3, 6, 10, 15, 21…
Praktycznie dorysowywanie kolejno cięciw tak, aby każda następna przecinała wszystkie już istniejące, może szybko okazać się bardzo trudne lub niemożliwe (krzyżować będą się ich przedłużenia poza okręgiem). Należałoby więc właściwie rozwiązywać po kolei odrębne zadania dla każdej liczby cięciw: „poprowadź n cięciw tak, aby liczba ich skrzyżowań była maksymalna”.
Teraz o częściach koła. Każda n -ta cięciwa dzieli na dwie części:
– (n – 2) obszary między kolejnymi cięciwami, które przecina,
– dwa obszary między pierwszą i ostatnią przecinaną cięciwą a okręgiem.
W sumie po poprowadzeniu n -tej cięciwy przybywa więc n obszarów (o), czyli ciąg o dla n = 0, 1, 2, 3,… zaczyna się tak: 1, 2, 4, 7, 11, 16, 22, 29,…
Zadanie domowe brzmi następująco: proszę wyprowadzić wzór na wyraz ogólny ciągu sn oraz wyraz ogólny ciągu on.
Podkreślam: „wyprowadzić” – a nie tylko „podać”, bo znaleźć je w sieci nietrudno – czyli pokazać lub krótko opisać sposób otrzymania wzoru, jeśli znamy kilka jego początkowych wyrazów. Sposób jest oczywiście taki sam w przypadku obu ciągów.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.
Komentarze
s(n)= s(n-1)+n-1; s(0)=0
dowodzimy indukcyjnie – sprawdzamy, ze dziala dla n=1, czyli s(1)=0
mamy dla k cięciw s(k)=s(k-1)+k-1 skrzyżowań
po dorysowaniu k+1 cięciwy przybywa nam skrzyżowań ze wszystkimi wcześniej narysowanymi (czyli k)
s(k+1) = s(k-1)+k-1+k=s(k)+k
———————————–
o(n)=o(n-1)+n; o(0)=1
i znów: o(1) =1+1=2 – zgadza się
dla k cięciw mamy o(k)=o(k-1)+k obszarów
po dorysowaniu k+1 cięciwy przecina ona k+1 obszarów na dwa – czyli tyle własnie przybywa
o(k+1)=o(k-1)+k+k+1=o(k)+k+1
I tu dopiero mam wątpliwości – czy cnw czy cbdo…
OK, ale to są wzory rekurencyjne, a chodzi o wzory na wyraz ogólny.
mp
1) Skrzyżowania:
s1=0
s2=0+1
s3=0+1+2=3
s4=0+1+2+3=6
s5=0+1+2+3+4=10
s6=0+1+2+3+4+5=15
s7=0+1+2+3+4+5+6=21
…
sn=0+1+2+3+4+5+6+7+…+(n-1)=(0+n-1)n/2=(n^2-n)/2
2) Obszary:
o0=1
o1=2
o2=4=2×2-0
o3=7=2×4-1
o4=11=2×7-3
o5=16=2×11-6
o6=22=2×16-10
o7=29=2×22-15
…
on+1=2xon-[0+1+2+3+4+…+(n-1)]=2xon-(n^2-n)/2
on+1-on=n+1
on+1-2xon=-(n^2-n)/2
on=n+1+(n^2-n)/2=(n^2+n+2)/2
pokrótce:
0+1+2+…+n=(0+1+2+…+n+0+1+2+…+n)/2=((0+n)+(1+(n-1))+(2+(n-2))+…+((n-1)+1)+(n+0)=(n+1)n/2
Więc zapewne:
s_n=n(n-1)/2
o_n=n(n+1)/2+1
Ale ja jako uczniak ogólniaka mogę mieć łatwiej niż inni…
Pozdrawiam
s(n)= n(n-1)/2 – przeliczamy osobno dla parzystych i nieparzystych dodajac n-1 + 1; n-2 + 2 – dostajemy n-1/2 (dla nieparzystego n) lub n-2/2 (dla parzystego n) par po n – i n/2 do dodania (wciaz dla parzystego n)
o(n)=1 + n(n+1)/2
podobnie – rozpisujac wzor rekurencyjny dochodzimy do sumy: n+ n-1 + n-2 + … + 2 + 1 + 1 (jako s(0)); dodajac parami n + 1; n-1 + 2 itd otrzymujemy podana powyzej sume