Примени математику (Гашков, Сергеев) - страница 37

откуда q>1 и, значит, в этом случае сумму можно уплатить q-1 трехрублевыми купюрами и 1 пятирублевой.

6.2. Если у кассира нет ни одной пятирублевой купюры, то покупатель может заплатить за покупку стоимостью в n рублей только при условии, что число n кратно 3. Если у кассира есть 1 пятирублевая купюра, то. покупатель может заплатить за покупку только при условии, что число n либо кратно 3, либо дает остаток 1 при делении на 3 (в последнем случае покупатель платит на 5 рублей больше и получает 5 рублей сдачи: n = 3q + 1 = 3(q + 2) - 5). Наконец, если кассир имеет 2 пятирублевые купюры, то покупатель может заплатить за покупку при любом значении n (в случае, когда остаток от деления числа n на 3 равен 2, покупатель может заплатить на 10 рублей больше и получить 10 рублей сдачи:

Таким образом, в условиях задачи кассир должен иметь минимум 2 пятирублевые купюры.

6.3. Пусть (a, b) = d и число с не делится на d. Тогда если уравнение ax + by = c имеет целочисленное решение x = x_>0, y = y_>0, то справедливо числовое равенство ax_>0 + by_>0 = c, в котором левая часть делится на d (ибо числа а и b кратны d), а правая нет. Полученное противоречие доказывает, что указанное уравнение в целых числах не может иметь решений.

6.4. Если сумму в 1000 рублей можно набрать с помощью х, y и z купюр достоинством в 1 рубль, 10 рублей и 100 рублей соответственно, то справедливо равенство x + 10y + 100z = 1000. Если к тому же всего купюр должно быть x + y + z = 40, то целые числа x и y должны удовлетворять уравнению (40 - y - z) + 10y + 100z = 1000, или 9y + 99z = 960. Согласно утверждению задачи 6.3, последнее уравнение в целых числах не имеет решений, так как число 960 не делится на наибольший общий делитель пары чисел 9 и 99, равный 9.

6.5. Задача сводится к решению уравнения

в целых неотрицательных числах. Заметим, что число y не может быть равным 0, так как иначе уравнение

в целых числах имело бы решение, что противоречило бы утверждению задачи 6.3 (ибо число 140 не делится на число (16, 40)=8). Далее, число х также не может быть равным 0, так как иначе было бы выполнено равенство 17y = 140 - 40z = 10(14 - 4z) и неотрицательное число 14 - 4z делилось бы на 17 при целом неотрицательном значении z, что невозможно. Наконец, число z также не может быть равным 0, так как иначе из равенства 17y = 140 - 16x = 4(35 - 4x) следовало бы, что число 35 - 4x кратно 17 при x>0, что невозможно.

Таким образом, числа x, y, z должны быть положительными, а числа х' = х - 1, y' = y - 1, z' = z - 1 - целыми неотрицательными, удовлетворяющими уравнению