Фильтр
Задачи
Задача 98057 |
|
|
Хозяйка испекла для гостей пирог. За столом может оказаться либо p человек, либо q (p и q взаимно просты). На какое минимальное количество кусков (не обязательно равных) нужно заранее разрезать пирог, чтобы в любом случае его можно было раздать поровну?
Решение
Считая пирог длинным прямоугольником, разобьём его на p равных кусков (p – 1 разрез) и на q равных кусков (q – 1 разрез). Так как разрезов p + q – 2, то кусков p + q – 1.
Рассмотрим произвольное разбиение пирога объёма pq. Пусть гости – вершины графа (всего p + q вершин). По каждому куску строим ребро, соединяющее двух гостей, которым достаётся этот кусок при первой и второй раздаче. Рассмотрим одну из компонент связности. Сумма "объёмов" её рёбер должна быть кратна как p, так и q, значит, она равна pq. Следовательно, граф связен, а поэтому число его рёбер не меньше p + q – 1 (см.задачу 31098 а, б).
Ответ
На p + q – 1 кусок.
|
|
Задача 109724 |
|
|
Таня задумала натуральное число X ≤ 100, а Саша пытается его угадать. Он выбирает пару натуральных чисел M и N, меньших 100, и задаёт вопрос: "Чему равен наибольший общий делитель X + M и N?" Докажите, что Саша может угадать Танино число, задав семь таких вопросов.
Решение
Узнав НОД(X + 1, 2), Саша определит чётность X. Если X оказалось чётным, то второй вопрос будет о НОД(X + 2, 4), а если нечётным, то о
НОД(X + 1, 4). В результате Саша узнает остаток от деления X на 4.
Пусть, задав k ≤ 5 вопросов, Саша определил остаток rk от деления X на 2k. Тогда (k+1)-м вопросом он узнаёт НОД(X + 2k – rk, 2k+1) (заметим, что
0 < 2k – rk ≤ 2k+1 ≤ 64 < 100. Если НОД(X + 2k – rk, 2k+1) = 2k+1, то X ≡ 2k + rk (mod 2k+1), а если НОД(X + 2k – rk, 2k+1) = 2k, то X ≡ rk (mod 2k+1).
Итак, задав шесть вопросов, Саша узнает остаток от деления X на 64.
Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более двух. Если их все же два – a и a + 64, – то Саша узнаёт
НОД(X + 3 – r, 3), где r – остаток от деления a на 3. Если X = a, то этот НОД равен 3, а если X = a + 64, то 1. Итак, седьмым вопросом число X определится однозначно.
|
|
|
Задача 109854 |
|
|
Пусть a1, a2, ..., a10 – натуральные числа, a1 < a2 < ... < a10. Пусть bk – наибольший делитель ak, меньший ak. Оказалось, что b1 > b2 > ... > b10.
Докажите, что a10 > 500.
Решение
Заметим, что bk = ak/ck , где ck – наименьший простой делитель ak. Из неравенств ai < ai+1, bi > bi+1 следует, что ci < ci+1, то есть c1 < c2 < ... < c10. Значит, c9 ≥ 23, так как 23 – девятое по счёту простое число.
Так как b9 > b10, то b9 > 1 и b9 ≥ c9. Отсюда
|
|
|
Задача 109651 |
|
|
Найдите все такие тройки натуральных чисел m, n и l, что m + n = (НОД(m, n))², m + l = (НОД(m, l))², n + l = (НОД(n, l))².
Решение
Положим d = НОД(m, n, l). Пусть m = dm1, n = dn1, l = dl1. Тогда где dmn = НОД(m1, n1); откуда
Складывая это равенство с двумя аналогичными, получаем
Покажем, что d взаимно просто с суммой m1 + n1 + l1. В самом деле, если у d и этой суммы есть общий делитель δ > 1, то он будет общим делителем всех чисел m1, n1 и l1 (так как сумма любых двух из них делится на d).
Но тогда dδ – общий делитель чисел m, n и l, что противоречит определению числа d.
Следовательно, d является делителем числа 2.
Заметим, что числа dmn, dnl, dml попарно взаимно просты (иначе у чисел m1, n1, l1 нашелся бы общий делитель, не равный 1). Поэтому m1 = dmndmlm2,
n1 = dmndnln2, l1 = dnldmll2, где m2, n2, l2 – натуральные числа. В таких обозначениях первое из исходных уравнений приобретает вид dmlm2 + dnln2 = ddmn.
Не умаляя общности, мы можем считать, что число dmn – наименьшее из чисел dmn, dml и dnl. Имеем: dmlm2 + dnln2 ≥ dml + dnl ≥ 2dmn ≥ ddmn (так как
d ≤ 2). Итак, все неравенства являются на самом деле равенствами, откуда m2 = n2 = 1, d = 2 и dml = dmn = dnl. Но числа dml, dmn, dnl попарно взаимно просты,
следовательно, они равны 1, и мы нашли единственное решение m = n = l = 2.
Ответ
(2, 2, 2).
|
|
|
Задача 109730 |
|
|
По окружности расставлено 100 натуральных чисел, взаимно простых в совокупности. Разрешается прибавлять к любому числу наибольший общий делитель его соседей. Докажите, что при помощи таких операций можно сделать все числа попарно взаимно простыми.
Решение
Положим для удобства an+100 = an при n = 1, 2, ..., 100. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть a1, a2, ...,
an и d – натуральные числа. Тогда существует такое натуральное k, что НОД(a1 + kd, ai) ≤ d для любого i = 2, 3, ..., n.
Доказательство. Существует некоторое число, кратное a2a3...an, скажем,
la2a3...an, которое больше a1. Тогда среди тех k, для которых a1 + kd > la2a3... an, существует наименьшее число k0.
Положим b = a1 + k0d.
Тогда 0 < b – la2a3... an ≤ d, и НОД(b, ai) ≤ d.
Пусть теперь M > 1 – наибольший из попарных общих делителей чисел ai. Докажем, что с помощью операций, описанных в условии, мы сможем заменить исходный набор чисел на набор, в котором все попарные общие делители меньше M. Действительно, так
как числа a1, a2, ..., a100 взаимно просты в совокупности, найдутся два соседних числа ai и ai+1, первое из которых делится
на M, а второе – нет. Тогда d = НОД(ai–1, ai+1) < M. Применяя лемму, прибавим к ai такое кратное d, чтобы наибольшие общие делители bi с каждым из остальных чисел стали не больше d. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят M, а чисел, кратных M, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьёмся, что останется ровно одно число, кратное M, и тогда, очевидно, все попарные наибольшие общие делители станут меньше M.
Итак, если наибольший из попарных общих делителей чисел набора больше 1,
его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось.
|
|
|
Страница: << 20 21 22 23 24 25 26 >> [Всего задач: 274]
