Страница: << 20 21 22 23 24 25 26 >> [Всего задач: 275]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 64717

Темы:   [ НОД и НОК. Взаимная простота ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Делимость чисел. Общие свойства ] [ Индукция (прочее) ]

Сложность: 4+ Классы: 9,10

Радикалом натурального числа N (обозначается rad(N)) называется произведение всех простых делителей числа N, взятых по одному разу. Например,
rad(120) = 2·3·5 = 30.  Существует ли такая тройка попарно взаимно простых натуральных чисел A, B, C, что  A + B = C  и  C > 1000 rad(ABC)?

Решение

  Будем искать пример в виде  C = 10ⁿ,  B = 1,  A = 10ⁿ – 1.
  Индукцией по k докажем, что для любого натурального k существует такое натуральное n, что  10ⁿ – 1  кратно 3^k+1.
  База:  10¹ – 1 кратно 3².
  Шаг индукции. Если  10ⁿ – 1  кратно 3^k+1, то  10³ⁿ – 1 = (10ⁿ – 1)(10²ⁿ + 10ⁿ + 1)  кратно 3^k+2, так как  10²ⁿ + 10ⁿ + 1  делится на 3.
  Возьмём теперь такое k, что  3^k > 10000,  и такое n, что  10ⁿ – 1  кратно 3^k+1. Тогда

Ответ

Существует.

Прислать комментарий

---

Задача 98057

Темы:   [ НОД и НОК. Взаимная простота ] [ Связность и разложение на связные компоненты ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4+ Классы: 7,8,9,10

Хозяйка испекла для гостей пирог. За столом может оказаться либо 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

Темы:   [ НОД и НОК. Взаимная простота ] [ Математическая логика (прочее) ] [ Деление с остатком ]

Сложность: 4+ Классы: 8,9,10

Таня задумала натуральное число  X ≤ 100,  а Саша пытается его угадать. Он выбирает пару натуральных чисел M и N, меньших 100, и задаёт вопрос: "Чему равен наибольший общий делитель  X + M  и N?" Докажите, что Саша может угадать Танино число, задав семь таких вопросов.

Решение

  Узнав  НОД(X + 1, 2),  Саша определит чётность X. Если X оказалось чётным, то второй вопрос будет о  НОД(X + 2, 4),  а если нечётным, то о
НОД(X + 1, 4).  В результате Саша узнает остаток от деления X на 4.
  Пусть, задав  k ≤ 5  вопросов, Саша определил остаток r_k от деления X на 2^k.  Тогда (k+1)-м вопросом он узнаёт  НОД(X + 2^k – r_k, 2^k+1)  (заметим, что
0 < 2^k – r_k ≤ 2^k+1 ≤ 64 < 100.  Если  НОД(X + 2^k – r_k, 2^k+1) = 2^k+1,  то  X ≡ 2^k + r_k (mod 2^k+1),  а если  НОД(X + 2^k – r_k, 2^k+1) = 2^k,  то  X ≡ r_k (mod 2^k+1).
  Итак, задав шесть вопросов, Саша узнает остаток от деления X на 64.
  Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более двух. Если их все же два – a и  a + 64,  – то Саша узнаёт
НОД(X + 3 – r, 3),  где r – остаток от деления a на 3. Если  X = a,  то этот НОД равен 3, а если  X = a + 64,  то 1. Итак, седьмым вопросом число X определится однозначно.

Прислать комментарий

---

Задача 109854

Темы:   [ НОД и НОК. Взаимная простота ] [ Упорядочивание по возрастанию (убыванию) ] [ Простые числа и их свойства ]

Сложность: 4+ Классы: 8,9,10

Пусть a₁, a₂, ..., a₁₀ – натуральные числа,  a₁ < a₂ < ... < a₁₀.  Пусть b_k – наибольший делитель a_k, меньший a_k. Оказалось, что b₁ > b₂ > ... > b₁₀.
Докажите, что  a₁₀ > 500.

Решение

  Заметим, что  b_k = ^a_k/_ck ,  где c_k – наименьший простой делитель a_k.  Из неравенств  a_i < a_i+1,  b_i > b_i+1  следует, что  c_i < c_i+1,  то есть  c₁ < c₂ < ... < c₁₀.  Значит,  c₉ ≥ 23,  так как 23 – девятое по счёту простое число.
  Так как  b₉ > b₁₀,  то  b₉ > 1  и  b₉ ≥ c₉.  Отсюда  

Прислать комментарий

---

Задача 109651

Тема:   [ НОД и НОК. Взаимная простота ]

Сложность: 5- Классы: 8,9,10

Найдите все такие тройки натуральных чисел m, n и l, что  m + n = (НОД(m, n))²,  m + l = (НОД(m, l))²,  n + l = (НОД(n, l))².

Решение

  Положим  d = НОД(m, n, l).  Пусть  m = dm₁,  n = dn₁,  l = dl₁.  Тогда    где  d_mn = НОД(m₁, n₁);  откуда    Складывая это равенство с двумя аналогичными, получаем  
  Покажем, что d взаимно просто с суммой  m₁ + n₁ + l₁.  В самом деле, если у d и этой суммы есть общий делитель  δ > 1,  то он будет общим делителем всех чисел m₁, n₁ и l₁ (так как сумма любых двух из них делится на d). Но тогда dδ – общий делитель чисел m, n и l, что противоречит определению числа d.
  Следовательно, d является делителем числа 2.
  Заметим, что числа d_mn, d_nl, d_ml попарно взаимно просты (иначе у чисел m₁, n₁, l₁ нашелся бы общий делитель, не равный 1). Поэтому  m₁ = d_mnd_mlm₂,
n₁ = d_mnd_nln₂, l₁ = d_nld_mll₂,  где m₂, n₂, l₂ – натуральные числа. В таких обозначениях первое из исходных уравнений приобретает вид  d_mlm₂ + d_nln₂ = dd_mn.
  Не умаляя общности, мы можем считать, что число d_mn – наименьшее из чисел d_mn, d_ml и d_nl.  Имеем:  d_mlm₂ + d_nln₂ ≥ d_ml + d_nl ≥ 2d_mn ≥ dd_mn  (так как
d ≤ 2).  Итак, все неравенства являются на самом деле равенствами, откуда  m₂ = n₂ = 1,  d = 2  и  d_ml = d_mn = d_nl.  Но числа d_ml, d_mn, d_nl попарно взаимно просты, следовательно, они равны 1, и мы нашли единственное решение  m = n = l = 2.

Ответ

(2, 2, 2).

Прислать комментарий

---

Страница: << 20 21 22 23 24 25 26 >> [Всего задач: 275]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями