Найти все возможные комбинации баллов в соответствии с данными

Question

Итак, я работал над проблемой в свободное время и застрял.Вот где я.У меня есть номер 40. Он представляет игроков.Мне дали другие числа 39, 38, .... 10. Они представляют результаты первых 30 игроков (1 -30).Остальные игроки (31-40) имеют неизвестный счет.Что я хотел бы сделать, это выяснить, сколько комбинаций баллов соответствуют приведенным данным.

Итак, для более простого примера: если у вас есть 3 игрока.У каждого из них 1 балл. Тогда количество возможных комбинаций баллов равно 3 (0,2; 2,0; 1,1), где (a, b) обозначает количество выигрышей для первого и второго игрока.соответственно.Комбинация (3,0) не сработает, потому что ни у одного человека не может быть 3 побед.(0,0) также не сработает, потому что нам нужно всего 3 победы (а не 0,0).

Я нашел максимально возможное количество игр.Это общее количество сыгранных игр, то есть общее количество побед.(Нет никаких связей.) Наконец, у меня есть переменная для максимального выигрыша на игрока (который на один меньше, чем общее количество игроков. Ни у одного игрока не может быть больше этого).

Я пробовалнайти количество уникальных комбинаций, распределив N побед каждому игроку, а затем вычесть комбинации, которые не соответствуют критериям.Например, чтобы найти множество способов дать 10 побед 5 людям, но не более 4 побед каждому, вы должны использовать: C (14,4) - C (5,1) * C (9,4) + C(5,2) * C (4,4) = 381. C (14,4) происходит от формулы C (n + k-1, k-1) (гугл-бары и полоски, я считаю).Следующим является выбор из тех, которые с 5 (не допускается), но добавление в те, которые мы вычитали дважды.

Да, должен быть более легкий путь.Наконец, цифры становятся настолько большими, что я не уверен, что мой компьютер может адекватно с ними справиться.Мы говорим о C (780, 39), который равен 1,15495183 × 10 ^ 66.Несмотря на это, должен быть лучший способ сделать это.

Напомним, у вас есть 40 человек.Баллы первых 30 человек - 10 - 39. Последние десять человек имеют неизвестные оценки.Сколько очков вы можете набрать, которые соответствуют критериям: все очки складываются в общее количество возможных побед, и каждый игрок не получает больше 39 побед.

Мысли?

Answer 1

Генерация функций:

Поскольку вопрос больше касается математики, но все еще находится на сайте QA, позвольте мне дать вам частичное решение, которое работает для многих из этих проблем с использованием символической алгебры (например, Maple ofMathematica).Я настоятельно рекомендую вам взять вступительную книгу по комбинаторике, на эти вопросы есть ответы.

Прежде всего, первые 30 игроков, набравших 10-39 баллов (с общим счетом 735), немногокрасная сельдь - мы хотели бы решить проблему other , оставшиеся 10 игроков, чей счет может быть в диапазоне (0 ... 39).

Если мы думаемиз возможных баллов игроков как полином:

f(x) = x^0 + x^1 + x^2 + ... x^39

Где значение x ^ 2 является, например, счетом 2, рассмотрим, как это выглядит

f(x)^10    

Этопредставляет совокупный счет всех 10 игроков, т.е.коэффициент x^385 равен 2002, что отражает тот факт, что 10 игроков могут набрать 385 очков в 2002 году. Wolfram Alpha (язык программирования IMO) может оценить это для нас .

Если вы хотите узнать, сколько возможных способов сделать это, просто подставьте в выражение x=1 выражение 8 840 406 085 191 601, что равняется 39 ^ 10 (неудивительно!)

Почему это полезно?

Хотя я знаю, что некоторым может показаться глупым настроить весь этот механизм для простой задачи, которая может быть решена на бумаге - подход генерация функций полезно, когда проблема становится беспорядочной (и возможен асимптотический анализ).Рассмотрим ту же проблему, но теперь мы ограничиваем игроков набирать только простые числа (2,3,5,7,11, ...).Сколько возможных способов 10 из них могут набрать конкретное число, скажем, 344?Просто измените ваш f(x):

f(x) = x^2 + x^3 + x^5 + x^7 + x^11 ...

и повторите процесс!( Я получаю [x^344]f(x)^10 = 1390).