PeterNaut's blog

Combinatorics problem help
By PeterNaut, 10 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So is the answer binomial coefficient of (24, 12) * 12!?

    → Reply