LVIII OM - III - Zadanie 4

Dana jest liczba całkowita $ n\ge 1 $. Wyznaczyć liczbę możliwych wartości iloczynu $ k\cdot m $, gdzie $ k $, $ m $ są liczbami całkowitymi
spełniającymi nierówności

\[<br />
(1) \qquad n^2\le k\le m\le (n+1)^2.<br />
\]

Rozwiązanie

Sposób I

Przypuśćmy, że dwie różne pary $ (k,m) $ i $ (k',m') $,
spełniające zadany warunek, dają jednakowy iloczyn $ {km=k'm'=q} $.
Oznaczmy

\[<br />
m+k=s,\quad\ m-k=r,\quad\ m'+k'=s',\quad\ m'-k'=r'.<br />
\]

Wówczas $ {4q=s^2-r^2} $, czyli $ {r=\sqrt{s^2-4q}} $; różnica $ r' $
wyraża się analogicznie. Gdyby zachodziła równość $ {s=s'} $,
wynikałaby stąd także równość $ {r=r'} $. To jednak nie jest
możliwe, skoro pary $ (k,m) $ i $ (k',m') $ są różne. Zatem
$ {s\ne{s'}} $; nie tracąc ogólności przyjmijmy, że $ {s'\le s-1} $.
Tak więc

\[<br />
s^2-r^2=4q=4k'm'\le(k'+m')^2\le(s-1)^2=s^2-2s+1,<br />
\leqno(1)<br />
\]

wobec czego

\[<br />
r^2+1\ge2s=2(k+m)=2(2k+r)=4k+2r<br />
\]

i w konsekwencji $ (r-1)^2\ge4k\ge4n^2. $ Widać stąd, że $ r $ nie może być zerem. Zatem $ {r-1} $ jest
liczbą nieujemną i z ostatniej nierówności wynika, że
$ {r-1\ge2n} $. To znaczy, że

\[<br />
(2) \qquad r\ge2n+1.<br />
\]

Różnica liczb $ \,m $, $ k $ z przedziału $ \langle n^2;(n+1)^2\rangle $
nie może być większa niż jego długość, równa $ {2n+1} $.
Nierówność (2) musi więc być równością, a liczby
$ k $, $ m\, $ muszą pokrywać się z końcami tego przedziału.

Muszą ponadto zachodzić równości we wszystkich wcześniejszych
nierównościach, z których zależność (2) została
wyprowadzona. Równość w związkach (1) oznacza zaś, że
$ {k'=m'=(s-1)\slash2} $. Ostatecznie więc

\[<br />
k=n^2,\quad\ m=(n+1)^2,\quad\ k'=m'=n^2+n.<br />
\]

Znalezione pary $ (k,m) $ i $ (k',m') $ istotnie mają równe iloczyny
$ {km=k'm'} $; a z przeprowadzonego rozumowania wynika, że są to
jedyne takie dwie różne pary.

W zbiorze $ \{n^2,n^2{+}1,\ldots,(n{+}1)^2\} $ jest $ {2n+2} $ liczb.
Można z nich utworzyć $ {2n+2\choose2} $ par $ (k,m) $, w których
$ {k<m} $, oraz $ {2n+2} $ par, w których $ {k=m} $; łącznie
$ {2n^2+5n+3} $ par. Wśród wyznaczonych przez nie wartości
iloczynu $ km $ występuje dokładnie jedno powtórzenie. Tak
więc liczba możliwych wartości iloczynu $ km $ jest o jeden
mniejsza i wynosi $ {2n^2+5n+2} $.

Sposób II

Uporządkujmy wszystkie pary $ (k,m) $ spełniające warunek (1) tak,
aby sumy $ k+m $ tworzyły ciąg niemalejący, zaś w każdym bloku
kolejnych par, w którym ta suma jest stała, niech wartości $ m $ tworzą
ciąg malejący (rys. 17).

om58_3r_img_17.jpg

Wypiszmy ciąg iloczynów $ k\cdot m $ odpowiadających parom $ (k,m) $
uporządkowanym w opisany sposób. Udowodnimy, że:

  1. W obrębie bloku, w którym suma $ k+m $ jest stała,
    ciąg iloczynów $ k\cdot m $ jest ściśle rosnący.
  2. \smallskip

  3. Dla dwóch kolejnych par $ (k_1,m_1) $ oraz $ (k_2,m_2) $
    spełniających warunek $ k_2+m_2=k_1+m_1+1 $ zachodzi nierówność
    $ k_1\cdot m_1<k_2\cdot m_2 $, z jednym wyjątkiem: Dla par
    $ (k_1,m_1)=(n^2+n,n^2+n) $ i $ (k_2,m_2)=(n^2,(n+1)^2) $
    iloczyny są równe.

Dowód zdania 1. Niech dla par $ (k_1,m_1) $, $ (k_2,m_2) $ będzie $ m_1>m_2 $ oraz

\[<br />
k_1+m_1=k_2+m_2=s.<br />
\]

Jest jasne, że $ m_1>m_2\ge{1\over 2}s\ge k_2>k_1 $. Funkcja kwadratowa
$ f(x)=x(s-x) $ jest ściśle rosnąca na przedziale $ (-\infty;{1\over 2}s\rangle $.
Otrzymujemy stąd żądaną nierówność

\[<br />
k_1\cdot m_1=k_1(s-k_1)=f(k_1)<f(k_2)=k_2(s-k_2)=k_2\cdot m_2.<br />
\]

Dowód zdania 2. Przyjmijmy, że $ (k_2,m_2)=(n^2,n^2+l) $, gdzie
$ 1\le l\le 2n+1 $ (na rys. 17 jest to pole znajdujące się
na górnym brzegu kwadratu). Wówczas $ k_2\cdot m_2=n^4+ln^2 $. Ponadto
w zależności od parzystości liczby $ l $ mamy

\[<br />
\begin{split}(k_1,m_1) &=\Bigl(n^2+{l-1\over 2},n^2+{l-1\over 2}\Bigr),\quad<br />
\hbox{jeżeli }l\hbox { jest liczbą nieparzystą}, \\<br />
(k_1,m_1) &=\Bigl(n^2+{l\over 2},n^2+{l\over 2}-1\Bigr),\quad\quad\,<br />
\hbox{jeżeli }l\hbox{ jest liczbą parzystą}.<br />
\end{split}<br />
\]

Bezpośrednio sprawdzamy, że

\[<br />
\begin{split}<br />
k_1\cdot m_1=n^4+(l-1)n^2+{(l-1)^2\over 4}& \le n^4+ln^2\quad\hbox<br />
{dla }l=1,3,5,\ldots,2n-1,2n+1,  \\<br />
k_1\cdot m_1=n^4+(l-1)n^2+{l(l-2)\over 4}& <<br />
n^4+ln^2\quad\hbox{dla }l=2,4,6,\ldots,2n.<br />
\end{split}<br />
\]

Rzeczywiście, pierwsza z powyższych nierówności jest równoważna
nierówności $ (l-1)^2\le 4n^2 $, która zachodzi dla $ 1\le l\le 2n+1 $,
przy czym równość ma miejsce jedynie dla $ l=2n+1 $, natomiast druga
nierówność sprowadza się do $ l(l-2)<4n^2 $, co jest prawdą dla $ 2\le l\le 2n $.

Analogicznie rozważamy przypadek $ (k_2,m_2)=((n+1)^2,n^2+l) $
(pole na prawym brzegu kwadratu na rys. 17). Wtedy
$ k_2\cdot m_2=n^2(n+1)^2+l(n+1)^2 $ i

\[<br />
\begin{split}(k_1,m_1) &=\Bigl(n^2+n+{l+1\over 2},n^2+n+{l-1\over 2}\Bigr),\quad<br />
\hbox{jeżeli }l\hbox { jest liczbą nieparzystą}, \\<br />
(k_1,m_1) &=\Bigl(n^2+n+{l\over 2},n^2+n+{l\over 2}\Bigr),\quad\quad\quad\,\,\,\,\,\,<br />
\hbox{jeżeli }l\hbox{ jest liczbą parzystą}.<br />
\end{split}<br />
\]

Nierówność $ k_1\cdot m_1<k_2\cdot m_2 $ przekształcamy równoważnie do postaci

\[<br />
l^2-1<4l(n+1)\quad\hbox{dla }l\hbox{ nieparzystych,}\qquad<br />
l<4(n+1)\quad\hbox{dla }l\hbox{ parzystych},<br />
\]

co jest prawdą, gdyż $ 1\le l\le 2n+1 $. To kończy dowód zdania 2.

W oparciu o zdania 1 i 2 stwierdzamy, że liczba różnych wartości
iloczynu $ k\cdot m $ jest o jeden mniejsza od liczby par $ (k,m) $
spełniających warunek (1). Patrząc na rys. 17
widzimy, że ta ostatnia liczba jest równa sumie

\[<br />
1+2+\ldots+(2n+1)+(2n+2)=(n+1)(2n+3)=2n^2+5n+3.<br />
\]

Zatem liczba możliwych wartości iloczynu $ k\cdot m $ wynosi $ {\bf 2n^2+5n+2} $.