liczba kwadratów w prostokącie

metalknight · Post autor: **metalknight** » 26 lut 2014, o 18:52

Prostokąt \(\displaystyle{ ABCD}\) o naturalnych bokach \(\displaystyle{ a,b}\) podzielono na \(\displaystyle{ ab}\) jednakowych kwadratów jednostkowych. Ile jest wszystkich takich kwadratów jednostkowych, których wnętrza przecina przekątna \(\displaystyle{ AC}\)?

bartek118 · Post autor: **bartek118** » 26 lut 2014, o 20:46

Na pewno jest ich przynajmniej \(\displaystyle{ \max\left\{ a, b\right\}}\). Z drugiej strony, liczba ta nie może przekraczać \(\displaystyle{ 2 \max\left\{ a, b\right\}}\). Nie wydaje mi się jednak, by istniał dokładny wzór na tę liczbę.

metalknight · Post autor: **metalknight** » 26 lut 2014, o 22:45

Mogą występować różne rzeczy oprócz dodawania, mnożenia, odejmowania, dzielenia, potęgowania, pierwiastkowania - podłoga, sufit itp. Chodzi o to żeby dla danych \(\displaystyle{ a,b}\) w miarę łatwo to policzyć.

Wie ktoś jak to zrobić?

norwimaj · Post autor: **norwimaj** » 27 lut 2014, o 16:24

Jeśli przekątna nie przechodzi przez żaden punkt kratowy wewnątrz prostokąta, to oczywiście przejdzie przez \(\displaystyle{ a+b-1}\) kwadratów jednostkowych, bo przetnie \(\displaystyle{ a-1}\) linii poziomych, będących granicami kwadratów, i \(\displaystyle{ b-1}\) linii pionowych. W przypadku ogólnym od \(\displaystyle{ a+b-1}\) trzeba jeszcze odjąć liczbę punktów kratowych wewnątrz przekątnej. Do tego przyda się \(\displaystyle{ \gcd}\).

metalknight · Post autor: **metalknight** » 27 lut 2014, o 17:12

Nie widzę związku między \(\displaystyle{ \gcd}\), a liczbą punktów kratowych. Mógłbyś coś więcej na ten temat napisać?

norwimaj · Post autor: **norwimaj** » 27 lut 2014, o 17:15

Zbyt szybko się poddajesz. Jak do jutra nie wymyślisz, to mogę więcej napisać.

metalknight · Post autor: **metalknight** » 27 lut 2014, o 19:08

\(\displaystyle{ a+b-\gcd(a,b)}\)?

norwimaj · Post autor: **norwimaj** » 27 lut 2014, o 19:11

Tak, to jest dobra odpowiedź.

metalknight · Post autor: **metalknight** » 27 lut 2014, o 19:13

To zaobserwowałem na kilku przykładach, ale nadal niestety nie wiem jak udowodnić, że liczba wszystkich punktów kratowych wewnątrz przekątnej wynosi \(\displaystyle{ \gcd(a,b)-1}\)

norwimaj · Post autor: **norwimaj** » 28 lut 2014, o 14:49

Punkty kratowe dzielą przekątną na równe odcinki. Powiedzmy, że jest tych odcinków \(\displaystyle{ n}\). Wtedy punkty kratowe na przekątnej mają współrzędne na przykład (bo to zależy od umieszczenia prostokąta w układzie odniesienia) \(\displaystyle{ \left(\frac{ka}n,\frac{kb}n\right)}\) dla \(\displaystyle{ k\in\{0,\ldots,n\}}\). Zatem \(\displaystyle{ n}\) jest wspólnym dzielnikiem \(\displaystyle{ a}\) i \(\displaystyle{ b}\), więc \(\displaystyle{ n\le\gcd(a,b)}\). Z drugiej strony, punkty \(\displaystyle{ \left(\frac{ka}{\gcd(a,b)},\frac{kb}{\gcd(a,b)}\right)}\) dla \(\displaystyle{ k\in\{0,\ldots,\gcd(a,b)\}}\) są kratowe i leżą na przekątnej, zatem odcinków jest co najmniej \(\displaystyle{ \gcd(a,b)}\), czyli \(\displaystyle{ n\ge\gcd(a,b)}\).