Комбинаторика, голосование

Математика
1

30 people vote on 4 proposals. In how many ways can votes be distributed if everyone votes for only one proposal and only the number of votes for each proposal is taken into account?

можете объяснить как решается?
никак не понимаю даже суть задачи

2

@eudaimon в чем вообще суть задачи? Можешь объяснить на русском?

3

Объяснение задачи на русском

Здравствуйте! Я понимаю ваше затруднение. Давайте разберемся с сутью задачи на русском языке.

Суть задачи:

  • У нас есть 30 человек, которые голосуют
  • Есть 4 предложения (proposals), за которые можно голосовать
  • Каждый человек голосует только за одно предложение
  • Нас интересует только количество голосов за каждое предложение (а не то, кто именно за что проголосовал)
  • Требуется найти: сколько разных способов распределения голосов возможно?

Пример для понимания:

Например, один вариант распределения:

  • 10 голосов за предложение №1
  • 5 голосов за предложение №2
  • 8 голосов за предложение №3
  • 7 голосов за предложение №4

Другой вариант:

  • 15 голосов за предложение №1
  • 5 голосов за предложение №2
  • 5 голосов за предложение №3
  • 5 голосов за предложение №4

И так далее. Нам нужно посчитать, сколько всего может быть разных распределений.

Скажите, стала ли задача понятнее? Что вы думаете о том, как можно подойти к её решению?

4

Знаком с задачей про шары и перегородки? Почти тоже самое

Рассмотрим уравнение:

x_1 + x_2 + x_3 + x_4 = 30

Число таких решений находится с помощью формулы шаров и перегородок:

C^{n + k - 1}_{k - 1}

где n = 30 — количество голосов, а k = 4 — количество предложений. Подставляем:

C^{30 + 4 - 1}_{4 - 1} = C^{33}_{3}

Рассчитываем биномиальный коэффициент:

C^{33}_{3} = \frac{33 \cdot 32 \cdot 31}{3 \cdot 2 \cdot 1} = 5456

Таким образом, количество способов распределить голоса равно 5456.

4 лайка
5

Я обычно решаю такие задачи довольно странным, но примитивным способом. Поскольку все голоса эквивалентны (нам не важно кто за что голосовал), обозначим один голос символом \times. Если мы расставим все тридцать голосов в ряд по типу

\times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times \times

то очевидно, что нет возможности дифференцировать между кол-вом голосов за каждый proposal. Но что если мы внедрим символ | для возможности дифференцировать? Тогда можно представить ситуацию, в которой у proposal 1 имеется 10 голосов, у proposal 2 имеется 5 голосов, у proposal 3 имеется 7 голосов, и у proposal 4 имеется 8 голосов как последовательность

\times \times \times \times \times \times \times \times \times \times | \times \times \times \times \times | \times \times \times \times \times \times \times | \times \times \times \times \times \times \times \times

Тогда вся задача сводится к тому, чтобы найти количество всевозможных строк, которые состоят из тридцати символов \times и трех символов |. Если бы все символы были разные, то получилось бы 33! строк. Но поскольку тридцать символов абсолютно идентичны, у одной репрезентативной строки имеется 30! копий, и тогда разных строк будет 33!/30!. Так как оставшиеся три символа тоже идентичны, у каждой репрезентативной строки из 33!/30! строк имеется 3! копий, и тогда конечным кол-вом всевозможных строк будет 33!/(30!3!) = 5456.

P.S. А, ну хотя, принципиально ничем не отличается от предыдущего решения

P.S.2. Более того, я оказывается расписал абсолютно тот же метод, к которому ссылался @ace :kissing:

5 лайков