Melyik  $n<10000$  -re van a legtöbb olyan  $k$  pozitív egész, hogy  $n$  -et  $ 2k+1$  -gyel osztva  $k$  lesz a maradék? Adjuk meg  $n$  értékét!

Végeredmény: 8662

 $n\equiv k\pmod{2k+1}$  akkor és csak akkor, ha  $ 2k+1|2n+1$  , tehát elég megmondani, hogy 20000-ig melyik  $m = 2n+1$  páratlan számnak van a legtöbb osztója (a  $k$  -k száma ennél 1-gyel kevesebb, mert  $ 2k+1 \neq 1$  .)

Tegyük fel, hogy  $d(m) = (l_1+1)\cdot (l_2+1)\cdot\ldots$  maximális, az ilyen  $m<20000$  számok között pedig  $m$  minimális. Ekkor  $l_1\geq l_2\geq \ldots l_s$  . Ha a  $ 13$  exponense,  $l_5 \ge 1$  , akkor  $ 2n+1 \ge 3\cdot 5\cdot (7\cdot 11 \cdot 13) = 15\cdot 1001 = 15015$  , tehát  $l_1 = \dots = l_5 = 1$  ,  $l_6 = 0$  , vagyis  $d(m) = 32$  . Tegyük fel, hogy  $l_4 = 0$  (a  $ 11$  sem szerepel). Ekkor:  $l_2 = 0$  (nincs 5-ös) esetén 3-hatványt kapunk, ami triviális, hogy nem a legjobb.  $l_2 = 1$  esetén vagy  $m = 3^{l_1} \cdot 5 \cdot 7$  , amiből könnyen jön  $l_1 \le 7$  , tehát  $d(m) \le 32$  , vagy pedig  $m = 3^{l_1} \cdot 5$  , amiből bőven  $d(m) < 10\cdot 2$  .  $l_2 \ge 2$  és  $l_1 \ge 3$  esetén  $\frac {11}{15}m$  -nek legalább  $\frac 21 \cdot \frac 34 \cdot \frac 23 = 1$  -szer annyi osztója van és kisebb, ellentmondás.  $l_1 = l_2 = 2$  esetén  $l_3 \ge 2$  , ezért  $\frac {11}{7}m$  jobb. Tehát feltehető, hogy  $l_4 = 1$  ,  $l_5 = 0$  . Vagyis  $m = 3\cdot 5\cdot 7\cdot 11 \cdot m' = 1155m'$  , ahol  $m'$  prímtényezői a  $ 3$  ,  $ 5$  ,  $ 7$  közül kerülnek ki.  $m_0 < 20$  .  $m_0$  lehetséges értékei  $ 1, 3, 5, 7, 9, 15$  , amik közül könnyen látszik, hogy a  $ 15$  élesen a legjobb (  $d(m)=36)$  ), tehát  $m = 3^2 \cdot 5^2 \cdot 7 \cdot 11$  , amiből  $n = \frac{m-1}2 = 8662$  . A lépéseket követve az is látható, hogy más  $m'<20000$  -re  $d(m')<d(m)$  .

Megjegyzés

Ez a példa rokona a szokásos feladatoknak, hogy pl. ,,volt  $n$  süti, és akár  $ 2, 3, 4, \ldots$  felé akarták osztani, mindig maradt 1 extra, mennyi  $n$  ?''.