#Soham Palande, Assignment 13, 10/25/2020




#PART 1

A={S, O, H, A, M, P, L, N, D, E} -> set of letters in my name
A_v={O, A, E} -> set of vowels in my name
A_c={S, H, M, P, L, N, D} -> set of consonants in my name

(i)

The total number of 100 letter words is = 10^100

Since we cannot have any two consonants be adjacent, we can break this this down into distinct sets.
We have 7 consonants in total.
Thus we cannot have :

7 consonants be together 
6 consonants be together 
.
.
.
2 consonants be together

The number of ways in which we can have 7 consonants be together is 
 
4^100 * 7!


The number of ways in which we can have 6 consonants be together is 

5^100 * 7C1 * 6!


The number of ways in which we can have 5 consonants be together is 

6^100 * 7C2 * 5!

.
.
.

The number of ways in which we can have 2 consonants be together is 

9^100 * 7C5 * 2!


Hence the number of words in which no two consonants can be adjacent is 

10^100 - ( 4^100 * 7! +  5^100 * 7C1 * 6! + 6^100 * 7C2 * 5! + ... + 9^100 * 7C5 * 2!)


(ii) 

No two vowels can be adjacent.

This follows a similar approach to (i).
We have 3 vowels in total. 
Thus we cannot have :

3 vowels be together 
2 vowels be together

The number of ways in which 3 vowels can be together is

8^100 * 3!


The number of ways in which 2 vowels can be together is 

9^100 * 3C2 * 2!


Hence the number of words in which no two vowels can be adjacent is 

10^100 - ( 8^100 * 3! + 9^100 * 3C2 * 2! )


(iii)

No two vowels and no two consonants can be adjacent. 

Thus the consonants and vowels must be alternating.

Since we have 7 consonants and 3 vowels at each position we can choose from among 3 vowels or 7 constants in an alternating sequence.

So if we start with vowels, the number of such words are:

3 * 7 * 3 * 7 * 3 * ... * 7      (the sequence of length 100)

Similarly, if we start with consonants, the number of such words are:

7 * 3 * 7 * 3 * 7 * ... * 3


So the total number of such words are

( 3 * 7 * 3 * 7 * 3 * ... * 7 ) + (7 * 3 * 7 * 3 * 7 * ... * 3 )

= (3^50)(7^50) + (3^50)(7^50)

=  2*(3^50)*(7^50)


(iv)







#PART 2

F: Farmer
W: Wolf
S: Sheep
C: Cabbage

We will model each of the possible states and then represent them as a graph

1:  F W C S   ------   		(all of them are on the same side)

2:  W C       ------   F S      (the farmer can only bring the sheep across)

3:  F W C     ------   S        (the farmer can take either the wolf or cabbage with him)

4:  C         ------   F W S

5:  W         ------   F C S

(From states 4 or 5 the farmer must take back the sheep with him otherwise we would return to state 3)

6:  F W S     ------   C        

7:  F C S     ------   W

(now the farmer must take the wolf or cabbage across from states 6 and 7 respectively otherwise he could take the sheep which would return to state 4 and 5 respectively)



8:  S         ------   F W C    (now taking either the wolf or cabbage would return to states 6 or 				the inverse of state 5 so the farmer goes alone)


9:  F S       ------   W C      (If the farmer goes back alone that would return to state 7 so he 				must take the sheep back with him)

10:            ------   F W C S  (they have all crossed successfully)


Now if we consider the states 1-10 as vertices and two vertices are neighbors iff they can transition from those two states using one boat ride

We get the following directed graph in the list of sets notation

G:=[{2},{3},{4,5},{7},{6},{8},{8},{9},{10},{}]

Paths(G,1,10,7)
{[1, 2, 3, 4, 7, 8, 9, 10], [1, 2, 3, 5, 6, 8, 9, 10]}



#PART 4

Modeling the problem using graphs, the vertices can be of the form (M,C,S) where:

M: # of Missionaries
C: # of Cannibals 
S: Side- left/right

Initially, we have (3,3,L) assuming they start on the left side of the river. Any transition from this state produces a vertex (M,C,R) on the right side. Thus we can transition from vertices iff they satisfy the given constraints. We want to find the Paths from (3,3,R) to (0,0,L). 


The graph will have vertices:

1: (3,3,L)
2: (3,3,R)         
3: (3,2,R) 
4: (3,2,L) 
5: (3,1,R) 
6: (3,1,L) 
7: (3,0,R) 
8: (3,0,L) 
9: (2,3,R) 
10: (2,3,L) 
11: (2,2,R) 
12: (2,2,L) 
13: (2,1,R) 
14: (2,1,L) 
15: (2,0,R) 
16: (2,0,L) 
17: (1,3,R) 
18: (1,3,L) 
19: (1,2,R) 
20: (1,2,L) 
21: (1,1,R)
22: (1,1,L) 
23: (1,0,R) 
24: (1,0,L) 
25: (0,3,R)  
26: (0,3,L) 
27: (0,2,R)  
28: (0,2,L) 
29: (0,1,L)
30: (0,1,R)  
31: (0,0,L)
32: (0,0,R)  

Now two vertices have an edge between them if the to states represented by the vertices can be interchanged by one boat ride.

The solution can be obtained by drawing the edges between the 1 step transition states and using the function Paths(G,1,2,k).
The graph is