|
|
 |
Условие
Даны два взаимно простых натуральных числа a и b. Рассмотрим множество M целых чисел, представимых в виде ax + by, где x и y – целые неотрицательные числа.
а) Каково наибольшее целое число c, не принадлежащее множеству М?
б) Докажите, что из двух чисел n и с – n (где n – любое целое) одно принадлежит М, а другое нет.
Решение
Cформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел (x, y) будем называть "целой точкой" и изображать красной точкой, если обе её координаты неотрицательны, и синей точкой – если хотя бы одна координата отрицательна. Для каждого целого n уравнение ax + by = n определяет прямую ln. Все прямые ln параллельны друг другу. Пусть n – целое. Будем считать прямую ln красной, если она проходит хотя бы через одну красную точку, и синей – в противном случае.
Каждая прямая ln проходит ровно через целую одну точку полосы 0 ≤ x ≤ b – 1 (см. задачу 60525 а, при b = 1 полоса вырождается в прямую). При этом очевидно, что если прямая красная, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симметрии относительно точки (b–1/2, ½) (эта симметрия задаётся формулой (x, y) → (b – 1 – x, –1 – y)) указанная полоса переходит в себя, причём красные точки переходят в синие, и наоборот. Прямую ln эта симметрия переводит в прямую lab–a–b–n :
если ax + by = n, то ax' + by' = a(b – 1 – x) + b(–1 – y) = ab – a – b – n. Ясно, что самая нижняя красная прямая – это l0. Следовательно, самая верхняя синяя прямая – это lab–a–b. Итак, наибольшее число, не принадлежащее множеству M, – это c = ab – a – b, и из двух чисел n и c – n одно принадлежит M, а другое – нет.
Ответ
а) c = ab – a – b.
Замечания
1. См. также решение задачи 60525 б.
2. Ср. с задачей 60527.
