Question

In arranging a 10-day examination time-table involving 10 subjects and one subject per day, how many ways are possible when mathematics, physics and chemistry all separated by at least one day?

Answer 1

1,693,440

Explanation:

There are 10 days, 10 subjects, and we don't want M, P, and C to sit next to each other. We can either find all the ways to arrange the 10 subjects and subtract out those ways where M, P, and C do sit next to each other, or we can specifically list out the ways to arrange M, P, and C within the requirements.

Since I'm not a fan of the subtract out method (it starts to get convoluted with dealing with any given (but only) 2 of the subjects next to each other, then dealing with all 3 next to each other, that I prefer (when feasible) to list out the ways we can have M, P, and C arranged.

Ok... we have 10 days:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

we can put one of our subjects in day 1, one in day 3, and one in day 5 (inserting S for Subject):

S, 2, S, 4, S, 6, 7, 8, 9, 10

that's

1, 3, 5

and we can continue:

1, 3, 5
1, 3, 6
1, 3, 7
1, 3, 8
1, 3, 9
1, 3, 10

or 6 ways starting with 1, 3, ...

notice that each time we move a starting digit over, we lose one way:

1, 4, 6
1, 4, 7
1, 4, 8
1, 4, 9
1, 4, 10

or 5 ways with 1, 4, ...

By extension, our arrangements starting with 1 is:

`6+5+4+3+2+1=21`

And the same goes for starting with a 2:

2, 4, 6
2, 4, 7
2, 4, 8
2, 4, 9
2, 4, 10

or 5 ways to arrange.

By extension, the number of ways we can arrange starting with a 2 is:

`5+4+3+2+1=15`

And by extension again, the number of ways we can arrange further is:

`4+3+2+1=10`
`3+2+1=6`
`2+1=3`
`1`

All told:

`21+15+10+6+3+1=56`

56 valid arrangements of time schedule. There are 3 subjects we can stick into that arrangement, and they order internally `3! = 6` ways, so we have:

`56xx6=336` ways

Now let's deal with the other seven subjects. They can go anywhere in the remaining slots, which is `7! = 5040` ways.

And so with 336 ways to arrange M, P, and C and 5040 ways to arrange the other subjects, we have:

`336xx5040="1,693,440"` ways

Answer 2

An alternate solution approach:

Explanation:

Let's work this from the other direction and see that we get the same result.

The first thing we need to do is find the total number of ways we can order the 10 subjects, which is `10! = "3,628,800"`

Now we start working through the numbers of ways that are disallowed - having 2 or more of the three subjects next to each other.

All 3 together

For this calculation, we can have the subjects in spots 1, 2, 3; 2, 3, 4; ... 8, 9, 10. That's 8 ways altogether they can be arranged. Within that arrangement, they can be internally ordered `3! = 6` different ways, so we end up with

`8xx6=48` different ways they can be arranged.

We then look at the remaining 7 subjects and see that they can be arranged in `7! = 5040` ways, giving

`48xx5040="241,920"` ways that are disallowed.

Only 2 together

This one is a little trickier because if we have the two subjects in places 1, 2 or 9, 10, there is only one place where the third subject can't be: 3 or 8 respectively. If we have the two courses in the other possible places (2, 3 up to 8, 9), then there are 2 places the third course can't be.

In places 1, 2 and 9, 10, we have 7 places the third course can be. That's `2xx7=14`.

In places 2, 3 up to 8, 9 (7 places), we have 6 places where the third course can be. That's `7xx6=42`.

We add these up: `14+42=56` ways to arrange two courses only touching.

There are `3! =6` ways to arrange the three courses. And there are `7! =5040` places where the remaining courses can go:

`56xx6xx5040="1,693,440"`

2 or 3 courses together

`"241,920"+"1,693,440"="1,935,360"` excluded ways

This then gives the amount of allowable arrangements:

`"3,628,800"-"1,935,360"="1,693,440"`