Поездка в трамвае

[Ktina]

Билет на трамвай стоит 1 тугрик. У 20 пассажиров имеются лишь монеты достоинством в 2 и 5 тугриков, а у кондуктора вообще ничего. Оказалось, что все пассажиры смогли заплатить за проезд и получить сдачу. Какое наименьшее суммарное количество тугриков могло быть у пассажиров?

[statistonline]

Небольшое уточнение: пассажирам разрешается обмениваться между собой тугриками (временно в долг или равноценным обменом)? Или все операции только через кондуктора?

[slavav]

Полагаю, что можно переформулировать задачу так: после поездки у кондуктора стало на 20 тугриков больше, а каждого из двадцати пассажиров на один тугрик меньше. То есть, после поездки никто никому ничего не должен. В процессе обмена могут быть любые эволюции. Например: все пассажиры выложили свои тугрики на общий стол, затем каждый забрал на тугрик меньше чем выкладывал. Оставшиеся 20 тугриков забрал кондуктор. Сколько было тугриков на столе в начале?

-- 27.12.2018, 11:06 --

(Оффтоп)

Есть решение на 110 тугриков.

[Ktina]

statistonline в сообщении #1363962 писал(а):

Небольшое уточнение: пассажирам разрешается обмениваться между собой тугриками (временно в долг или равноценным обменом)? Или все операции только через кондуктора?

Разрешается.

[Booker48]

$191$?

(Оффтоп)

Рассмотрим случай 2-х пассажиров и кондуктора. У пассажира A $6 $тугриков $3$-мя монетками, у B - $5$ тугриков. A отдает $2$ тугрика кондуктору и $4$ пассажиру B, получая от последнего $5$ тугриков.
Теперь $20$ пассажиров. A, как и в первом случае, платит за всех $20$ тугриков ($10$ монет). После чего остальные отдают ему единственные пятачки, получая от него по $2$ монетки двушками. Всего денег у A $20+4\cdot19$, у остальных по $5$ тугриков.

[slavav]

(Оффтоп)

Решение для пары пассажиров годится и для двадцати. Разбейте их на пары.
Нужно 11 тугриков на двоих.
Для 20 нужно 110 тугриков.

[Booker48]

slavav

(Оффтоп)

Это было моё первое решение (разбить на пары), правда я в предновогоднем дурдоме решил, что интегрально получится 220 тугриков на всех...

[slavav]

(Оффтоп)

Долгий нудный ручной перебор показал что 110 - лучшее и единственное решение.

-- 27.12.2018, 14:18 --

(Оффтоп)

alex1910 в личном сообщении привёл результат 108.

-- 27.12.2018, 14:20 --

(Оффтоп)

Мой перебор не полон. Да, есть решение для 108. Как доказать что оно лучшее?

[slavav]

(Оффтоп)

Перебрал все решения, когда пассажиры выкладывают по 5 или 6 тугриков каждый. Их три с суммами 110, 109, 108. 108 - лучшее решение. Спасибо alex1910.

[gris]

Чего мудрить с переломами? Ясно, что у каждого пассажира для минмальности должно быть 5 или 6 тугриков, обозначим количество таких и таких пассажиров и составом два неравенства на получение сдачи. Получим 8 по 6 и 12 по 5.
Но где это вы видели такие монеты? Два и пять мунгу были и один тугрик, а потом только 10 тугриков и больше.

[PETIKANTROP]

В моем городе трамваи исчезли десять лет назад. Вот такой, друзья, каприз природы. На работу всем пешком пришлось бежать. Ехали по улицам трамваи, ехали куда-то умирать...

Ktina в сообщении #1363927 писал(а):

Какое наименьшее суммарное количество тугриков могло быть у пассажиров?

20 тугриков: минимально 4 монеты по 5 тугриков, если ехали 4 семьи.