5
$\begingroup$

Given $10$ digits, where each digit can be an integer from $0$ to $9$, how can I determine the number of ways to arrange the numbers so that two odds are not adjacent?

Repetition of digits is not allowed.

So far, I have figured out the total number of possibilities: $$10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 10!$$

Then I had planned to subtract the number of bad possibilities from the total number of possibilities.$$10! - X$$ Where $X$ is all the bad possibilities, which means $X$ is all the possibilities where two odds could be next to each other in the $10$ digits.

I know that for each number, $5$ odds can be selected, how can I use this information to figure out the answer to the question?

$\endgroup$
  • $\begingroup$ If you only care about odd or even for a second, how many ways can you distribute the five odds and the five evens so that no odds are adjacent? $\endgroup$ – Arthur Oct 20 '18 at 6:51
  • 1
    $\begingroup$ Hint: put the odds in a row (how many possibilities?) and then separate consecutives by placing an even (how many possibilities?). After that only one even number is left and must be placed. Watch out for multiple counting. $\endgroup$ – drhab Oct 20 '18 at 6:57
  • $\begingroup$ Are the digits all distinct? The way you're talking about the possible solutions seems to imply that they are, but I notice that you don't actually say so anywhere in the question. $\endgroup$ – David Z Oct 20 '18 at 8:45
  • $\begingroup$ @DavidZ it says in the question that repetition is not allowed. $\endgroup$ – Matt Hough Oct 20 '18 at 8:51
  • 1
    $\begingroup$ Oh, so it does, somehow I missed that. Sorry! $\endgroup$ – David Z Oct 20 '18 at 9:07
8
$\begingroup$

There are six different admissible assignments of odd (O) and even (e) numbers:

OeOeOeOeOe
OeOeOeOeeO
OeOeOeeOeO
OeOeeOeOeO
OeeOeOeOeO
eOeOeOeOeO

For these arrangements of parity there are $5!$ ways of fixing the odd numbers, and the same number of ways to fix the even numbers. Thus there are $6×5!×5!=86400$ ways.

$\endgroup$
  • $\begingroup$ the final one might have an issue with starting $0$ digit. Not sure if it's allowed. One would need to substract some options. $\endgroup$ – Henno Brandsma Oct 20 '18 at 7:15
  • $\begingroup$ @HennoBrandsma it was not specified in the question that the result had to be a 10-digit number. $\endgroup$ – Parcly Taxel Oct 20 '18 at 7:16
  • $\begingroup$ It's just 10 digits, not a 10 digit number. It's fine. $\endgroup$ – Matt Hough Oct 20 '18 at 7:17
9
$\begingroup$

Let $O$ and $E$ be the odd and even numbers respectively.

The odd digits are $1,3,5,7,9$.

The even digits are $0,2,4,6,8$.

$_E_E_E_E_E_$

If you are filling the odd numbers in any $5$ blank spaces yiels a required number.

There are $6$ blank spaces. So the number of ways to select $5$ spaces among $6$ spaces $=6C5 =6$.

Number of possible shuffling on $5$ odd number is $=5!=120$.

Again,Number of possible shuffling on $5$ even number is $=5!=120$.

Thus total number of possibility is $=6×120×120=86400$.

$\endgroup$
  • 1
    $\begingroup$ Is there a reason the image has 11 spots? (_E_E_E_E_E_) $\endgroup$ – Matt Hough Oct 20 '18 at 7:23
  • $\begingroup$ I think, there is no reason behind it. I just think logically and post the answer. $\endgroup$ – Avinash N Oct 20 '18 at 7:27
  • $\begingroup$ The logic seems off because you can assign more than one even number to one of the middle spaces and still get a valid solution. On the other hand, if you use both outer spaces, your solution will be invalid. $\endgroup$ – Sumyrda Oct 20 '18 at 10:49
  • 1
    $\begingroup$ @Sumyrda, that's why there are six blank slots for five odd digits. Consider oEoEoE_EoEo, where one of the middle blanks is left empty. Now there are two even digits next to each other in the middle and both of the outer spaces are used. On the other hand, if you put two of the five even digits in one of the "E" slots, you'll need to leave another empty since you run out of digits. Then you'll have to avoid putting two odds around that empty "E". You'll get the same possible orderings still, it just breaks this simple system of counting them. $\endgroup$ – ilkkachu Oct 20 '18 at 13:37
  • 1
    $\begingroup$ @MattHough If we line up the five even numbers, this creates six spaces, four between successive evens and two at the ends of the row. In order to separate the odds, we must choose five of these six spaces in which to place an odd number. The number of blank spaces created when you line up $n$ objects in a row is $n + 1$ since there are $n - 1$ spaces between successive objects and two at the ends of the row. $\endgroup$ – N. F. Taussig Oct 21 '18 at 9:22
1
$\begingroup$

This is almost same as the previous answers, but I’m going to present it in an (arguably) less brute-force manner.

We first observe that if we partition the digits in any valid permutation into 5 pairs, each pair must have exactly 1 odd and 1 even digits, for otherwise, there must be at least one (odd, odd) pair. (An unordered pair can only be (odd, even), (even, even) and (odd, odd). If (even, even) appears, since the numbers of odd and even digits are the same (both 5), there must be an (odd, odd) pair to balance it.)

Now fix the odd digits $1, 3, 5, 7, 9$ and assign each digit an even digit. So there are $5!$ ways to assign the even digits.

Now we have $5$ (odd, even) pairs. To permutate them we have another $5!$ ways.

Next, we are going to merge the pairs. Since no two odd digits can be adjacent, we observe the following: if the previous pair is (even, odd), then the next pair must be (even, odd). Otherwise, we can choose to have (even, odd) or (odd, even).

Hence we can “switch” to (even, odd) at any of 5 pairs, and we can switch at most once. The remaining possibility is not to switch at all. Hence for every pair set containing 5 pairs, there are altogether $6$ switching possibilities.

It follows that the number of permutations is $5!\times5!\times6 = 86400$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.