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=7\Rightarrow x= \frac{4776}{31} \\y=8\Rightarrow x= \frac{4744}{31} \\y=9\Rightarrow 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 n\in \mathbb {Z}$

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

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

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

$n\in [-4,75,+\infty)$

2. 

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

$n\in (-\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.

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

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

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