If each class is used once per schedule, how many class schedules for next year are possible?

Question

You are choosing your classes for the upcoming school year.Your schedule consists of 8 class

periods. You have chosen classes A through H

for next year. Each class is taught during (a) specific period(s) and no two or more classes can take place at the same time. If each class is used once per schedule, how many class schedules for next year are possible? 

(Individual class time slots below)

Class A: periods: 1, 2, 4, and 6

Class B: periods: 1, 2, 6, and 8

Class C: periods: 4 and 6

Class D: periods: 1 and 8

Class E: periods: 4, 6, and 7

Class F: periods: 3 and 5

Class G: period: 3

Class H: Periods 1-8

Answer 1

There are two straightforward ways to do this problem.

Method 1;

have 8 variables a-h

loop each 1 1 -8;

check whether each meets the conditions stated above

if they do and a, b, c, d, e, f, g, and h are all different values, add 1.

Using the R programming and code

count = 0

for(a in 1:8){

if(a %in% c(1,2,4,6)){

for(b in 1:8){

if(b %in% c(1,2,6,8)){

for(c in 1:8){

if(c %in% c(4,6)){

for(d in 1:8){

if(d %in% c(1,8)){

for(e in 1:8){

if(e %in% c(4,6,7)){

for(f in 1:8){

if(f %in% c(3,5)){

for(g in 1:8){

if(g == 3){

for(h in 1:8){

if(!(a %in% c(b,c,d,e,f,g,h)) &

!(b %in% c(c,d,e,f,g,h)) &

!(c %in% c(d,e,f,g,h)) &

!(d %in% c(e,f,g,h)) &

!(e %in% c(f,g,h)) &

!(f %in% c(g,h)) &

g !=h)

{count = count + 1

countx <- paste(count,": ",a,sep='')

print(paste(countx,b,c,d,e,f,g,h,sep = ", "))

}}}}}}}}}}}}}}}}

I got a count of 23 with the following output: (see counter and periods selected for the classes)

[1] "1: 1, 2, 4, 8, 6, 5, 3, 7"

[1] "2: 1, 2, 4, 8, 7, 5, 3, 6"

[1] "3: 1, 2, 6, 8, 4, 5, 3, 7"

[1] "4: 1, 2, 6, 8, 7, 5, 3, 4"

[1] "5: 1, 6, 4, 8, 7, 5, 3, 2"

[1] "6: 2, 1, 4, 8, 6, 5, 3, 7"

[1] "7: 2, 1, 4, 8, 7, 5, 3, 6"

[1] "8: 2, 1, 6, 8, 4, 5, 3, 7"

[1] "9: 2, 1, 6, 8, 7, 5, 3, 4"

[1] "10: 2, 6, 4, 1, 7, 5, 3, 8"

[1] "11: 2, 6, 4, 8, 7, 5, 3, 1"

[1] "12: 2, 8, 4, 1, 6, 5, 3, 7"

[1] "13: 2, 8, 4, 1, 7, 5, 3, 6"

[1] "14: 2, 8, 6, 1, 4, 5, 3, 7"

[1] "15: 2, 8, 6, 1, 7, 5, 3, 4"

[1] "16: 4, 1, 6, 8, 7, 5, 3, 2"

[1] "17: 4, 2, 6, 1, 7, 5, 3, 8"

[1] "18: 4, 2, 6, 8, 7, 5, 3, 1"

[1] "19: 4, 8, 6, 1, 7, 5, 3, 2"

[1] "20: 6, 1, 4, 8, 7, 5, 3, 2"

[1] "21: 6, 2, 4, 1, 7, 5, 3, 8"

[1] "22: 6, 2, 4, 8, 7, 5, 3, 1"

[1] "23: 6, 8, 4, 1, 7, 5, 3, 2"

I wrote out the possibilities below

Method 2:

Use deductive reasoning combined with to eliminate parts of the search, and try certain values for some of the classes and see how that affects the other choices.

H will be the result of all other choices.

As G is 3, F is 3 or 5, so F is 5

Let's consider each of E in 4, 6, and 7

if E is 4, C is 4 or 6, so C is 6; if E is 6, C is 4 or 6, so C is 6.

Then, Class A can be 1, 2, 4, or 6, so it is 1 or 2, as 4 and 6 are taken.

If it is 1, as D is 1 or 8, D is 8. Then, as B is 1, 2, 6, and 8, 1, 6, and 8 are taken, so B is 2.

If Class A is 2, Class B can be 1, 2, 6, and 8, but 2 and 6 are taken, so B can be 1 or 8, and D can be 1 or 8

We thus have, for total counts, 2(from E, C) * (1 (A = 1) + 2 (A = 2)) = 2 * 3 = 6

(Note that, in our computer generated list, if we look for E and C as 4 and 6, we see 1, 3, 6, 8, 12, and 14 in our computer-generated list; this has the count of 6 as we deduced)

Now, we must consider E = 7.

if E is 7 and C is 6, we then have A is 1, 2, or 4, B is 1, 2, or 8, and D is 1 or 8. If D is 1, A is 2 or 4, and B is 2 or 8; this means 3 possibilities (either of A or B excluding both equal to 2. Thus, we have 3 choices. If D is 8, then A is 1, 2, or 4, and B is 1 or 2. If A is 4, then B can be 1 or 2. If A is 1, then B is 2, and if A is 2, then B is 1. Thus, for D is 8, we have 4 possibilities. Then, for E = 7 and C = 6, we have 3 possibilities with D = 1 and 4 with D = 8 equals 7 total. (This corresponds to 4, 9, and 15 - 19 above.)

If E is 7 and C is 4, we have A is 1, 2, 6, B is 1, 2, 6, 8, and D is 1, 8

If D is 1, then A is 2 or 6 and B is 2, 6, or 8. This gives us 2 * 3 - 2 = 4 possibilities (1 of each minus the 2 cases that they are the same). (10, 13, 21, and 23 above).

If D is 8, then A and B can both be 1, 2, or 6. This gives us 3 * 3 - 3 = 6 possibilities(3 of each minus the 3 where they are equal) (2, 5, 7, 11, 20, and 22)

We have now considered all possibilities.

We have 6 from E equaling 4 or 6, 7 from E equaling 7 and C equaling 6, 4 from E equaling 7, C equaling 4 and D equaling 1, and 6 from E equaling 7, C equaling 4, and D equaling 8 =

6 + 7 + 4 + 6 = 23

A lot easier to let the computer program do the work!