2.

This was an essay writing type question and scores were given based on the completeness, acuracy and depth of the arguments that were given.



6.

This was the hardest problem in this problem set. Several possible solutions exist. I will present here briefly one of the most intuitive ones.

Variables:
Mi[t] = true if i missionaries are on the original side of the river (i=0,1,2,3) at step t
Ci[t] = true if i cannibals are on the original side of the river (i=0,1,2,3) at step t
B[t]  = true if the boat is near the original side of the river at step t
Also:
C[t], CC[t], MC[t], M[t] and MM[t] are operator variable that become true when you at step t 1 canibal, 2 canibals etc. respectively are transported on the boat

Starting condition:
M3[0] and C3[0] and B[0]

End conditions: (M0[0] and C0[0]) or (M0[1] and C0[1]) or ... or (M0[k] and C0[k])

Now that we have all the variables and start/end conditons we need to state constraints. The following constraints are in conjunction (and).
First to make the variables consistent: (these are wirtten for all time steps t: 0<=t<=k)
- at least one Mi[t] is true: M0[t] or M1[t] or M2[t] or M3[t]
- at most one Mi[i] is true: ~Mi[t] or ~Mj[t], for all i<>j
- at least one Ci[t] is true: C0[t] or C1[t] or C2[t] or C3[t]
- at most one Ci[i] is true: ~Ci[t] or ~Cj[t], for all i<>j
Then we need to make sure that we do not end up in a state that the missionaries get eaten:
e,g, the case that we have 2 missionaries and 3 cannibals on the original side is not permitted so we put the constraint: ~M2[t] or ~C3[t]
similar for all the other invalid states.
Then we need to put constraints that we only take one operator varible at each step (alternatively you can state that we only have one state at each time step t):
- at least one operator varibale true: C[t] or CC[t] or MC[t] or M[t] or MM[t]
- at most one at each time step: ~operation1[t] or ~operation2[t], for all operation1<>operation2 when they take values from {C, CC, MC, M and MM} that is all the possible moves.
Now we need constraints to describe the transitions from state to state as we move people around in the boat. Two ways to do it are:
a)
when boat on the original side: M3[t] and C3[t] and B[t] and CM[t] => M2[t+1] and C2[t+1] and ~B[t+1]
when boat on the other side: M2[t] and C2[t] and ~B[t] and CM[t] => M3[t+1] and C3[t+1] and B[t+1]
we need to write all possible combinations of states and moves
we take the conjunction of these as we did with all the other constraints
The reason this works is because only one state and op. variable combination will be true at any time (due to the other constraints) and this will force the varibles at time t+1 to take the proper values
b)
when boat on the original side: M3[t] and C3[t] and B[t] and CM[t] and M2[t+1] and C2[t+1] and ~B[t+1]
when boat on the other side: M2[t] and C2[t] and ~B[t] and CM[t] and M3[t+1] and C3[t+1] and B[t+1]
we take the disjunction (or) of these for each time step t and then the conjunction of these for all t.
We take disjunction of these at the beginning because we only wish one combination of states at times t, t+1 and op. varible to be true at any time step and this for all time steps. Again based on the other constraints only one of these can be true at each step t.

By stating the problem like that when we solve it we will get a list of the operator variables that become true at each time t and this is the solution we seek.