In this puzzle, a traveler needs to transport a lion, a poodle, and a giant chocolate bar across a river, but his boat can only fit himself plus one of the other three. A configuration of this puzzle can be described as a length 4 binary string, where each bit from left to right describes the status of the traveler, the lion, the poodle, and the chocolate, respectively. A 0 means that the item is on one side of the river (the starting side) and a 1 means that the item is on the other side of the river. For example the configuration 1100 means that the traveler and the lion are on not on the starting side of the river, and the poodle and the chocolate are on the starting side of the river. (a) (4 points) Which of the 16 possible configurations can actually be reached from the starting configuration (0000) if the following rules apply? It is forbidden to leave the lion and the poodle on a shore together without the traveler, or the lion will eat the poodle. It is forbidden to leave the poodle and the chocolate on a shore together without the traveler, or the poodle will eat the chocolate. Justify your answer using an appropriate graph. (b) (4 points) How can the traveler, the lion, the poodle, and the chocolate all make it across the river in the fewest number of boat trips possible? Say how many boat trips are required, and justify why this is the minimum amount by referring to the graph used in part (a). 2 (c) (2 points) Now suppose that the traveler must pay a toll of one dollar every time he crosses the river with an animal. How can they all make it across the river while paying the least money possible? Say how much money is required, and justify why this is the minimum amount by referring to the graph used in part (a).

2. In this puzzle, a traveler needs to transport a lion, a poodle, and a giant chocolate bar across a river, but his boat can only fit himself plus one of the other three. A configuration of this puzzle can be described as a length 4 binary string, where each bit from left to right describes the status of the traveler, the lion, the poodle, and the chocolate, respectively. A 0 means that the item is on one side of the river (the starting side) and a 1 means that the item is on the other side of the river. For example the configuration 1100 means that the traveler and the lion are on not on the starting side of the river, and the poodle and the chocolate are on the starting side of the river (a) (4 points) Which of the 16 possible configurations can actually be reached from the I is forbidden to leave the lion and the poodle on a shore together without the It is forbidden to leave the poodle and the chocolate on a shore together without the starting configuration (0000) if the following rules apply? traveler, or the lion will eat the poodle traveler, or the poodle will eat the chocolate Justify your answer using an appropriate graph (b) (4 points) How can the traveler, the lion, the poodle, and the chocolate all make it across ps possible? Say how many boat trips are required, and justify why this is the minimum amount by referring to the graph used in the river in the fewest number of boat tri part (a) (c) (2 points) Now suppose that the traveler must pay a toll of one dollar every time he crosses the river with an animal. How can they all make it across the river while paying the least money possible? Say how much money is required, and justify why this is the minimum amount by referring to the graph used in part (a)