Докажите чётность числа

[Neoguri]

Вы тут переоткрываете Dirichlet hyperbola method.

[wrest]

Neoguri
Спасибо большое!

Итак:


Синяя гипербола $y=14/x$, красная $y=15/x$, зеленая $y=16/x$

Синие точки -- это точки с целочисленными координатами под синей гиперболой, красные -- точки которые добавляются для красной гиперболы по сравнению с синей, зеленые -- добавляются для зеленой по сравнению с красной. "Проколотые" точки - лежат на прямой $y=x$, "сплошные" -- остальные.

Синих точек всего $41$. И это число -- сумма

$$\left\lfloor \frac{14}{1} \right\rfloor+ \left\lfloor \frac{14}{2} \right\rfloor + \cdots + \left\lfloor \frac{14}{14} \right\rfloor$$

Самый левый вертикальный ряд -- $14$ точек, это $\left\lfloor \frac{14}{1} \right\rfloor$, следующий это $7$ точек и $\left\lfloor \frac{14}{2} \right\rfloor$ и так далее.
На прямой $y=x$ расположены "проколотые" точки, и их соответственно $\left\lfloor \sqrt{14} \right\rfloor=3$
"Сплошных" точек очевидно четное число в силу симметрии.

Теперь про корень. Светло-синим прямоугольником выделена сумма $\cdot\sum\limits_{i=1}^{\lfloor \sqrt{14}\rfloor=3}\lfloor\dfrac{14}{i}\rfloor=25$
Эта же сумма выделена розовым прямоугольником. Всего в обоих прямоугольниках $50$ точек. Но пересечение прямоугольников есть квадрат $3\texttt{x} 3$ в котором соответственно $9$ точек которые учлись дважды, так что всего синих точек $2\cdot 25 - 9 =41$. Это собсно откуда берется квадрат целой части корня вот тут:

$$\sum\limits_{i=1}^n\lfloor\dfrac{n}{i}\rfloor=2\cdot\sum\limits_{i=1}^{\lfloor \sqrt{n}\rfloor}\lfloor\dfrac{n}{i}\rfloor-\lfloor \sqrt{n}\rfloor^2 $$

Ну вот собсно и всё. "Сплошные" точки -- это сумма из условия задачи: их всегда четное число в силу симметрии гиперболы.

[kotenok gav]

TOTAL говорил такое же док-во.

[wrest]

kotenok gav в сообщении #1332633 писал(а):

TOTAL говорил такое же док-во.

Ну, будем считать, что я просто проиллюстрировал его доказательство картинкой.