Trójkąty w kwadracie
- mol_ksiazkowy
- Użytkownik
- Posty: 11371
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Trójkąty w kwadracie
Ile różnych trójkątów rozwartokątnych można utworzyć jeśli ich wierzchołki są punktami kratowymi, które znajdują się wewnątrz kwadratu o boku \(\displaystyle{ m}\) ?
- arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Re: Trójkąty w kwadracie
Jeżeli chodziłoby o trójkąty czy inne wielokąty gdzie krawędzie są równoległe do głównych linii układu współrzędnych to sprawa by była prosta.
Natomiast ten przypadek skłaniał mnie najpierw do tworzenia rekurencji, ale to paliło na panewce...
Pomysł znalazłem inny, mianowicie niech będzie dany taki dowolny trójkąt o wierzchołkach w punktach kratowych i teraz obrysujmy go minimalnym prostokątem, którego boki są równoległe do osi układu...
Będziemy mieli trzy główne przypadki, wartało by to rozrysować ale jakoś nie lubię, apeluję o odrobinę wyobraźni...
I. Przypadek pierwszy:
Podstawa trójkąta leży na całym boku prostokąta \(\displaystyle{ ABCD}\), gdzie \(\displaystyle{ A}\) to lewy dolny wierzchołek, a wierzchołki prostokąta idą przeciwnie do ruchu wskazówek zegara...
Czyli wierzchołki trójkąta to: \(\displaystyle{ ABX}\), gdzie \(\displaystyle{ X \in CD , X \neq C, D}\)
Oczywiście \(\displaystyle{ AB}\) będzie to najdłuższy bok trójkąta...
Czyli bok trójkąta naszego jest bokiem np. \(\displaystyle{ AB}\) prostokąta, pozostałe przypadki idą razy cztery bo cztery boki ma prostokąt...
II. Przypadek drugi:
\(\displaystyle{ AC}\) czyli przekątna prostokąta jest zarazem najdłuższym bokiem trójkąta, czyli nasz trójkąt:
\(\displaystyle{ ABX}\) gdzie \(\displaystyle{ X}\) jest dowolnym punktem należącym do kratowego prostokąta, oprócz ma się rozumieć przekątnej \(\displaystyle{ AB}\) oraz pozostałych wierzchołków \(\displaystyle{ C,D}\) prostokąta...
III. Przypadek trzeci (najtrudniejszy):
Pierwszym wierzchołkiem trójkąta jest punkt \(\displaystyle{ A}\), pozostałe wierzchołki: \(\displaystyle{ X \in CD , Y \in BC.}\)
Oczywiście pozostałe wierzchołki nie mogą leżeć w wierzchołkach prostokąta bo wtedy nasze trójkąty byłyby prostokątne a nie rozwartokątne...
Po tym dość dokładnym chyba opisie możemy zająć się poszczególnymi przypadkami:
ad. I.:
Przede wszystkim coś sobie ustalmy będę korzystał z tego, że trójkąt jest rozwartokątny jeżeli:
\(\displaystyle{ a^2-b^2-c^2>0}\) gdzie : \(\displaystyle{ a, b , c}\) to boki trójkąta a "a" bok najdłuższy...
Jest to wzięte z twierdzenia cosinusów niech jak ktoś nie wierzy niech sobie to sprawdzi, że tak jest...
Ustalmy jeszcze, że boki naszego minimalnego otaczającego trójkąt prostokąta mają długość:
\(\displaystyle{ AB=r , BC=s}\)
Wróćmy do pierwszego przypadku , łatwo zauważyć, że nasz trójkąt będzie rozwartokątny jeżeli:
\(\displaystyle{ s^2< \sqrt{x \left( r-x \right) }}\) gdzie: \(\displaystyle{ x=DX}\)
warunek na x:
\(\displaystyle{ 1 \le x \le r-1}\), oczywiście \(\displaystyle{ x}\) jest całkowite...
lub:
\(\displaystyle{ x^2-rx+s^2<0}\)
\(\displaystyle{ \Delta=r^2-4s^2 , r>2s}\)
z tego mamy warunek:
\(\displaystyle{ \frac{r- \sqrt{r^2-4s^2} }{2} <x<\frac{r+ \sqrt{r^2-4s^2} }{2}}\)
łatwo sprawdzić, że lewa strona jest zawsze większa od zera, i te wartości nie muszą choć mogą być całkowite, w związku z tym ilość interesujących ixów spełniających ten warunek to:
\(\displaystyle{ \left\lfloor \frac{r+ \sqrt{r^2-4s^2} }{2} \right\rfloor- \left\lceil \frac{r- \sqrt{r^2-4s^2} }{2} \right\rceil}\)
Przy warunku \(\displaystyle{ r>2s}\), jeżeli sprawę symetrycznie przeniesiemy na bok \(\displaystyle{ DC}\) on będzie podstawą to wystarczy pomnożyć przez dwa..., a jeżeli podstawą będzie bok \(\displaystyle{ AD}\) lub\(\displaystyle{ BC.}\)
To poprzez analogię otrzymamy:
\(\displaystyle{ s>2r}\) (warunek)
a nasza liczba to:
\(\displaystyle{ m_{1} \left( r,s \right) =\left\lfloor \frac{s+ \sqrt{s^2-4r^2} }{2} \right\rfloor- \left\lceil \frac{s- \sqrt{s^2-4r^2} }{2} \right\rceil}\)
A bok równoległy, przemnażamy przez dwa...
czyli przypadek pierwszy to:
\(\displaystyle{ u_{1} \left( r,s \right) =2\left( m_{1}+m_{2}\right)}\)
Gdzie: \(\displaystyle{ m_{2}}\) analogiczne zliczanie przy następnej parze boków równoległych, przy warunku:
\(\displaystyle{ r>2s}\)
Przypadek II:
\(\displaystyle{ AC}\) przekątna jest również najdłuższym bokiem trójkąta...
Wystarczy zliczyć wszystkie punkty prostokąta nieleżące na przekątnej i niebędące wierzchołkami...
Z obserwacji musimy wiedzieć ile jest punktów kratowych na odcinku o końcach też w punktach kratowych, a mianowicie ...
Łatwo zauważyć, że:
\(\displaystyle{ \left( r,s \right) =d}\) jest to największy wspólny dzielnik boków prostokąta...
Punktów kratowych wewnątrz odcinka (w naszym przypadku przekątnej) jest:
\(\displaystyle{ d-1}\).
Wszystkich punktów prostokąta \(\displaystyle{ ABCD}\) jest: \(\displaystyle{ \left( r+1 \right) \left( s+1 \right)}\)
Wyrzucamy teraz punkty wewnątrz przekątnej i punkty wierzchołkowe prostokąta i otrzymamy ilość takich trójkątów rozwartokątnych:
\(\displaystyle{ \left( r+1 \right) \left( s+1 \right) -d-4.}\)
Całość mnożymy przez dwa bo są dwie przekątne i otrzymamy:
\(\displaystyle{ u_{2} \left( r,s \right) =2\left[ \left( r+1 \right) \left( s+1 \right) -d-4 \right]}\)
Teraz trzeci przypadek:
\(\displaystyle{ Trójkąt.: AXY , X \in DC, Y \in BC}\)
\(\displaystyle{ a,b,c}\)- boki naszego trójkąta...
dane:
\(\displaystyle{ DX=x, XC=r-x,CY=s-y,YB=y,AB=r,BC=s}\)
Z Pitagorasa łatwo wyliczyć:
\(\displaystyle{ a^2=r^y^2 , b^2= \left( r-x \right) ^2+ \left( s-y \right) ^2 , c^2s^2+x^2}\)
I teraz będziemy mieć dwie możliwości:
Kąt, który może być kątem rozwartym w naszym trójkącie to kąt: \(\displaystyle{ X \vee Y}\), ale na pewno nie kąt przy wierzchołku \(\displaystyle{ A}\), bo \(\displaystyle{ A}\) może być maksymalnie prosty...
!. Przypadek gdzie najdłuższy jest bok: \(\displaystyle{ c}\)
Mamy więc warunek:
\(\displaystyle{ c^2-a^2-b^2>0.}\)
Po uproszczeniu i skróceniu mamy nierówność kwadratową:
\(\displaystyle{ y^2-sy+r^2-rx<0}\)
z tego:
\(\displaystyle{ x> \frac{y^2-sy}{r}+r}\), ale pamiętajmy, że:
\(\displaystyle{ 1 \le x \le r-1 , 1 \le y \le s-1.}\)
W związku z powyższymi musi zachodzić:
\(\displaystyle{ \frac{y^2-sy}{r}+r<r-1.}\)
Po uproszczeniu:
\(\displaystyle{ y^2-sy+r<0}\)
\(\displaystyle{ \Delta=s^2-4s>0.}\)
Rozwiązanie:
\(\displaystyle{ \frac{s- \sqrt{s^2-4r} }{2} <y<\frac{s+ \sqrt{s^2-4r} }{2}.}\)
Brzeg tej nierówności jest większy od zera (ale może być mniejszy od jeden) , a prawa strona może być większa od \(\displaystyle{ s}\).
Więc potrzebujemy warunków dodatkowych
Liczba przypadków nas interesujących będzie w przedziale:
\(\displaystyle{ x=\left\langle \max \left( 1,\left\lceil \frac{4r^2-s^2}{4r} \right) ;r-1 \right\rceil \right) \right\rangle}\)
Niech teraz liczba: \(\displaystyle{ l_{1} \left( r,s \right) =s-1-\max \left( 1,\left\lceil \frac{4r^2-s^2}{4r} \right) -1}\)
\(\displaystyle{ y=\left\langle \max \left( 1,\left\lceil \frac{s- \sqrt{s^2-4r} }{2} \right\rceil \right) ;\min \left( s-1,\left\lfloor \frac{s+ \sqrt{s^2-4r} }{2} \right\rfloor \right) \right\rangle}\)
\(\displaystyle{ l_{2} \left( r,s \right) =\min \left( s-1,\left\lfloor \frac{s+ \sqrt{s^2-4r} }{2} \right\rfloor \right) -\max \left( 1,\left\lceil \frac{s- \sqrt{s^2-4r} }{2} \right\rceil \right) -1}\)
Teraz łączna liczba trójkątów będzie:
\(\displaystyle{ l_{1} \left( r,s \right) \cdot l_{2} \left( r,s \right)}\) , przy warunku.:\(\displaystyle{ s>2 \sqrt{r}}\)
Analogicznie mamy drugi przypadek:
\(\displaystyle{ a^2-b^2-c^2}\) (najdłuższy bok a)
co przekłada się na warunek:
\(\displaystyle{ x^2-rx+s^2-sy<0}\)
lub:
\(\displaystyle{ y> \frac{x^2-rx}{s}+s}\)
\(\displaystyle{ \Delta=r^2-4s , r>2 \sqrt{s}}\)
rozwiązanie:
\(\displaystyle{ \frac{r- \sqrt{r^2-4s} }{2} <y<\frac{r+ \sqrt{r^2-4s} }{2}}\)
i analogicznie jak powyżej otrzymamy:
\(\displaystyle{ y=\left\langle \max \left( 1,\left\lceil \frac{4s^2-r^2}{4s} \right) ;s-1 \right\rceil \right) \right\rangle}\)
Niech teraz liczba: \(\displaystyle{ k_{1} \left( r,s \right) =r-1-\max \left( 1,\left\lceil \frac{4s^2-r^2}{4s} \right) -1}\)
\(\displaystyle{ x=\left\langle \max \left( 1,\left\lceil \frac{r- \sqrt{r^2-4s} }{2} \right\rceil \right) ;\min \left( r-1,\left\lfloor \frac{r+ \sqrt{r^2-4s} }{2} \right\rfloor \right) \right\rangle}\)
\(\displaystyle{ k_{2} \left( r,s \right) =\min \left( r-1,\left\lfloor \frac{r+ \sqrt{r^2-4s} }{2} \right\rfloor \right) -\max \left( 1,\left\lceil \frac{r- \sqrt{r^2-4s} }{2} \right\rceil \right) -1}\)
Teraz łączna liczba trójkątów będzie:
\(\displaystyle{ k_{1} \left( r,s \right) \cdot k_{2} \left( r,s \right)}\) , przy warunku \(\displaystyle{ r>2 \sqrt{s}.}\)
Biorąc pod uwagę, że w tym przypadku mamy cztery możliwości ponieważ wierzchołek naszego trójkąta może leżeć w czterech wierzchołkach prostokąta \(\displaystyle{ ABCD}\)
Mamy:
\(\displaystyle{ u_{3} \left( r,s \right) =4\left[ l_{1} \left( r,s \right) \cdot l_{2} \left( r,s \right) +k_{1} \left( r,s \right) \cdot k_{2} \left( r,s \right)\right]}\)
teraz wypada wszystkie możliwości zsumować, żeby sprawa zamknęła się w kwadracie o boku \(\displaystyle{ m}\)...
To znaczy wziąć wszystkie prostokąty \(\displaystyle{ (r,s)}\) równoległe do boków tegoż kwadratu.
Czyli zsumować:
\(\displaystyle{ \sum_{1 \le r , s \le m}^{}\left[ u_{1} \left( r,s \right) + u_{2} \left( r,s \right) + u_{3} \left( r,s \right) \right]}\)
Nie jest to piękny wzór ale biorąc pod uwagę przypadki, pod-przypadki i warianty tego zadania trudno chyba o jakiś fajerwerk...
Warto zliczyć ilość tych prostokątów o bokach: \(\displaystyle{ \left( r,s \right)}\) w kwadracie o boku \(\displaystyle{ m}\), lecz mi się już nie chce...
jakieś błędy się wkradły ale na razie nie mam czasu sprawdzać latexa...
Dzięki dobrym ludziom za poprawę , niestety nie mogłem tego dokonać bo wybrałem się na majówkę,
a jakbym poprawiał latex to bym się spóźnił...
Natomiast ten przypadek skłaniał mnie najpierw do tworzenia rekurencji, ale to paliło na panewce...
Pomysł znalazłem inny, mianowicie niech będzie dany taki dowolny trójkąt o wierzchołkach w punktach kratowych i teraz obrysujmy go minimalnym prostokątem, którego boki są równoległe do osi układu...
Będziemy mieli trzy główne przypadki, wartało by to rozrysować ale jakoś nie lubię, apeluję o odrobinę wyobraźni...
I. Przypadek pierwszy:
Podstawa trójkąta leży na całym boku prostokąta \(\displaystyle{ ABCD}\), gdzie \(\displaystyle{ A}\) to lewy dolny wierzchołek, a wierzchołki prostokąta idą przeciwnie do ruchu wskazówek zegara...
Czyli wierzchołki trójkąta to: \(\displaystyle{ ABX}\), gdzie \(\displaystyle{ X \in CD , X \neq C, D}\)
Oczywiście \(\displaystyle{ AB}\) będzie to najdłuższy bok trójkąta...
Czyli bok trójkąta naszego jest bokiem np. \(\displaystyle{ AB}\) prostokąta, pozostałe przypadki idą razy cztery bo cztery boki ma prostokąt...
II. Przypadek drugi:
\(\displaystyle{ AC}\) czyli przekątna prostokąta jest zarazem najdłuższym bokiem trójkąta, czyli nasz trójkąt:
\(\displaystyle{ ABX}\) gdzie \(\displaystyle{ X}\) jest dowolnym punktem należącym do kratowego prostokąta, oprócz ma się rozumieć przekątnej \(\displaystyle{ AB}\) oraz pozostałych wierzchołków \(\displaystyle{ C,D}\) prostokąta...
III. Przypadek trzeci (najtrudniejszy):
Pierwszym wierzchołkiem trójkąta jest punkt \(\displaystyle{ A}\), pozostałe wierzchołki: \(\displaystyle{ X \in CD , Y \in BC.}\)
Oczywiście pozostałe wierzchołki nie mogą leżeć w wierzchołkach prostokąta bo wtedy nasze trójkąty byłyby prostokątne a nie rozwartokątne...
Po tym dość dokładnym chyba opisie możemy zająć się poszczególnymi przypadkami:
ad. I.:
Przede wszystkim coś sobie ustalmy będę korzystał z tego, że trójkąt jest rozwartokątny jeżeli:
\(\displaystyle{ a^2-b^2-c^2>0}\) gdzie : \(\displaystyle{ a, b , c}\) to boki trójkąta a "a" bok najdłuższy...
Jest to wzięte z twierdzenia cosinusów niech jak ktoś nie wierzy niech sobie to sprawdzi, że tak jest...
Ustalmy jeszcze, że boki naszego minimalnego otaczającego trójkąt prostokąta mają długość:
\(\displaystyle{ AB=r , BC=s}\)
Wróćmy do pierwszego przypadku , łatwo zauważyć, że nasz trójkąt będzie rozwartokątny jeżeli:
\(\displaystyle{ s^2< \sqrt{x \left( r-x \right) }}\) gdzie: \(\displaystyle{ x=DX}\)
warunek na x:
\(\displaystyle{ 1 \le x \le r-1}\), oczywiście \(\displaystyle{ x}\) jest całkowite...
lub:
\(\displaystyle{ x^2-rx+s^2<0}\)
\(\displaystyle{ \Delta=r^2-4s^2 , r>2s}\)
z tego mamy warunek:
\(\displaystyle{ \frac{r- \sqrt{r^2-4s^2} }{2} <x<\frac{r+ \sqrt{r^2-4s^2} }{2}}\)
łatwo sprawdzić, że lewa strona jest zawsze większa od zera, i te wartości nie muszą choć mogą być całkowite, w związku z tym ilość interesujących ixów spełniających ten warunek to:
\(\displaystyle{ \left\lfloor \frac{r+ \sqrt{r^2-4s^2} }{2} \right\rfloor- \left\lceil \frac{r- \sqrt{r^2-4s^2} }{2} \right\rceil}\)
Przy warunku \(\displaystyle{ r>2s}\), jeżeli sprawę symetrycznie przeniesiemy na bok \(\displaystyle{ DC}\) on będzie podstawą to wystarczy pomnożyć przez dwa..., a jeżeli podstawą będzie bok \(\displaystyle{ AD}\) lub\(\displaystyle{ BC.}\)
To poprzez analogię otrzymamy:
\(\displaystyle{ s>2r}\) (warunek)
a nasza liczba to:
\(\displaystyle{ m_{1} \left( r,s \right) =\left\lfloor \frac{s+ \sqrt{s^2-4r^2} }{2} \right\rfloor- \left\lceil \frac{s- \sqrt{s^2-4r^2} }{2} \right\rceil}\)
A bok równoległy, przemnażamy przez dwa...
czyli przypadek pierwszy to:
\(\displaystyle{ u_{1} \left( r,s \right) =2\left( m_{1}+m_{2}\right)}\)
Gdzie: \(\displaystyle{ m_{2}}\) analogiczne zliczanie przy następnej parze boków równoległych, przy warunku:
\(\displaystyle{ r>2s}\)
Przypadek II:
\(\displaystyle{ AC}\) przekątna jest również najdłuższym bokiem trójkąta...
Wystarczy zliczyć wszystkie punkty prostokąta nieleżące na przekątnej i niebędące wierzchołkami...
Z obserwacji musimy wiedzieć ile jest punktów kratowych na odcinku o końcach też w punktach kratowych, a mianowicie ...
Łatwo zauważyć, że:
\(\displaystyle{ \left( r,s \right) =d}\) jest to największy wspólny dzielnik boków prostokąta...
Punktów kratowych wewnątrz odcinka (w naszym przypadku przekątnej) jest:
\(\displaystyle{ d-1}\).
Wszystkich punktów prostokąta \(\displaystyle{ ABCD}\) jest: \(\displaystyle{ \left( r+1 \right) \left( s+1 \right)}\)
Wyrzucamy teraz punkty wewnątrz przekątnej i punkty wierzchołkowe prostokąta i otrzymamy ilość takich trójkątów rozwartokątnych:
\(\displaystyle{ \left( r+1 \right) \left( s+1 \right) -d-4.}\)
Całość mnożymy przez dwa bo są dwie przekątne i otrzymamy:
\(\displaystyle{ u_{2} \left( r,s \right) =2\left[ \left( r+1 \right) \left( s+1 \right) -d-4 \right]}\)
Teraz trzeci przypadek:
\(\displaystyle{ Trójkąt.: AXY , X \in DC, Y \in BC}\)
\(\displaystyle{ a,b,c}\)- boki naszego trójkąta...
dane:
\(\displaystyle{ DX=x, XC=r-x,CY=s-y,YB=y,AB=r,BC=s}\)
Z Pitagorasa łatwo wyliczyć:
\(\displaystyle{ a^2=r^y^2 , b^2= \left( r-x \right) ^2+ \left( s-y \right) ^2 , c^2s^2+x^2}\)
I teraz będziemy mieć dwie możliwości:
Kąt, który może być kątem rozwartym w naszym trójkącie to kąt: \(\displaystyle{ X \vee Y}\), ale na pewno nie kąt przy wierzchołku \(\displaystyle{ A}\), bo \(\displaystyle{ A}\) może być maksymalnie prosty...
!. Przypadek gdzie najdłuższy jest bok: \(\displaystyle{ c}\)
Mamy więc warunek:
\(\displaystyle{ c^2-a^2-b^2>0.}\)
Po uproszczeniu i skróceniu mamy nierówność kwadratową:
\(\displaystyle{ y^2-sy+r^2-rx<0}\)
z tego:
\(\displaystyle{ x> \frac{y^2-sy}{r}+r}\), ale pamiętajmy, że:
\(\displaystyle{ 1 \le x \le r-1 , 1 \le y \le s-1.}\)
W związku z powyższymi musi zachodzić:
\(\displaystyle{ \frac{y^2-sy}{r}+r<r-1.}\)
Po uproszczeniu:
\(\displaystyle{ y^2-sy+r<0}\)
\(\displaystyle{ \Delta=s^2-4s>0.}\)
Rozwiązanie:
\(\displaystyle{ \frac{s- \sqrt{s^2-4r} }{2} <y<\frac{s+ \sqrt{s^2-4r} }{2}.}\)
Brzeg tej nierówności jest większy od zera (ale może być mniejszy od jeden) , a prawa strona może być większa od \(\displaystyle{ s}\).
Więc potrzebujemy warunków dodatkowych
Liczba przypadków nas interesujących będzie w przedziale:
\(\displaystyle{ x=\left\langle \max \left( 1,\left\lceil \frac{4r^2-s^2}{4r} \right) ;r-1 \right\rceil \right) \right\rangle}\)
Niech teraz liczba: \(\displaystyle{ l_{1} \left( r,s \right) =s-1-\max \left( 1,\left\lceil \frac{4r^2-s^2}{4r} \right) -1}\)
\(\displaystyle{ y=\left\langle \max \left( 1,\left\lceil \frac{s- \sqrt{s^2-4r} }{2} \right\rceil \right) ;\min \left( s-1,\left\lfloor \frac{s+ \sqrt{s^2-4r} }{2} \right\rfloor \right) \right\rangle}\)
\(\displaystyle{ l_{2} \left( r,s \right) =\min \left( s-1,\left\lfloor \frac{s+ \sqrt{s^2-4r} }{2} \right\rfloor \right) -\max \left( 1,\left\lceil \frac{s- \sqrt{s^2-4r} }{2} \right\rceil \right) -1}\)
Teraz łączna liczba trójkątów będzie:
\(\displaystyle{ l_{1} \left( r,s \right) \cdot l_{2} \left( r,s \right)}\) , przy warunku.:\(\displaystyle{ s>2 \sqrt{r}}\)
Analogicznie mamy drugi przypadek:
\(\displaystyle{ a^2-b^2-c^2}\) (najdłuższy bok a)
co przekłada się na warunek:
\(\displaystyle{ x^2-rx+s^2-sy<0}\)
lub:
\(\displaystyle{ y> \frac{x^2-rx}{s}+s}\)
\(\displaystyle{ \Delta=r^2-4s , r>2 \sqrt{s}}\)
rozwiązanie:
\(\displaystyle{ \frac{r- \sqrt{r^2-4s} }{2} <y<\frac{r+ \sqrt{r^2-4s} }{2}}\)
i analogicznie jak powyżej otrzymamy:
\(\displaystyle{ y=\left\langle \max \left( 1,\left\lceil \frac{4s^2-r^2}{4s} \right) ;s-1 \right\rceil \right) \right\rangle}\)
Niech teraz liczba: \(\displaystyle{ k_{1} \left( r,s \right) =r-1-\max \left( 1,\left\lceil \frac{4s^2-r^2}{4s} \right) -1}\)
\(\displaystyle{ x=\left\langle \max \left( 1,\left\lceil \frac{r- \sqrt{r^2-4s} }{2} \right\rceil \right) ;\min \left( r-1,\left\lfloor \frac{r+ \sqrt{r^2-4s} }{2} \right\rfloor \right) \right\rangle}\)
\(\displaystyle{ k_{2} \left( r,s \right) =\min \left( r-1,\left\lfloor \frac{r+ \sqrt{r^2-4s} }{2} \right\rfloor \right) -\max \left( 1,\left\lceil \frac{r- \sqrt{r^2-4s} }{2} \right\rceil \right) -1}\)
Teraz łączna liczba trójkątów będzie:
\(\displaystyle{ k_{1} \left( r,s \right) \cdot k_{2} \left( r,s \right)}\) , przy warunku \(\displaystyle{ r>2 \sqrt{s}.}\)
Biorąc pod uwagę, że w tym przypadku mamy cztery możliwości ponieważ wierzchołek naszego trójkąta może leżeć w czterech wierzchołkach prostokąta \(\displaystyle{ ABCD}\)
Mamy:
\(\displaystyle{ u_{3} \left( r,s \right) =4\left[ l_{1} \left( r,s \right) \cdot l_{2} \left( r,s \right) +k_{1} \left( r,s \right) \cdot k_{2} \left( r,s \right)\right]}\)
teraz wypada wszystkie możliwości zsumować, żeby sprawa zamknęła się w kwadracie o boku \(\displaystyle{ m}\)...
To znaczy wziąć wszystkie prostokąty \(\displaystyle{ (r,s)}\) równoległe do boków tegoż kwadratu.
Czyli zsumować:
\(\displaystyle{ \sum_{1 \le r , s \le m}^{}\left[ u_{1} \left( r,s \right) + u_{2} \left( r,s \right) + u_{3} \left( r,s \right) \right]}\)
Nie jest to piękny wzór ale biorąc pod uwagę przypadki, pod-przypadki i warianty tego zadania trudno chyba o jakiś fajerwerk...
Warto zliczyć ilość tych prostokątów o bokach: \(\displaystyle{ \left( r,s \right)}\) w kwadracie o boku \(\displaystyle{ m}\), lecz mi się już nie chce...
jakieś błędy się wkradły ale na razie nie mam czasu sprawdzać latexa...
Dzięki dobrym ludziom za poprawę , niestety nie mogłem tego dokonać bo wybrałem się na majówkę,
a jakbym poprawiał latex to bym się spóźnił...
Ostatnio zmieniony 26 maja 2019, o 12:32 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Pisz staranniej.
Powód: Poprawa wiadomości. Pisz staranniej.