| Описание и условия задач |
Решения задач части 1 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
4.1Решить систему уравнений:
$\qquad\qquad
\left \{ \begin{matrix}
x^2 + \lfloor y \rfloor = 10 \\
y^2 + \lfloor x \rfloor = 13
\end{matrix}
\right .
$
Эта система уравнений мне буквально вскружила голову. Никак не мог получить решения для отрицательных $x$ и $y$, будучи убежден что в этом случае они могут возрастать до бесконечности. Наверное так бы и застрял в этом неведении, если бы не подсказка скромного dxiv на форуме Mathematics Stack Exchange.
Прибавляя $x^2$ к обоим частям неравенства $\lfloor y \rfloor \lt y+1$, получаем: $$ x^2+y \lt x^2 + \lfloor y \rfloor + 1 = 11 $$ аналогично $$ y^2+y \lt y^2 + \lfloor x \rfloor + 1 = 14 $$
Складывая полученные неравенства получаем: $$ x^2+y^2+x+y \lt = 24 $$
Подумайте над извечным вопросом «Что же дальше?», прежде чем продолжать чтение.Если бы меня этом спросили, я наверняка ответил бы. Но в том то и беда, что спрашивать было некому!😉
Вот продолжение: учитывая тождества $x^2+x=(x+\frac{1}{2})^2-\frac{1}{4}$, $y^2+y=(y+\frac{1}{2})^2-\frac{1}{4}$, полученное неравенство можно записать в следующем виде: $$ \left (x+\dfrac{1}{2} \right)^2 + \left(y+\dfrac{1}{2}\right)^2 \lt 24\frac{1}{2} \lt 25 $$
Маленький нюанс поставил все на свои места. Теперь понятно, что $\left|x+\frac{1}{2} \right| \lt 5$, или $-5\frac{1}{2} \lt x \lt 4\frac{1}{2}$, откуда $-6 \leqslant \lfloor x \rfloor \leqslant 4$, поэтому из второго уравнения системы получаем: $$ 9 \leqslant y^2 = 13-\lfloor x \rfloor \leqslant 19 $$ или $$ 3 \leqslant |y| \leqslant \sqrt{19} $$
Рассмотрим отдельно случаи положительного и отрицательного $y$.
a) $y \geqslant 0$, таким образом $3 \leqslant y \leqslant \sqrt{19} $, следовательно $3\leqslant\lfloor y \rfloor \leqslant 4$. В таком случае из первого уравнения системы получаем: $x=\pm\sqrt{7}$ для $y=3$ и $x=\pm\sqrt{6}$ для $y=4$ .
Если $x$ — положительно, то есть $x=\sqrt{6}$ или $x=\sqrt{7}$, то $\lfloor x \rfloor = 2$, следовательно из второго уравнения системы (помятуя $y \geqslant 0$) получаем $y=\sqrt{11}$. При этом $\lfloor y \rfloor = 3$, так что $x=\sqrt{7}$. Мы получили первое решение: $(\sqrt{7},\;\sqrt{11})$, и, как вскоре в этом убедимся, далеко не последнее.
Если $x$ — отрицательно, то $x=-\sqrt{6}$ или $x=-\sqrt{7}$, поэтому $\lfloor x \rfloor = -3$, так что в этот раз второе уравнение дает $y=4$. Поскольку $\lfloor y\rfloor =4$, то $x=-\sqrt{6}$, так что второе решение $(-\sqrt{6},\;4)$.
б) $y \lt 0$, следовательно $-\sqrt{19} \leqslant y \leqslant -3$, откуда $-5 \leqslant\lfloor y \rfloor \leqslant -3$. В таком случае из первого уравнения системы получаем: $x=\pm\sqrt{15}$, $\pm\sqrt{14}$, $\pm\sqrt{13}$ для $y=-5$,$-4$ и $-3$ соответственно.
Если $x$ — положительно, то в любом из трех случаев $\lfloor x \rfloor = 3$, следовательно из второго уравнения системы (помятуя $y \lt 0$) получаем $y=-\sqrt{10}$. При этом $\lfloor y \rfloor = -4$, так что $x=\sqrt{14}$. Получили третье решение: $(\sqrt{14},\;-\sqrt{10})$.
Наконец, если $x$ — отрицательно, то $\lfloor x \rfloor = -4$, что соответствует $y=-\sqrt{17}$. При этом $\lfloor y \rfloor = -5$, так что $x=-\sqrt{15}$. Таким образом. последнее четвертое решение: $(-\sqrt{15},\;-\sqrt{17})$.
Ответ: $(\sqrt{7},\;\sqrt{11})$, $(-\sqrt{6},\;4)$, $(\sqrt{14},\;-\sqrt{10})$, и $(-\sqrt{15},\;-\sqrt{17})$.
Графическое решение системы уравнений показано ниже. Постарался, сделать чертеж настолько понятным, насколько мог. Точки пересечения обозначены красным цветом.
 Графическое решение системы уравнений $\left \{ \begin{matrix} x^2 + \lfloor y \rfloor = 10 \\y^2 + \lfloor x \rfloor = 13\end{matrix}\right .$ |
4.2Решить уравнение в целых положительных числах: $\quad \lfloor\sqrt[3]{1}\rfloor + \lfloor\sqrt[3]{2}\rfloor + ... + \lfloor\sqrt[3]{x^3-1}\rfloor = 400$
Олимпиада Англии, 1975 год, однако давно стала математической классикой.
Обозначим через $n$–е слагаемое через $a_n$. Таким образом $a_n=\left\lfloor \sqrt[3]{a} \right\rfloor$
Запишем $n$ и соответствующие $a_n$ в таблицу:
| $n$ | 1 | 2 | ... | 7 | 8 | 9 | ... | 26 | 27 | 28 | ... | (x-1)3-1 | (x-1)3 | (x-1)3+1 | ... | x3-1 | $a_n=\left\lfloor \sqrt[3]{n} \right\rfloor$ | 1 | 1 | ... | 1 | 2 | 2 | ... | 2 | 3 | 3 | ... | x-2 | x-1 | x-1 | ... | x-1 |
|---|
Mы видим, что каждый полный куб $n=i^3$ увеличивает значение $a_n$, делая его равным $i$.
Таким образом все слагаемые можно разделить на $x-1$ множеств, так что $i$-е множество начинается $(i^3)$-м элементом и заканчивается $((i+1)^3-1)$-м элементом. В этом множестве будет $(i+1)^3-i^3=3i^2+3i+1$ слагаемое, значение каждого из которых равно $i$. Таким образом можно вычислить сумму элементов $i$-го множества: $$ s_i = a_{i^3} + a_{i^3+1} + ... + a_{(i+1)^3-1} = i(3i^2+3i+1) \label{eq:0201}\tag{4.2.1} $$
Используя формулу суммы квадратов и кубов первых натуральных чисел, можно вычислить общую сумму и приравнять ее к 400, пытаясь подобрать целый корень полученного уравнения четвертой степени. Стоит ли усложнять жизнь, когда есть хоть не столь изящный, зато куда более легкий метод? Думаю, вы догадались, о каком методе идет речь.
Действительно, речь идет о методе проб. Введем обозначение $S_x$ для суммы с накоплением: $$ S_x = s_1 + s_2 +... + s_{x-1} $$
Будем увеличивать $x$, и накапливать $S_x$, вычисляя дополнительное слагаемое $s_{x-1}$ по формуле $\eqref{eq:0201}$, пока не получим требуемое число. После этого продолжать процесс не имеет смысла, так как дальнейшие числа будут больше требуемого.
Вычисления записываем в таблицу:
| $x$ | $s_{x-1}$ | $S_x$ |
|---|---|---|
| 1 | - | 0 |
| 2 | 7 | 7 |
| 3 | 38 | 45 |
| 4 | 111 | 156 |
| 5 | 244 | 400 |
Получилось! Ответ: $x=5$.
4.3 Доказать что для целого положительного $n$ $\quad\{\sqrt{1}\} + \{\sqrt{2}\} + ... + \{\sqrt{n^2}\} \leqslant \dfrac{n^2-1}{2}$, причем равенство имеет место тогда и только тогда, когда $n=1$.
На первый взгляд может показаться, что последнее слагаемое присутствует из чисто эстетических соображений, поскольку $\{\sqrt{n^2}\} = \{n\}=0$, так что его можно отбросить. Однако, если $n=1$, то отбросить последнее слагаемое не удается лишь потому, что оно единственное. Понятно, что в этом случае сумма равна нулю, при этом правая часть неравенства также обращается в нуль.
В дальнейшем будем считать, что $n \geqslant 2$, так что последнее слагаемое действительно можно игнорировать, считая что в сумме ($n^2-1$) слагаемых. Покажем, что в этом случае неравенство является строгим.
Действуем аналогично предыдущему решению, только, разумеется, в этот раз вместо кубов будем использовать квадраты. Обозначим через $a_m$ целую часть квадратного корня из $m$: $a_m=\left\lfloor \sqrt{a} \right\rfloor$.
Запишем $m$ и соответствующие значения $\left\lfloor \sqrt{m} \right\rfloor$ в таблицу:
| $m$ | 1 | 2 | 3 | 4 | 5 | ... | 8 | 9 | 10 | ... | (n-1)2-1 | (n-1)2 | (n-1)2+1 | ... | n2-1 | $\left\lfloor \sqrt{m} \right\rfloor$ | 1 | 1 | 1 | 2 | 2 | ... | 2 | 3 | 3 | ... | $n-2$ | n-1 | $n-1$ | ... | $n-1$ |
|---|
Замечаем, что каждый полный квадрат $m=i^2$ увеличивает значение $\left\lfloor \sqrt{m} \right\rfloor$, делая его равным $i$.
Разобьем числа $m$ ($1\leqslant m \leqslant n^2-1$) на множества $G_i$ ($1\leqslant i \leqslant n-1$), каждое из которых содержит числа от $i^2$ до $((i+1)^2-1)$ включительно. Таким образом $G_i$ состоит из $(i+1)^2-i^2=2i+1$ элементов причем для каждого $m \in G_i$ имеет место $\left\lfloor \sqrt{m} \right\rfloor=i$.
Будем нумеровать элементы внутри $G_i$ с нуля. Тогда $j$-й ($0 \leqslant j \leqslant 2i$) элемент $G_i$ равен $b_{i,j}=i^2+j$, отсюда, ввиду $\left\lfloor \sqrt{b_{i,j}} \right\rfloor = i$, $$ \left\{\sqrt{b_{i,j}}\right\} = \sqrt{i^2+j}-i $$
Поскольку $\left\{\sqrt{b_{i,0}}\right\}= \sqrt{i^2}-i = 0$, нулевой элемент можно игнорировать. Если $j>0$ (а такие элементы обязательно найдутся, так как $2i+1 \gt 1$ при $i \geqslant 1$), то, используя тождество $a-b=\dfrac{a^2-b^2}{a+b}$, приходим к следующему: $$ \left\{\sqrt{b_{i,j}}\right\} = \frac{j}{\sqrt{i^2+j}+i} \lt \frac{j}{2i} $$
Это позволяет оценить сумму $\left\{\sqrt{b_{ij}}\right\}$, для элементов $G_i$: $$ s_i = \left\{\sqrt{b_{i,1}}\right\} + ... + \left\{\sqrt{b_{i,2i}}\right\} \lt \frac{1}{2i}+...+\frac{2i}{2i}= \frac{1+...+2i}{2i} = \frac{2i+1}{2} $$
Осталось оценить общую сумму: $$ s_1 + s_2 + ... + s_{n-1} \lt \frac{3}{2} + \frac{5}{2}+...+\frac{2n-1}{2} = \frac{(2n+2)(2n-1)}{4} = \frac{n^2-1}{2}, $$ quod erat demonstrandum.
4.4Доказать, что если $p$ и $q$ — взаимно-простые числа, то: $\quad \left\lfloor \dfrac{p}{q} \right\rfloor + \left\lfloor \dfrac{2p}{q} \right\rfloor ... \left\lfloor \dfrac{(q-1)p}{q} \right\rfloor = \dfrac{(p-1)(q-1)}{2}$
Источник: А. Егоров. «Целая и дробная части числа» Квант №5, 2002. Приводится решение из статьи.
В системе координат рассмотрим прямоугольник ограниченный координатными осями, а также прямыми $x=q$ и $y=p$. Количество точек с целочисленными координатами находящихся внутри прямоугольника (но не вдоль его периметра) равно $(p-1)(q-1)$.
Проведем диагональ прямоугольника проходящую через начало координат. Уравнение прямой, на которой лежит диагональ: $y=\frac{p}{q}x$.
Покажем, что диагональ не содержит точек с целочисленными координатами, не совпадающих с ее концами. В самом деле, если точка ($m$,$n$) ($m$ и $n$ — целые числа, причем $0\lt m \lt q$ и $0\lt n \lt p$) принадлежит диагонали, то $n=\frac{p}{q}m$, или $pm=qn$. Отсюда $pm$ делится на $q$ и так как по условию $p$ и $q$ — взаимно простые числа, то $m$ должно делиться на $q$, что невозможно, так как $0 \lt m \lt q$.
Таким образом каждая точка с целочисленными координатами, лежащая внутри прямоугольника лежит также внутри соответствующего треугольника, а не на его границе. Ввиду симметрии относительно центра прямоугольника каждый треугольник содержит одинаковое количество внутренних точек с целочисленными координатами и это количество равно $S = \dfrac{(p-1)(q-1)}{2}$
Подсчитаем количество точек с целочисленными координатами лежащих ниже диагонали прямоугольника другим способом. Для некоторого целого $k$, такого что $0 \lt k \lt q$ рассмотрим точку диагонали $M$ с абсциссой $k$. Так как ордината точки $M$ равна $\dfrac{p}{q}k$, то непосредственно под точкой $M$ находится $\left\lfloor\dfrac{p}{q}k \right\rfloor $ точек с целочисленными координатами. Суммируя по всем $k$ от $1$ до $q-1$ получим общее количество точек с целочисленными координатами, лежащими внутри треугольника под диагональю: $$ S = \left\lfloor \frac{p}{q} \right\rfloor + \left\lfloor \frac{2p}{q} \right\rfloor + ... \left\lfloor \frac{(q-1)p}{q} \right\rfloor $$
Приравнивая значения полученные различными способами, приходим к утверждению задачи.
4.5Доказать, что для целого положительного $n$: $\quad\lfloor x \rfloor + \left\lfloor x+\dfrac{1}{n} \right\rfloor ... \left\lfloor x+\dfrac{n-1}{n} \right\rfloor = \lfloor nx \rfloor $
Источник тот же, что и в предыдущей задаче. В этот раз авторское решение отсутствует, так что приходится довольствоваться собственным.
Так как $\left(x+\frac{n-1}{n}\right)-x = \frac{n-1}{n} \lt 1$, значения слагаемых в левой части могут различаться между собой не более, чем на единицу.
Из $x+\frac{i}{n} = \lfloor x \rfloor + \left(\{x\}+\frac{i}{n}\right)$ следует, что $\left\lfloor x +\frac{i}{n} \right\rfloor$ равно $\lfloor x \rfloor$, если $\{x\}+\frac{i}{n} \lt 1$, и $\lfloor x \rfloor+1$ в противном случае.
Пусть $k$ — наименьшее значение $i$, при котором $\{x\}+\frac{i}{n} \geqslant 1$. Это означает следующее: $$ \{x\}+\frac{k-1}{n} \lt 1 \leqslant \{x\}+\frac{k}{n} \label{eq:0501}\tag{4.5.1} $$
Поскольку начальные $k$ слагаемых левой части (соответствующие $i=0,\;1,\;...\;k-1$) равны $\lfloor x \rfloor$ , а остальные $n-k$ слагаемых равны $\lfloor x \rfloor+1$, их сумма равна: $$ k \lfloor x \rfloor + (n-k)(\lfloor x \rfloor+1) = n\lfloor x \rfloor + n-k \label{eq:0502}\tag{4.5.2} $$
Осталось показать, что правая часть полученного равенства есть не что иное, как $\lfloor nx \rfloor$. Для этого заметим, что равенство $\eqref{eq:0501}$ можно записать в виде: $$ 1-\frac{k}{n}\leqslant \{x\} \lt 1-\frac{k-1}{n} $$ что после умножения на $n$ дает: $$ n-k \leqslant n\{x\} \lt n-k+1 \label{eq:0503}\tag{4.5.3} $$
Прибавляя $n\lfloor x \rfloor$ ко всем частям неравенства $\eqref{eq:0503}$, получаем: $$ n\lfloor x \rfloor+n-k \leqslant n(\lfloor x \rfloor +\{x\}) \lt n\lfloor x \rfloor+n-k+1 $$ или $$ n\lfloor x \rfloor+n-k \leqslant nx \lt n\lfloor x \rfloor+n-k+1 $$ откуда $\lfloor nx \rfloor = n\lfloor x \rfloor+n-k$, что совпадает с правой частью равенства $\eqref{eq:0502}$.
4.6Для целого неотрицательного $n$ и целого положительного $k$ доказать тождество: $\left\lfloor \dfrac{n}{k}\right\rfloor + \left\lfloor \dfrac{n+1}{k}\right\rfloor + \dots + \left\lfloor \dfrac{n+k-1}{k}\right\rfloor = n$
Зафиксируем целое положительное $k$ и докажем, что при выбранном $k$ тождество выполняется при любом целом неотрицательном $n$.
Для краткости обозначим левую часть доказываемого тождества через $S_k(n)$ и применим метод математической индукции.
База индукции. При $n=0$ в каждом из слагаемых для $S_k(n)$ числитель меньше знаменателя. Таким образом, все слагаемые — нули, $S_k(0) = 0$, и тождество действительно имеет место.
Индукционный переход. Докажем, что из $S_k(n) = n$ следует $S_k(n+1) = n+1$. Имеем: $$ \begin{align} S_k(n) = \left\lfloor \dfrac{n}{k}\right\rfloor + \left\lfloor \dfrac{n+1}{k}\right\rfloor + \dots + \left\lfloor \dfrac{n+k-1}{k}\right\rfloor \\ S_k(n+1) = \left\lfloor \dfrac{n+1}{k}\right\rfloor + \left\lfloor \dfrac{n+2}{k}\right\rfloor + \dots + \left\lfloor \dfrac{n+k}{k}\right\rfloor \end{align} $$
Вычтем из второго равенства первое. Тогда все слагаемые правой части, кроме крайних, взаимно уничтожаются. Получаем: $$ S_k(n+1)-S_k(n) = \left\lfloor \frac{n+k}{k}\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor = \left\lfloor \frac{n}{k}+1\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor $$
Согласно свойству 5 целой части $\left\lfloor \frac{n}{k}+1 \right\rfloor = \left\lfloor \frac{n}{k} \right\rfloor +1$, следовательно $S_k(n+1)-S_k(n)=1$. Так как, согласно индукционному предположению, $S_k(n) = n$, то $$ S_k(n+1) = S_k(n) + 1 = n + 1 $$ чем завершается доказательство.
4.7Доказать тождество для целого неотрицательного $n$: $\quad \lfloor \sqrt{n} + \sqrt{n+1} \rfloor = \lfloor \sqrt{4n+2}\rfloor$
Из австрийской олимпиады 1974 года. Приводится авторское решение с незначительными улучшениями.
Согласно неравенству между средне-арифметическим и средне-геометрическим $2\sqrt{n(n+1)} \leqslant 2n+1$ (равенства на самом деле быть не может, так как числа различные, но это не существенно), поэтому $$ (\sqrt{n}+\sqrt{n+1})^2=2n+1+2\sqrt{n(n+1)}\leqslant 4n+2\,. $$
Отсюда $\sqrt{n}+\sqrt{n+1} \leqslant \sqrt{4n+2}$, так что $$ \lfloor \sqrt{n}+\sqrt{n+1} \rfloor \leqslant \lfloor \sqrt{4n+2} \rfloor \label{eq:0701}\tag{4.7.1} $$
Остается показать, что полученное неравенство является равенством при всех целых неотрицательных $n$.
Допустим, что и неравенство $\eqref{eq:0701}$ является строгим для некоторого целого неотрицательного $n$. Тогда существует целое $m$, такое что $$ \sqrt{n}+\sqrt{n+1} \lt m \leqslant \sqrt{4n+2} $$
Возводим в квадрат:$$ 2n+1+2\sqrt{n(n+1)} \lt m^2 \leqslant 4n+2 $$
Учитывая что $\sqrt{n(n+1)}\geqslant n$ для целого неотрицательного $n$ (опять неравенство на самом деле строгое!), получаем: $$ 4n+1 \lt m^2 \leqslant 4n+2 $$ и поскольку $m^2$ — целое число, то $$ m^2=4n+2=2(2n+1) $$
Есть среди нас такие, у кого последнее равенство вызывает чувство дискомфорта? Обязательно есть! Квадрат целого числа делится на 2, но не делится на 4, что невозможно себе представить даже в фильмах ужасов! Полученное противоречие доказывает утверждение.
4.8Доказать, что уравнение: $\quad\lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor + \lfloor 32x \rfloor = 12345\quad$ не имеет решений.
Канадская олимпиада, 1981. Приводится авторское решение.
Обозначим сумму слева через $S$: $$ S = \lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor + \lfloor 32x \rfloor $$
Из свойства 6b следует: $$ 2\lfloor x \rfloor \leqslant \lfloor 2x \rfloor \leqslant 2\lfloor x\rfloor+1 \\ 4\lfloor x \rfloor \leqslant \lfloor 4x \rfloor \leqslant 4\lfloor x\rfloor+3 \\ 8\lfloor x \rfloor \leqslant \lfloor 8x \rfloor \leqslant 8\lfloor x\rfloor+7 \\ 16\lfloor x \rfloor \leqslant \lfloor 16x \rfloor \leqslant 16\lfloor x\rfloor+15 \\ 32\lfloor x \rfloor \leqslant \lfloor 32x \rfloor \leqslant 32\lfloor x \rfloor+31 $$
Складывая эти неравенства и добавляя $\lfloor x \rfloor$ ко всем частям, получаем: $$ 63 \lfloor x \rfloor \leqslant S \leqslant 63 \lfloor x \rfloor + 57 $$
Таким образом, остаток от деления $S$ на $63$ не может быть больше $57$. Кстати, а какой остаток дает $12345$ при делении на $63$? Давайте проверим: $12345 = 63 \cdot 195 + 60$. Комментарии излишни.
Достойный финал для этой серии задач!
| Описание и условия задач |
Решения задач части 1 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
Комментариев нет:
Отправить комментарий