Районная олимпиада, 2011-2012 учебный год, 11 класс

Имеется шесть различных кошельков. Сколькими способами можно разложить в них двенадцать одинаковых монет, чтобы пустым остался максимум один кошелек?

Комментарий/решение

Ответ : $30^{12} $

Решение. Рассмотрим несколько случаев. Пусть заполняются 6 кошельков. Каждая монета может попасть в один из шести кошельков, а таких монет 12. Из этого следует, что для 6 кошельков способов будет $6^{12}$. В случае, если кошельков будет 5,то получим $5^{12 } $ способов. Окончательно $30^{12} $способов

Давайте разделим условие на два независимых события:

заполнено ровно 6 кошельков;

заполнено ровно 5 кошельков (выбрать которые можно шестью различными способами).

В первом случае 6 из 12 монет следует разложить в каждый из 6-ти кошельков (чтобы ни один не оказался пустым).

Остальные 6 монет следует распределить между кошельками произвольным образом в количестве от 0 до 6 в каждом. В переводе на язык комбинаторики означает выбрать 6 раз один из 6-ти кошельков, возможно, неоднократно и без учета порядка. Или формально, количество сочетаний с повторениями из 6 элементов по 6:

H66 = C66+6-1 = C611.

Аналогично, во втором случае(для каждой из 6-ти пятерок выбранных кошельков) 5 из 12 монет следует разложить в каждый из 5-ти кошельков.

Остальные 12-5=7 монет следует распределить между этими 5-ю кошельками произвольным образом в количестве от 0 до 7 в каждом. Что означает выбрать 7 раз один из 5-ти кошельков, возможно, неоднократно и без учета порядка:

H75 = C77+5-1 = C711.

Объединив оба случая, получим общее количество способов:

n = H66 + 6*H75 = C611 + 6*C711 = 462 + 6*330 = 2442.