Олимпиадные задачи из источника «параграф 2. Алгоритм Евклида» для 11 класса - сложность 3 с решениями

Отметим на прямой красным цветом все точки вида  81<i>x</i> + 100<i>y</i>,  где <i>x, y</i> – натуральные, и синим цветом – остальные целые точки.

Найдите на прямой такую точку, что любые симметричные относительно неё целые точки окрашены в разные цвета.

Пусть натуральные числа $a$ и $b$ взаимно просты. Докажите, что для того, чтобы уравнение  $ax + by = c$  имело ровно $n$ целых положительных решений, значение $c$ должно находиться в пределах  $(n - 1) \cdot ab + a + b \leqslant c \leqslant (n + 1) \cdot ab.$

Пусть <i>a</i> и <i>b</i> – натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами  (<i>x, y</i>),  лежащие в полосе  0 ≤ <i>x ≤ b</i> – 1.  Каждой такой точке припишем целое число  <i>N</i>(<i>x, y</i>) = <i>ax + by</i>.

  а) Докажите, что для каждого натурального <i>c</i> существует ровно одна точка  (<i>x, y</i>)  (0 ≤ <i>x ≤ b</i> – 1),  для которой  <i>N</i>(<i>x, y</i>) = <i>c</i>.

  б) <b>Теорема Сильвестра</b>. Докажите, что наибольшее <i>c</i>, для которого уравнение  <i>ax + by = c</i>  не имеет решений в целых неотрицательных числах, имеет вид

<i>c...

В каких пределах должно заключаться <i>c</i>, чтобы уравнение  19<i>x</i> + 14<i>y = c</i>  имело шесть натуральных решений?

Найдите наименьшее <i>c</i>, при котором

  а) уравнение  7<i>x</i> + 9<i>y = c</i>  имело бы ровно шесть натуральных решений;

  б) уравнение  14<i>x</i> + 11<i>y = c</i>  имело бы ровно пять натуральных решений.

На доске написано <i>n</i> натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.

  а) Докажите, что можно провести только конечное число операций.

  б) Финальный результат независимо от порядка действий будет одним и тем же. Например:

    (4, 6, 9) → (2, 12, 9) → (2, 3, 36) → (1, 6, 36),

    (4, 6, 9) → (4, 3, 18) → (1, 12, 18) → (1, 6, 36).