Монеты бывают номиналов 50 копеек, 1 рубль, 2 рубля, 5 рублей, 10 рублей. В кошельке лежит несколько монет. Известно, что какие бы 20 монет ни вытащить из кошелька, среди них будет хотя бы одна рублевая, хотя бы одна двухрублевая и хотя бы одна пятирублевая. При каком наибольшем количестве монет в кошельке такое возможно?

Предыдущий
вопрос Следующий
вопрос

Наибольшее количество монет в кошельке, при котором можно гарантировать наличие по одной монете каждого номинала в любых 20 монетах, равно 22.

Пусть в кошельке имеется a монет номиналом 50 копеек, b монет номиналом 1 рубль, c монет номиналом 2 рубля, d монет номиналом 5 рублей и e монет номиналом 10 рублей.

Тогда общее количество монет в кошельке равно a + b + c + d + e, и условие задачи можно записать в виде системы неравенств
a + b + c + d + e = 2
a ≥ 1, b ≥ 1, c ≥ 1, d ≥ 1, e ≥ 1

Количество вариантов решения этой системы можно найти методом комбинаторики. Первоначально есть C(22+5-1,5-1) способов сделать 22 из 5 положительных целых чисел, что равно C(26,4). Но это число включает и случаи, когда одно или несколько чисел равны 0. Но всегда должно быть по крайней мере одно числов независимо от других, значит такие случаи будут отдельными группами, которые мы из числа вариантов вычитаем.

Таким образом, общее количество возможных вариантов равно
C(26,4) - C(5,1) C(21,4) + C(5,2) C(16,4) = 14950

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