Фильтр
Задачи
Задача 98410 |
|
|
Шайка разбойников отобрала у купца мешок монет. Каждая монета стоит целое число грошей. Оказалось, что какую бы монету ни отложить, оставшиеся монеты можно разделить между разбойниками так, чтобы каждый получил одинаковую сумму в грошах. Докажите, что если отложить одну монету, то число монет разделится на число разбойников.
Решение
Можно считать, что стоимости монет в грошах взаимно просты. Действительно, если они имеют наибольший общий делитель d > 1, то деноминируем грош, приравняв один новый к d старым. Тогда все условия задачи по-прежнему выполнены, но новые стоимости монет будут взаимно простыми.
Пусть n разбойников отняли m монет на общую сумму в g грошей. Так как при вычитании из g стоимости любой монеты получим число, кратное n, то стоимости всех монет дают при делении на n один и тот же остаток r. Так как стоимость любого набора из m – 1 монет делится на n, то (m – 1)r делится на n. Кроме того, r и n взаимно просты, поскольку любой их общий делитель является общим делителем стоимостей всех монет. Отсюда следует, что
m – 1 делится на n.
|
|
Задача 35406 |
|
|
Дано n целых чисел, каждое из которых взаимно просто с n. Также дано неотрицательное целое число r < n.
Докажите, что среди данных n чисел можно выбрать несколько чисел, сумма которых дает остаток r при делении на n.
Подсказка
Доказывайте следующее более общее утверждение: если дано k (0 < k < n + 1) чисел, взаимно простых с n, то среди сумм некоторых из этих k чисел встретится не менее k остатков от деления на n.
Решение
Утверждение задачи следует из более общего утверждения: если дано k (0 < k ≥ n) чисел, взаимно простых с n, то среди сумм некоторых из этих k чисел встретится не менее k остатков от деления на n. Последнее утверждение докажем индукцией по k. База (k = 1) очевидна.
Шаг индукции. Пусть даны числа a0, a1, a2, ..., ak (k + 1 ≤ n), взаимно простые с n. По предположению индукции среди сумм некоторых из чисел a1, a2, ..., ak встретится не менее k различных остатков от деления на n; пусть R – множество этих остатков. Если R в более k элементов, то все уже доказано. Пусть в R ровно k элементов и среди сумм некоторых из чисел a0, a1, a2, ..., ak встречаются только остатки из множества R. Рассмотрим сумму S некоторых из чисел a1, a2, ..., ak, дающую остаток r ∈ R от деления на n. Тогда сумма S + a0 снова даёт некоторый остаток r' ∈ R. Отсюда следует, что для любого остатка r ∈ R остаток числа r + a0 также принадлежит R. Значит, остатки всех чисел r, r + a0, r + 2a0, ..., r + (n – 1)a0 принадлежат множеству R, состоящему из k < n остатков. Однако, выписанные числа дают различные остатки от деления на n. Действительно, разность (r + ka0) – (r + ma0) = (k – m)a0 не делится на n, так как 0 < |k – m| < n, а (a0, n) = 1. Противоречие.
|
|
|
Задача 78761 |
|
|
Имеется натуральное число n > 1970. Возьмём остатки от деления числа 2n на 2, 3, 4, ..., n. Доказать, что сумма этих остатков больше 2n.
Решение
Обозначим сумму остатков от деления 2n на числа 1, 2, ..., n через Sn. Мы докажем, что Sn > 3,5n при n > 1000.
2n не делится нацело ни на какое нечётное число, отличное от 1, значит, остаток от деления 2n на такое число не меньше 1. Отсюда легко вывести, что для любого нечётного k > 1 остаток от деления 2n на 2lk не меньше 2l.
Отсюда следует, что Sn ≥ n0 + 2n1 + 22n3 + ... + 2mnm, где ni – количество не превосходящих n чисел вида 2i(2k + 1), k > 1, а m определяется условиями
3·2m ≤ n < 3·2m+1 (нет смысла брать большее m, так как тогда выражение в скобке будет равно нулю).
Рассмотрим (i+1)-e слагаемое 2ini. Число ni равно числу не превосходящих n членов арифметической прогрессии 3·2i, 5·2i, 7·2i, .... Число таких членов не меньше , и, значит, это слагаемое не меньше n/2 – 3·2i–1.
Заменив сумму в правой части первыми восемью слагаемыми, получим
Sn > 8·n/2 – 3(2–1 + 1 + 2 + 2² + ... + 26) > 4n − 3·27 = 3,5n + (n/2 – 384).
При n > 1000 выражение в скобке положительно, то есть Sn > 3,5n.
|
|
|
Задача 107998 |
|
|
В ящиках лежат камни. За один ход выбирается число k, затем камни в ящиках делятся на группы по k штук и остаток менее, чем из k штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
а) не более 460 камней;
б) не более 461 камня?
Решение
Заметим, что если выбрано число k, то после хода в ящике, в котором было m камней, будет q + r камней, где q и r – частное и остаток от деления m на k соответственно.
Ясно, что достаточно рассмотреть ситуацию, когда в первом ящике лежит 1
камень, во втором – 2 камня и т. д. вплоть до n-го ящика, в котором лежит n камней (где n = 460 или 461).
1) Пусть в ящиках лежат 1, 2, ..., n камней. Пусть выбрано число k и сделан ход а f(n, k) – максимальное число камней в ящике (после хода). Тогда для любого числа камней j, 1 ≤ j ≤ f(n, k) найдётся ящик, в котором лежит j камней. Иначе говоря, числа камней в ящиках снова будут образовывать начальный отрезок натурального ряда.
Докажем это обратной индукцией по j. Пусть найдётся ящик с j камнями. Тогда найдётся такое число m (1 ≤ m ≤ n), что j = q + r, где q и r – частное и остаток от деления m на k. Если r ≠ 0, то в ящике, в котором был m – 1 камень, станет j – 1 камень. Если r = 0, то нужно рассмотреть ящик, в котором было m – k камней.
2) Пусть частное от деления n + 1 на k равно q. Рассмотрим ящик, в (q – 1)k + (k – 1) камней. В нём останется q + k – 2 камня. Нетрудно видеть, что это будет самый большой ящик (впрочем,
если n + 2 делится на k, то будет еще ровно один ящик с таким же числом камней). Итак,
f(n, k) = q + k – 2 = [n+1/k] + k – 2.
Обозначим m = , s = [m].
3) Оптимальное значение k (при котором f(n, k) достигает минимума) равно s + 1.
Доказательство. f(n, k) = [n+1/k + k] – 2. Функция n+1/x + x убывает на интервале
(0, m) и возрастает на интервале
(m, n]. Так как [x] – неубывающая функция, f(n, k) достигает минимума либо при k = s, либо при k = s + 1.
Осталось доказать, что f(n, s + 1) < f (n, s), то есть что [n+1/s+1] < [n+1/s].
Из неравенства s² ≤ n + 1 < (s + 1)² следует, что [n+1/s+1] ≤ s, а [n+1/s] ≥ s. Значит, достаточно доказать, что обе части не могут равняться s. Но
[n+1/s] = s ⇒ n+1/s < s + 1 ⇒ n+1/s+1 < s ⇒ [n+1/s+1] < s.
4) Пусть g(n) = f(n, s + 1). Тогда, начиная с ящиков с 1, 2, ..., n камнями, мы при оптимальном выборе k (за один ход) получим ящики с 1, 2, ..., g(n) камнями.
Осталось убедиться прямым вычислением, что g(g(g(g(g(460))))) = 1, а g(g(g(g(g(461))))) = 2.
Последовательность ходов для n = 460 приведена в таблице:
Если же в ящиках содержатся все наборы камней от 1 до 461, то после первого хода останутся, по крайней мере, все наборы от 1 до
g(461) = f(461, 22) = 41; после второго – все наборы от 1 до g(41) = 11; затем – от 1 до 5; от 1 до 3; и, наконец, от 1 до 2. Итак, при n = 461 не всегда можно оставить по одному камню во всех ящиках.
|
|
|
Задача 66590 |
|
|
Решение
Предположим, что для какого-то $d < p + q$ такие точки не найдутся.
Лемма. Найдутся такие целые $a$ и $b$, что $d = a p - b q$.
Доказательство леммы. Рассмотрим числа $a p - d$ при $a = 2, 3, \ldots, q + 1$. Если хотя бы одно из них делится на $q$, то есть имеет вид $b q$, то мы получаем $a p - d = b q$, что и требуется. В ином случае какие-то два их этих чисел дают одинаковый остаток от деления на $q$ (так как их всего ровно $q$ и остатка $0$ там нет). Тогда $(a_1 p - d) - (a_2 p - d) = q k$, откуда $p (a_1 - a_2) = q k$. Тогда, так как $p$ и $q$ взаимно просты, $a_1 - a_2$ кратно $q$; но в диапазоне от $2$ до $q + 1$ все числа отличаются менее чем на $q$, то есть этот случай невозможен. Лемма доказана.
Мы можем увеличить $a$ на $q$, а $b$ на $p$ – соотношение $d = a p - b q$ при этом не нарушится. Будем делать так до тех пор, пока не добьемся $a, b > 1$.
Пусть лягушка вернулась в $0$, сделав $n$ шагов вправо и $m$ шагов влево. Тогда $n p = m q$, а значит, $\frac{n}{m} = \frac{q}{p}$. Будем считать, что лягушка пропрыгивает эту последовательность $m + n$ ходов бесконечное число раз по циклу; ясно, что точки она при этом будет посещать те же.
Возьмем $k > \smash[t]{\frac{a + b}{m + n}}$. Расставим по кругу буквы, описывающие $(m + n) k$ подряд идущих ходов лягушки. Будем выписывать их по часовой стрелке, по одной букве на ход; если это ход вправо, напишем букву «П», а если ход влево – «Л». Всего мы расставили по кругу $n k$ букв «П» и $m k$ букв «Л».
Пусть мы найдем отрезок из $a + b$ подряд идущих букв, среди которых ровно $a$ раз встречается «П» (и ровно $b$ раз – «Л»). Тогда эти буквы соответствуют $a + b$ последовательным ходам, за которые лягушка сдвинулась ровно на $a p - b q = d$. Противоречие. Значит, ни на каком таком отрезке буква «П» не может встречаться $a$ раз.
Рассмотрим какой-то отрезок из $a + b$ подряд идущих букв. Пусть буква «П» встречается на нем не более чем $a - 1$ раз. Посмотрим на отрезок из $a + b$ букв, отличающийся от предыдущего сдвигом на $1$ по часовой стрелке, то есть получившийся выкидыванием одной буквы и добавлением другой. Заметим, что на новом отрезке буква «П» встречается не более чем $a - 1 + 1 = a$ раз, а так как ровно $a$ быть не может, то тоже не более чем $a - 1$ раз. Повторив эти рассуждения, получим, что на любом отрезке такой длины буква «П» встречается не более чем $a - 1$ раз. Мы можем рассмотреть среднее количество букв «П» во всех наборах $a+b$ подряд идущих букв и сделать вывод, что доля букв «П» во всем круге не более $\frac{a - 1}{a + b}$. Значит, отношение количества букв «П» к количеству букв «Л» во всем круге не превосходит $\frac{a - 1}{b + 1}$.
Аналогично, если на каком-то отрезке из $a + b$ подряд идущих букв буква «П» встречается не менее чем $a + 1$ раз, то отношение количества букв «П» во всем круге к количеству букв «Л» не менее $\frac{a + 1}{b - 1}$. Следовательно, $$\text{либо}\quad \frac{n k}{m k} \leq \frac{a - 1}{b + 1}, \quad\text{либо}\quad \frac{n k}{m k} \geq \frac{a + 1}{b - 1}.$$ При этом $\frac{nk}{mk} = \frac{n}{m} = \frac{q}{p}$. Чтобы прийти к противоречию, нам достаточно показать, что $$\frac{a - 1}{b + 1} < \frac{q}{p} < \frac{a + 1}{b - 1}.$$ Левое неравенство эквивалентно $(a - 1) p < (b + 1) q$, что следует из $a p - b q = d < p + q$. Правое неравенство аналогично эквивалентно $(a + 1) p > (b - 1) q$, что следует из $a p - b q = d > - p - q$.
Мы пришли к противоречию, значит, точки на расстоянии $d$ найдутся.
|
|
|
Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 188]
