LVIII OM - III - Zadanie 4

Zawody matematyczne:

LVIII OM, 2006-2007

Etap:

III

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

$ (1) \qquad n^2\le k\le m\le (n+1)^2. $

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

$ m+k=s,\quad\ m-k=r,\quad\ m'+k'=s',\quad\ m'-k'=r'. $

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

$ s^2-r^2=4q=4k'm'\le(k'+m')^2\le(s-1)^2=s^2-2s+1, \leqno(1) $

wobec czego

$ r^2+1\ge2s=2(k+m)=2(2k+r)=4k+2r $

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

$ (2) \qquad r\ge2n+1. $

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

$ k=n^2,\quad\ m=(n+1)^2,\quad\ k'=m'=n^2+n. $

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).

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

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.

\smallskip

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

$ k_1+m_1=k_2+m_2=s. $

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ść

$ 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. $

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

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

Bezpośrednio sprawdzamy, że

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

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

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

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

$ l^2-1<4l(n+1)\quad\hbox{dla }l\hbox{ nieparzystych,}\qquad l<4(n+1)\quad\hbox{dla }l\hbox{ parzystych}, $

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

$ 1+2+\ldots+(2n+1)+(2n+2)=(n+1)(2n+3)=2n^2+5n+3. $

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