Разделы 
Дополнительно
Задача по математике - 2910
2019-05-06 
Пусть $p$ и $q$ - два взаимно простых натуральных числа. Натуральное число $n$ условимся называть «хорошим», если его можно представить в виде $px + qy$, где $x$ и $у$ - целые неотрицательные числа, и «плохим» в противном случае.
а) Доказать, что существует такое число $A$, что если сумма двух целых чисел равна $A$, то обязательно одно из них «хорошее», а второе - «плохое».
б) Если числа $p$ и $q$ заданы, то как найти число всевозможных «плохих» натуральных чисел?
Решение:
Из того, что $p$ и $q$ - взаимно просты, с помощью алгоритма Евклида устанавливается, что любое целое число $n$ можно представить в виде:
$n = px + qy$, где $p$ и $у$ - целые числа. (*)
В самом деле, пусть $p > q$; тогда $p = qd + r$, где $0 < r < q$, т. е.
$r = p \cdot 1 + q (-d) (= px_1 + qy_1)$
(здесь $d$ - частное, а $r$ - остаток от деления $р$ на $q$). Далее, имеем $q = rd_1 + r_1$, где $0 < r_1 < r$ (число $r_1$ - остаток от деления $q$ на $r$); объединяя эти два равенства, получаем представление $r_1$, в виде (*):
$r_1 = q - rd_1 = q - (px_1 + qy_1)d_1 = p (-x_1d_1) + q(1 - y_1d_1) = px_2 + qy_2$,
где $x_2 (= - x_1d_1 = - d_1)$ и $y_2 (= 1 - y_1d_1 = 1 + dd_1)$ - целые числа. Затем, полагая $r = r_1d_2 + r_2$, где $0 < r_2 < r_1$, и пользуясь предшествующим равенством, мы точно так же можем представить $r_2$ в виде комбинации $px_3 + qy_3$ чисел $p$ и $q$, и т. д. - вплоть до общего наибольшего делителя 1 чисел $p$ и $q$. (Легко видеть, что последний отличный от нуля остаток будет общим наибольшим делителем чисел $p$ к $q$ - в рассматриваемом случае он равен 1.) Но если единицу можно записать в виде $1 = px_k + qy_k$, где $x_k, y_k$ - целые числа, то и любое число $n = n \cdot 1 = n (px_k + qy_k) = p (nx_k) + q (ny_k)$ можно записать в виде (*).
Далее, из того, что $p$ и $q$ взаимно просты, вытекает, что если $n$ представляется в виде (*) двумя разными способами:
$n = px + qy = px^{ \prime} + qy^{ \prime}$, где $x, у; x^{ \prime}, у^{ \prime}$ - целые, (**)
то $x - x^{ \prime}$ кратно $q$ и $y - y^{ \prime}$ кратно $p$: в самом деле, из (**), например, следует что $p(x - x^{ \prime}) = - q (y - y^{ \prime})$, или $x - x^{ \prime} = - q \frac {y - y^{ \prime}}{p}$, и так как $p$ и $q$ не имеют общих простых делителей, то $x - x^{ \prime}$ делится на $q$. Последнее утверждение можно сформулировать как утверждение об «единственности» представления (*): каждое целое число $n$ можно - и притом единственным образом - записать в виде (*), где $0 \leq x < q$ в самом деле, число $x$ в формуле (*) всегда можно представить в виде $x = kq + x_0$, где $0 \leq x_0 < q$ ($x_0$ есть остаток от деления $x$ на $q$); при этом
$n = px + qy = p(kq + x_0) + qy = px_0 + q (pk + y) = px_0 + qy_0$, где $0 \leq x_0 < q$ и $x_0, y_0$ - целые (***),
С другой стороны, два разных представления (***) (т. е. равенство (**), $0 \leq x < q$ и $0 \leq x^{ \prime} < q$) невозможны, ибо при этом $|x - x^{ \prime} | < q$ и разность $x - x^{ \prime}$ не делится на $q$. Число $n$, очевидно, будет «хорошим», если $у_0$ в формуле (***) неотрицательно, и «плохим», если $у_0$ отрицательно: ведь если $n = px_0 + qy_0$, где $0 \leq x_0 < q$ и $y_0 < 0$, то, заменив $x_0$ на $x = x_0 - \lambda q$ и $у_0$ на $y = x_0 + \lambda p$, где $\lambda$ - целое, мы никогда не придем к представлению (*) числа $n$, в котором $x$ и $у$ оба неотрицательны.
Эти замечания позволяют без труда решить задачу.
а) Очевидно, наименьшим «хорошим» числом является число $0 = 0 \cdot p + 0 \cdot q$; наибольшим «плохим» числом, в силу сказанного выше, является число вида (***), где $x_0$ - наибольшее из «допустимых» (положительных) чисел, т. е. $x_0 = q - 1$, а $у_0$ - наименьшее из отрицательных чисел, т. е. $y_0 = - 1$; таким образом, наибольшее «плохое» число $P = p(q-1) + q(-1) = pq - p - q$. При этом естественно считать, что эти два числа $0$ и $P$ как раз и «дополняют» друг друга до фигурирующего в условии задачи числа $A$, т. е. что за число $A$ следует принять $P = pq - p - q$. И действительно, если число $n$ имеет вид (***), то число
$n^{ \prime} = A - n = (pq - p - q) - (px_0 + qy_0) = p(q - 1 - x_0) + q (-1-y_0)$
имеет тот же вид (***), где только роль $x_0$ играет число $x_0^{ \prime} = q - 1 - x_0$, а роль $у_0^{ \prime}$ - число $y_0^{ \prime} = -1 - y_0$. Но если $0 \leq x_0 \leq q - 1$, то и $0 \leq x_0^{ \prime} \leq q - 1$ и из чисел $у_0$ и $у_0^{ \prime}$ одно положительно, а другое отрицательно; это и доказывает утверждение задачи.
б) Первое решение. Из результата задачи а) непосредственно следует, что среди чисел $n$, где $0 \leq n \leq P = pq - p - q$ ($P$- это наибольшее «плохое» число), ровно половина будет «плохими», а остальные - «хорошими»; так как при этом мы учтем все натуральные «плохие» числа, то интересующее нас количество $t$ таких чисел
$t = \frac{P+1}{2} = \frac {pq - p - q + 1}{2} = \frac{(p-1)(q-1)}{2}$.
Второе решение. «Плохими» числа $n$, которые представимы в виде (***), где $0 \leq x_0 < q, y_0^{ \prime} < 0$ и $px_0 + qy_0 > 0$ (ибо число $n$ положительно). На плоскости с координатами $x_0, у_0$ линии $x_0 = q$, $y_0 = 0$, $px_0 + qy_0 = 0$ выделяют заштрихованный на рис. треугольник; нам надо найти число «целых точек» в этом треугольнике. Но ясно, что это число ровно вдвое меньше числа «целых точек» в прямоугольнике $OABC$ (на диагонали прямоугольника «целых точек» нет, ибо $p$ и $q$ взаимно просты). Так как число «целых точек» внутри прямоугольника, очевидно, равно $(p-1) \cdot (q-1)$, то мы приходим к тому же значению искомого числа $t$, что и выше.
Пусть $p$ и $q$ - два взаимно простых натуральных числа. Натуральное число $n$ условимся называть «хорошим», если его можно представить в виде $px + qy$, где $x$ и $у$ - целые неотрицательные числа, и «плохим» в противном случае.
а) Доказать, что существует такое число $A$, что если сумма двух целых чисел равна $A$, то обязательно одно из них «хорошее», а второе - «плохое».
б) Если числа $p$ и $q$ заданы, то как найти число всевозможных «плохих» натуральных чисел?
Решение:
Из того, что $p$ и $q$ - взаимно просты, с помощью алгоритма Евклида устанавливается, что любое целое число $n$ можно представить в виде:
$n = px + qy$, где $p$ и $у$ - целые числа. (*)
В самом деле, пусть $p > q$; тогда $p = qd + r$, где $0 < r < q$, т. е.
$r = p \cdot 1 + q (-d) (= px_1 + qy_1)$
(здесь $d$ - частное, а $r$ - остаток от деления $р$ на $q$). Далее, имеем $q = rd_1 + r_1$, где $0 < r_1 < r$ (число $r_1$ - остаток от деления $q$ на $r$); объединяя эти два равенства, получаем представление $r_1$, в виде (*):
$r_1 = q - rd_1 = q - (px_1 + qy_1)d_1 = p (-x_1d_1) + q(1 - y_1d_1) = px_2 + qy_2$,
где $x_2 (= - x_1d_1 = - d_1)$ и $y_2 (= 1 - y_1d_1 = 1 + dd_1)$ - целые числа. Затем, полагая $r = r_1d_2 + r_2$, где $0 < r_2 < r_1$, и пользуясь предшествующим равенством, мы точно так же можем представить $r_2$ в виде комбинации $px_3 + qy_3$ чисел $p$ и $q$, и т. д. - вплоть до общего наибольшего делителя 1 чисел $p$ и $q$. (Легко видеть, что последний отличный от нуля остаток будет общим наибольшим делителем чисел $p$ к $q$ - в рассматриваемом случае он равен 1.) Но если единицу можно записать в виде $1 = px_k + qy_k$, где $x_k, y_k$ - целые числа, то и любое число $n = n \cdot 1 = n (px_k + qy_k) = p (nx_k) + q (ny_k)$ можно записать в виде (*).
Далее, из того, что $p$ и $q$ взаимно просты, вытекает, что если $n$ представляется в виде (*) двумя разными способами:
$n = px + qy = px^{ \prime} + qy^{ \prime}$, где $x, у; x^{ \prime}, у^{ \prime}$ - целые, (**)
то $x - x^{ \prime}$ кратно $q$ и $y - y^{ \prime}$ кратно $p$: в самом деле, из (**), например, следует что $p(x - x^{ \prime}) = - q (y - y^{ \prime})$, или $x - x^{ \prime} = - q \frac {y - y^{ \prime}}{p}$, и так как $p$ и $q$ не имеют общих простых делителей, то $x - x^{ \prime}$ делится на $q$. Последнее утверждение можно сформулировать как утверждение об «единственности» представления (*): каждое целое число $n$ можно - и притом единственным образом - записать в виде (*), где $0 \leq x < q$ в самом деле, число $x$ в формуле (*) всегда можно представить в виде $x = kq + x_0$, где $0 \leq x_0 < q$ ($x_0$ есть остаток от деления $x$ на $q$); при этом
$n = px + qy = p(kq + x_0) + qy = px_0 + q (pk + y) = px_0 + qy_0$, где $0 \leq x_0 < q$ и $x_0, y_0$ - целые (***),
С другой стороны, два разных представления (***) (т. е. равенство (**), $0 \leq x < q$ и $0 \leq x^{ \prime} < q$) невозможны, ибо при этом $|x - x^{ \prime} | < q$ и разность $x - x^{ \prime}$ не делится на $q$. Число $n$, очевидно, будет «хорошим», если $у_0$ в формуле (***) неотрицательно, и «плохим», если $у_0$ отрицательно: ведь если $n = px_0 + qy_0$, где $0 \leq x_0 < q$ и $y_0 < 0$, то, заменив $x_0$ на $x = x_0 - \lambda q$ и $у_0$ на $y = x_0 + \lambda p$, где $\lambda$ - целое, мы никогда не придем к представлению (*) числа $n$, в котором $x$ и $у$ оба неотрицательны.
Эти замечания позволяют без труда решить задачу.
а) Очевидно, наименьшим «хорошим» числом является число $0 = 0 \cdot p + 0 \cdot q$; наибольшим «плохим» числом, в силу сказанного выше, является число вида (***), где $x_0$ - наибольшее из «допустимых» (положительных) чисел, т. е. $x_0 = q - 1$, а $у_0$ - наименьшее из отрицательных чисел, т. е. $y_0 = - 1$; таким образом, наибольшее «плохое» число $P = p(q-1) + q(-1) = pq - p - q$. При этом естественно считать, что эти два числа $0$ и $P$ как раз и «дополняют» друг друга до фигурирующего в условии задачи числа $A$, т. е. что за число $A$ следует принять $P = pq - p - q$. И действительно, если число $n$ имеет вид (***), то число
$n^{ \prime} = A - n = (pq - p - q) - (px_0 + qy_0) = p(q - 1 - x_0) + q (-1-y_0)$
имеет тот же вид (***), где только роль $x_0$ играет число $x_0^{ \prime} = q - 1 - x_0$, а роль $у_0^{ \prime}$ - число $y_0^{ \prime} = -1 - y_0$. Но если $0 \leq x_0 \leq q - 1$, то и $0 \leq x_0^{ \prime} \leq q - 1$ и из чисел $у_0$ и $у_0^{ \prime}$ одно положительно, а другое отрицательно; это и доказывает утверждение задачи.
б) Первое решение. Из результата задачи а) непосредственно следует, что среди чисел $n$, где $0 \leq n \leq P = pq - p - q$ ($P$- это наибольшее «плохое» число), ровно половина будет «плохими», а остальные - «хорошими»; так как при этом мы учтем все натуральные «плохие» числа, то интересующее нас количество $t$ таких чисел
$t = \frac{P+1}{2} = \frac {pq - p - q + 1}{2} = \frac{(p-1)(q-1)}{2}$.
Второе решение. «Плохими» числа $n$, которые представимы в виде (***), где $0 \leq x_0 < q, y_0^{ \prime} < 0$ и $px_0 + qy_0 > 0$ (ибо число $n$ положительно). На плоскости с координатами $x_0, у_0$ линии $x_0 = q$, $y_0 = 0$, $px_0 + qy_0 = 0$ выделяют заштрихованный на рис. треугольник; нам надо найти число «целых точек» в этом треугольнике. Но ясно, что это число ровно вдвое меньше числа «целых точек» в прямоугольнике $OABC$ (на диагонали прямоугольника «целых точек» нет, ибо $p$ и $q$ взаимно просты). Так как число «целых точек» внутри прямоугольника, очевидно, равно $(p-1) \cdot (q-1)$, то мы приходим к тому же значению искомого числа $t$, что и выше.
