【正确答案】人、猫、鸡、米分别记为i=1，2，3，4，当i在此岸时记x_i=1，否则记x_i=0，则此岸的状态可用s=(x₁，x₂，x₃，x₄)表示．记s的反状态为s'=(1-x₁，1-x₂，1-x₃，1-x₄)，允许状态集合为s={(1，1，1，1)，(1，1，1，0)，(1，1，0，1)，(1，0，1，1)，(1，0，1，0)及它们的5个反状态}．
   决策为乘船方案，记作d=(u₁，u₂，u₃，u₄)，当i在船上时记u_i=1，否则记u_i=0，允许决策集合为D={(1，1，0，0)，(1，0，1，0)，(1，0，0，1)，(1，0，0，0)}．
   记第k次渡河前此岸的状态为s_k，第k次渡河的决策为d_k，则状态转移律为s_k+1=s_k+(-1)^kd_k，设计安全过河方案归结为求决策序列d₁，d₂，…，d_n∈D，使状态s_k∈S按状态转移律由初始状态s₁=(1，1，1，1)经n步到达s_n+1=(0，0，0，0)．一个可行方案如下：
   

k	1	2	3	4	5	6	7	8
sk	(1，1，1，1)	(0，1，0，1)	(1，1，0，1)	(0，1，0，0)	(1，1，1，0)	(0，0，1，0)	(1，0，1，0)	(0，0，0，0)
dk	(1，0，1，0)	(1，0，0，0)	(1，0，0，1)	(1，0，1，0)	(1，1，0，0)	(1，0，0，0)	(1，0，1，0)