Блог пользователя PeterNaut

Combinatorics problem help
Автор PeterNaut, 10 лет назад, По-английски

You want to send a message that contains 12 distinct signals and 45 spaces. You want that for any pair of signals in the message, there should be at least 3 spaces between them. How many different messages can you send?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Let the number of blank spaces before the first signal be x0, the number of blank spaces between the first and second signal be x1, etc.

Then your problem is equivalent to counting number of solutions to equation x0 + x1 + x2 + ... + xn = T, where T is total number of blank spaces and xi ≥ 3 for all 0 < i < n. You can use variable yi = xi - 3 and get the number of integer solutions to x0 + y1 + y2 + ... + yn - 1 + xn = T - (n - 1) * 3, which is solvable by balls and urns.

As the signals are distinct, multiply by n! in the end.

→ Ответить