Question

Ребят, помогите с заданием. Даю 50 баллов.

Проезд в Москве по карте "Тройка" в 2016 году стоит 32 рубля за одну поездку на метро и 31 рубль за одну поездку на наземном транспорте. Какое наименьшее суммарное число поездок можно совершить по этим тарифам, потратив ровно 5000 рублей?

Answer 1

Сведём данную задачу к уравнению с 2 неизвестными (Диофантово уравнение). При этом нам потребуется частное наименьшее решение.

Пусть 31x это количество поездок с тарифом 31 рубль.
А 32y это количество поездок с тарифом 32 рубля.

Тогда, задача сводится к уравнению:
$31x+32y=5000$

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент.
$displaystyle 31x=5000-32y\\x= frac{5000-32y}{31}$

Остатки при делении на 31: 0,1,2,3,4,5,6,7,8...30. Подставим вместо y эти числа.
$y=0 Rightarrow x =frac{5000}{31}\y=1 Rightarrow x =frac{4968}{31} \y=2 Rightarrow x =frac{4936}{31} \y=3 Rightarrow x =frac{4904}{31}\y=4 Rightarrow x =frac{4872}{31}\y=5 Rightarrow x =frac{4840}{31}\y=6 Rightarrow x =frac{4808}{31} \y=7Rightarrow x= frac{4776}{31} \y=8Rightarrow x= frac{4744}{31} \y=9Rightarrow x= frac{4712}{31} =152$

С помощью такого подбора, мы обнаружили первую пару: $(152,9)$.

Найдем теперь общее решение уравнения:
$displaystyle {begin{cases}x=x_{0}+n{frac {b}{(a,;b)}}\y=y_{0}-n{frac {a}{(a,;b)}}end{cases}}quad nin mathbb {Z}$

Здесь (a,b) = НОД(а,b) - коэффициенты при неизвестных.
$displaystyle {begin{cases}x=152+32n}\y=9-31n}end{cases}}quad nin mathbb {Z}$

Теперь на нужно найти минимальное количество поездок.

Решим неравенства:
1.
$displaystyle 152+32n geq 0\152 geq -32n\n geq -4,75$

$nin [-4,75,+infty)$

2. 

$9-31n geq 0\9 geq 31n\n leq frac{9}{31}$

$nin (-infty, frac{9}{31}]$

Находим пересечение:
$(-infty, frac{9}{31} ]cap [-4,75,+infty)=[-4,75, frac{9}{31} ]$

Наименьшее целое число из данного промежутка, это -4.

Подставляем n=-4:

$displaystyle {begin{cases}x=24}\y=133}end{cases}}$

Мы математически строго нашли наименьший натуральный x и наименьший натуральный y.

$31cdot 24=744$ - рубля, потрачено на наземном транспорте.

$32cdot 133=4256$ - рубля, потрачено на метро.

$24+133=157$ - суммарное количество поездок.

Answer 2

КРУТО! Спасибо!