Фильтр
Задачи
Задача 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 |
|
|
Решение
Пусть в момент времени $k$ лягушка находится в точке $a_k$, $a_0 = a_N = 0$. Продолжим последовательность $(a_i)$ периодически по правилу $a_{i+N} = a_i$. Обозначим $A = p+q$. Заметим, что $-q \equiv p \bmod A$, поэтому $a_n \equiv n p \bmod A$ для любого $n$.
Так как $p$ и $q$ взаимно простые, то $p$ и $A$ взаимно простые. Докажем, что найдется такое целое $s$, что $sp \equiv d \bmod A$.
В самом деле, числа $0, p, 2p, \dots, (A-1)p$ дают различные остатки при делении на $A$ (иначе для некоторых $ 0 \leq i < j < A $ получаем, что $(j-i)p \equiv 0 \bmod A$, чего не может быть, так как $j - i$ не делится на $A$, а $p$ взаимно просто с $A$). А значит, среди этих остатков есть и $d$.
Обозначим $r_k = a_{s+k} - a_k$. Легко видеть, что все $r_k$ дают остаток $d$ от деления на $A$.
Если $a_k$ – самая левая из точек, посещенных лягушкой, то $r_k > 0$. Если $a_k$ – самая правая точка, то $r_k < 0$. Значит, при некотором $i$ в последовательности $r_i$ происходит перемена знака, $r_i < 0$ и $r_{i+1} > 0$. Тогда $r_{i+1} < A$, потому что $$r_{i+1} - r_i = (a_{i+s+1} - a_{i+s}) - (a_{i+1} - a_i) \leqslant p - (-q) = A.$$ А так как $r_{i+1} \equiv d \bmod A$, то $r_{i+1} = d$, что и требовалось.
|
|
|
Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 188]
