Разделы 
Дополнительно
Задача по математике - 3592
2019-06-12 
Даны два взаимно простых числа $p > 0$ и $q > 0$. Целое число $n$ называется хорошим, если его можно представить в виде $n = px + qy$, где $x$ и $у$ - целые неотрицательные числа, и плохим - в противном случае, а) Докажите, что существует такое целое число $с$, что из двух целых чисел $n$ и $c - n$ всегда одно хорошее, а другое - плохое, б) Сколько всего плохих неотрицательных чисел?
Решение:
Если $p$ и $q$ - взаимно простые натуральные числа, то каждое целое число $z$ представляется в виде $z = px + qy$. Всякое такое представление получается из некоторого фиксированного $z = pa + qb$ по общей формуле $z = p(a - qt) + q(b + pt)$, где $t$ - целое, причем существует единственное представление, для которого $0 \leq x \leq q - 1$.
Каждому целому числу $z$ мы сопоставили пару $(x, у)$ целых чисел такую, что $0 \leq x \leq q - 1, z = px + qy$. Разным числам при этом соответствуют разные пары, причем $z$ будет хорошим только при $у \geq 0$. (Если $z = px + qy$ - хорошее число, то при $x = qt + r \geq 0$, $0 \leq r \leq q - 1$, имеется представление $z = pr + q(y + t)$.)
Теперь заметим, что если число $z = px + qy$, $0 \leq x \leq q - 1$ - хорошее, то число $z^{ \prime} = (q - 1 - x)p + (-1 - y)q$ плохое и, наоборот, если $z$ - плохое, то $z^{ \prime}$ - хорошее. Точки $(x, y)$ и $(q - 1 - x, -1 - у)$ симметричны относительно точки $(x_0, y_0) = \left ( \frac{q-1}{2}, - \frac{1}{2} \right )$, а сами числа $z$ и $z^{ \prime}$ симметричны относительно точки $z_0 = px_0 + qy_0 = \frac{pq - p - q}{2}$, поскольку $z + z^{ \prime} = pq - p - q = 2z_0 = c$.
Тем самым доказано а): хорошему числу z соответствует плохое (симметричное ему) $c - z = z^{ \prime}$ и наоборот.
Поскольку наименьшее хорошее число 0, то наибольшим плохим будет $c$, а всего плохих чисел будет $\frac{c+1}{2} = \frac{(p-1)(q-1)}{2}$.
Очень полезно, разбирая решение этой задачи, опираться на геометрическую иллюстрацию: пары $(x, y)$ - точки плоской решетки, $px + qy = z$ - проходящие через них прямые и т. д.
Ответ: б) $\frac{(p - 1) (q - 1)}{2}$.
Даны два взаимно простых числа $p > 0$ и $q > 0$. Целое число $n$ называется хорошим, если его можно представить в виде $n = px + qy$, где $x$ и $у$ - целые неотрицательные числа, и плохим - в противном случае, а) Докажите, что существует такое целое число $с$, что из двух целых чисел $n$ и $c - n$ всегда одно хорошее, а другое - плохое, б) Сколько всего плохих неотрицательных чисел?
Решение:
Если $p$ и $q$ - взаимно простые натуральные числа, то каждое целое число $z$ представляется в виде $z = px + qy$. Всякое такое представление получается из некоторого фиксированного $z = pa + qb$ по общей формуле $z = p(a - qt) + q(b + pt)$, где $t$ - целое, причем существует единственное представление, для которого $0 \leq x \leq q - 1$.
Каждому целому числу $z$ мы сопоставили пару $(x, у)$ целых чисел такую, что $0 \leq x \leq q - 1, z = px + qy$. Разным числам при этом соответствуют разные пары, причем $z$ будет хорошим только при $у \geq 0$. (Если $z = px + qy$ - хорошее число, то при $x = qt + r \geq 0$, $0 \leq r \leq q - 1$, имеется представление $z = pr + q(y + t)$.)
Теперь заметим, что если число $z = px + qy$, $0 \leq x \leq q - 1$ - хорошее, то число $z^{ \prime} = (q - 1 - x)p + (-1 - y)q$ плохое и, наоборот, если $z$ - плохое, то $z^{ \prime}$ - хорошее. Точки $(x, y)$ и $(q - 1 - x, -1 - у)$ симметричны относительно точки $(x_0, y_0) = \left ( \frac{q-1}{2}, - \frac{1}{2} \right )$, а сами числа $z$ и $z^{ \prime}$ симметричны относительно точки $z_0 = px_0 + qy_0 = \frac{pq - p - q}{2}$, поскольку $z + z^{ \prime} = pq - p - q = 2z_0 = c$.
Тем самым доказано а): хорошему числу z соответствует плохое (симметричное ему) $c - z = z^{ \prime}$ и наоборот.
Поскольку наименьшее хорошее число 0, то наибольшим плохим будет $c$, а всего плохих чисел будет $\frac{c+1}{2} = \frac{(p-1)(q-1)}{2}$.
Очень полезно, разбирая решение этой задачи, опираться на геометрическую иллюстрацию: пары $(x, y)$ - точки плоской решетки, $px + qy = z$ - проходящие через них прямые и т. д.
Ответ: б) $\frac{(p - 1) (q - 1)}{2}$.
