4. (a) (2 points) A well-known old puzzle requires a farmer to get a wolf, a sheep, and a head of time, without lettuce across a river in a boat

that will only hold one of the three items at a time leaving the wolf alone with the sheep or the sheep alone with the lettuce. Explain how to solve this problem. (b) (4 points) now suppose a zorblaxian farmer named XAea-14 wants to cross a river of liquid nitrogen with n quoozods one of each species i will eat any quoozods of species i 1 left without their farmers so the zorblaxian farmer is nin an analogous situation to the earthling in the previou How big an airship does XAEA-14 need to be able to get all n quoozods across the river Consider separately the cases that n is even respectively odd (c) (2 points) Finally, suppose that XAEA-14 has a set of V of quoozaps together with a simple bipartite graph G= (v,e) such that (v1,v2 ) E if and only v1 will eat v2 if they are left together without the farmer suppose that min (v1),(v2) =k can xae14 always get all the quoozaps across he river with an airship of capacity k (d) (0 points) (Challenge:) If you answered "yes" to the previous part, try to generalize to non-bipartite graphs. If you answered "no", give the most general sufficient conditions on a bipartite graph you can to make the crossing possible. This is an open-ended question,so just do anything you can!