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

[Ktina]

Докажите, что число

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

чётно при любом натуральном $n$.
(Индия, 2014, национальный этап)

[TOTAL]

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

В конце этой суммы стоят слагаемые равные единице, их $\left\lfloor \frac{n}{1} \right\rfloor- \left\lfloor \frac{n}{2} \right\rfloor $ штук.
А перед ними слагаемые равные двойке, которые вообще не учитываем.
Поэтому с точностью до четности имеем

$$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor= \left\lfloor \frac{n}{1} \right\rfloor- \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor= \left\lfloor \frac{n}{3} \right\rfloor+ \left\lfloor \frac{n}{4} \right\rfloor + \cdots + \left\lfloor \frac{n}{\left\lfloor \frac{n}{3} \right\rfloor} \right\rfloor $$

И так далее. Думаю, всё благополучно получится.

[Ktina]

TOTAL
Спасибо, но как-то запутанно у Вас...

[versham]

Доказательство по индукции.
База. $n=1$
$[\frac{1}{1}]+[\sqrt{1}]=2\equiv 0$
(все сравнения идут по модулю $2$, если не оговорено иное)

Переход. Пусть утверждение верно для $n$, т. е.
$[\frac{n}{1}] + \dots + [\frac{n}{n}] + [\sqrt{n}] \equiv 0$
А нам нужно доказать
$[\frac{n+1}{1}]+\dots+[\frac{n+1}{n}]+[\frac{n+1}{n+1}]+[\sqrt{n+1}] \equiv 0$
Посмотрим, что произойдет при переходе к $n+1$. Заметим, что
$[\frac{n}{m}]\neq[\frac{n+1}{m}]$
возможно только в случае
$n+1\equiv 0 (\mod m)$
В этом случае слагаемое увеличивается на $1$. Всего тогда к сумме прибавится $\sigma_0(n+1)-1$ (где $\sigma_0(x)$ - кол-во положительных делителей $x$). $-1$ появился потому, что не был задействован делитель $n+1$ (в исходной сумме из утверждения для $n$ его нет). Еще к сумме добавилось слагаемое $[\frac{n+1}{n+1}]=1$. И наконец, могло изменится последнее слагаемое, это возможно только если $n+1$ - точный квадрат. Тогда разберем два случая:
1. $n+1$ - не точный квадрат.
Тогда нужно доказать, что
$\sigma_0(n+1)\equiv 0$
Это очень легкое утверждение: если $n+1$ делится на какое-то число $a$ и $\frac{n+1}{a}=b$, то $n+1$ делится на $b$, причем $a\neq b$ (иначе число $n+1$ было бы квадратом). То есть у каждого делителя числа есть пара, причем одно из этих чисел всегда строго меньше $\sqrt{n+1}$, другое - строго больше. Таким образом, если мы будем перебирать все делители меньше $\sqrt{n+1}$, мы всегда будем находить сразу пару делителей. То есть число делителей четно.
2. $n+1$ - точный квадрат.
Теперь нужно, наоборот
$\sigma_0(n+1)\equiv 1$
То же самое, что и в предыдущем случае, только один делитель $n+1$ не будет иметь пары - это $a=\sqrt{n+1}$:
$n+1=a \cdot a$. И количество делителей получается нечетным.

[wrest]

Очевидно не.. не так. Широко известно, что не... опять не так. Короче, есть подозрение, что

$$\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 \eqno(1)$$

Тогда остается только рассмотреть сумму

$$s=\lfloor \sqrt{n}\rfloor^2-\lfloor \sqrt{n}\rfloor \eqno(2)$$

В которой очевидно что $s$ - четное, т.к. возведение в квадрат не меняет четности а сумма (разность) двух чисел одной четности - четная.

Осталось доказать (1). И тут видно откуда собсно вылезает корень.

versham в сообщении #1332447 писал(а):

Доказательство по индукции.

Да, кажись всё сходится. Но неясный момент с количеством делителей. Вроде всё так, но почему прибавляется именно прибавится $\sigma_0(n+1)-1$ (про минус единицу ясно)?

[versham]

wrest в сообщении #1332453 писал(а):

versham в сообщении #1332447 писал(а):

Доказательство по индукции.

Да, кажись всё сходится. Но неясный момент с количеством делителей. Вроде всё так, но почему прибавляется именно прибавится $\sigma_0(n+1)-1$ (про минус единицу ясно)?

Я показал, что увеличиваются все слагаемые вида $[\frac{n+1}{m}]$, где $m|n+1$. Очевидно, все положительные делители $n+1$ будут перечислены в знаменателях этой суммы (потому что там перечислены вообще все целые числа от $1$ до $n$), то увеличится ровно столько слагаемых, сколько делителей у числа $n+1$. Из всех делителей не будет только самого $n+1$, отсюда, как я говорил, появляется $-1$.

[wrest]

versham Да, тут тогда получается, что попутно выяснилось, что (это следует из той же индукции)

$$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor = \sigma_0(1)+\sigma_0(2)+...+\sigma_0(n)$$

то есть в итоге:

$$\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=\sum\limits_{i=1}^n\sigma_0(i)$$

[grizzly]

Идея versham вполне рабочая, но изложение немного сумбурное. Рассмотреть 2 простых случая: переход от неквадрата к квадрату и остальное. В первом случае сумма увеличится на число делителей плюс 1, во втором просто на число делителей. И то и другое чётное. Задача совсем простая, если выписать одно под другим несколько сумм для первых чисел и заметить это:

versham в сообщении #1332447 писал(а):

Заметим, что
$[\frac{n}{m}]\neq[\frac{n+1}{m}]$
возможно только в случае
$n+1\equiv 0 (\mod m)$
В этом случае слагаемое увеличивается на $1$.

Чётные и нечётные рассматривать совсем не нужно, кажется.

[12d3]

Запишем на доске все упорядоченные пары натуральных чисел $(a,b)$, произведение которых не превосходит $n$ и где $a\le b$. А потом для каждой пары $(a,b)$ запишем еще пару $(b,a)$. Всего на доске окажется четное количество пар. А теперь посчитаем их. Уникальных пар, в которых первое число равно $\displaystyle k$, будет $\displaystyle \left\lfloor \frac{n}{k} \right\rfloor$. Итого уникальных пар будет $\displaystyle \sum\limits_{k=1}^{n}\left\lfloor \frac{n}{k} \right\rfloor$ штук. Но у нас некоторые пары дублируются, те, в которых одинаковые числа. Таких пар будет $ \left\lfloor \sqrt{n} \right\rfloor$ штук. Итого, на доске записано $\displaystyle \sum\limits_{k=1}^{n}\left\lfloor \frac{n}{k} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$ пар, а оно по построению четное.

[wrest]

12d3 в сообщении #1332493 писал(а):

Запишем на доске все упорядоченные пары натуральных чисел $(a,b)$, произведение которых не превосходит $n$ и где $a<b$.

Ok, пусть $n=5$ Записываем все такие пары: $(1,2);(1,3);(1,4);(1,5)$

12d3 в сообщении #1332493 писал(а):

А потом для каждой пары $(a,b)$ запишем еще пару $(b,a)$.

Записываем $(2,1);(3,1);(4,1);(5,1)$

12d3 в сообщении #1332493 писал(а):

Всего на доске окажется четное количество пар. А теперь посчитаем их.

Получилось $8$ пар, четное.

12d3 в сообщении #1332493 писал(а):

Уникальных пар, в которых первое число равно $\displaystyle k$, будет $\displaystyle \left\lfloor \frac{n}{k} \right\rfloor$.

Ок, берем $k=2$, и такая пара одна: $(2,1)$ хотя $\displaystyle \left\lfloor \frac{5}{2} \right\rfloor=2$

[kotenok gav]

wrest в сообщении #1332498 писал(а):

Ok, пусть $n=5$ Записываем все такие пары: $(1,2);(1,3);(1,4);(1,5)$

12d3 исправил, теперь еще есть (1,1) и (2,2).

[12d3]

wrest
Я там поправил очепятку. $a \le b$ вместо $a < b$.

[wrest]

12d3 в сообщении #1332501 писал(а):

Я там поправил очепятку. $a \le b$ вместо $a < b$.

А, тогда O'k

Можете, кстати, пояснить как получить еще вот это:

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

[Shadow]

Подведем итоги хороших идей:

Пусть $f(n)=\sum\limits_{k=1}^{n} \left\lfloor\dfrac n k \right\rfloor$

Тогда
$f(n)-f(n-1)=\tau(n)$

где $\tau(n)$ - число делителей $n$

Пусть $g(n)=f(n)+\lfloor\sqrt n\rfloor$

Тогда $g(n)-g(n-1)=\tau(n)+\lfloor\sqrt n\rfloor- \lfloor\sqrt {n-1}\rfloor$

------------------

Для доказательства методом мат. индукции достаточно

$g(1)$ - четное

$g(n)-g(n-1)$ - четное $\forall n \in \mathbb{N}$

$\tau(n)$ (как правило) четное, если $n$ не являтся квадратом, но тогда $\lfloor\sqrt n\rfloor= \lfloor\sqrt {n-1}\rfloor$

а если квадрат...ну вы меня поняли.

[TOTAL]

Ktina в сообщении #1332435 писал(а):

TOTAL
Спасибо, но как-то запутанно у Вас...

Легко распутывается. Например, так.

Вся сумма представляет собой количество квадратиков один на один, лежащих в первом квадранте ниже кривой $y=n/x$, но не лежащих на прямой $y=x$ (их "уничтожает" корень). Из-за симметрии относительно $y=x$ это число четное.

Берем другую симметричную убывающую функцию и получаем снова четное число

$$\left\lfloor \sqrt{n^2-1^2} \right\rfloor+ \left\lfloor \sqrt{n^2-2^2} \right\rfloor + \cdots + \left\lfloor \sqrt{n^2-n^2} \right\rfloor + \left\lfloor n/\sqrt{2} \right\rfloor$$