[Math] Different ways to write a number given digit constraints

combinatoricsprobability

Originally I was just going to ask the problem on my practice math contest, which is asking how many ways there are to write a nine-digit number containing each digit $1-9$ so that the first digit is twice as big as the second and the last two digits are odd. (e.g. $846527913$).

I understood that in this case, the number would be in the form of $EE(EEEOO)OO$ or $EO(EEOOO)OO$ where $E$ is an even, $O$ is an odd, the numbers in the parentheses can be ordered in any way, and the only four cases for the first two are $21, 42, 63,$ and $84.$ Calculating this gave me $240,$ which is definitely wrong (I made a program to check, and it says $7680$).

So here are the questions:

  1. How do I solve this particular problem correctly? Am I on the right track?
  2. How are these solved in general? Given that it's a $9$-digit number and each digit $1-9$ is used once, how does one handle constraints such as these? This has always confused me (I'm not very strong in combinatorics)

Best Answer

You're on the right track. I'd break the problem up into four cases: where the number starts with 21, 42, 63 or 84.

In the case where you start with 21, you must have 21(EEEOO)OO in your notation. (There are four even digits, so three of them must be in the middle part of the number.)

So we can ask the questions: - in how many different places can 4 go? - in how many different places can 6 go (given that we've already placed 4?) - in how many different places can 8 go (given that we've already placed 4 and 6)? The answers are 5, 4, and 3 respectively.

Then we need to place the four remaining odd digits among the four remaining places; there are of course $4! = 24$ ways to do this.

So there are a total of $5 \times 4 \times 3 \times 24 = 1440$ such numbers beginning with 21. The same is true if we start with 63 instead of 21. When we start with 42 or 84 the result is different but the method is much the same, and adding up the results from the four cases gives 7680.

As for (2), there aren't really "general" methods. But one thing that is good to keep in mind is trying to place the digits one at a time (as I've done above) instead of trying to do everything in one fell swoop.

Related Question