Assignments

Homework	[15 points] A farmer went to a market and purchased a wolf, a goat, and a cabbage. There is a river the farmer has to cross to bring the three things home. The farmer owns a boat. The boat capacity is two. Only the farmer can row the boat. In the absence of the farmer, the wolf eats the goat or the goat eats the cabbage. What is the strategy to transport the farmer and all three purchases to the other side of the river safely? Construct a state diagram; give two solutions; and find the number of trips. [15 points] There are two empty containers: a 3-liter container and a 5-liter container. There is a fresh pond with water that can be used to either fill up or empty a container. Three operations are allowed: fill, empty, and transfer. How would you measure exactly 4 liters of water using the two containers and the pond in the minimum number of steps/operations? Construct a state diagram; give an optimal solution; and find the number of steps/operations. [15 points] There are 9 identical-looking coins; one of these coins is defective and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the lighter coin with a two-arm weighing balance scale? Draw the decision tree showing all possible options similar to what we discussed in the class; write the solution clearly in words using step-by-step instructions; and write the minimum number of weighings needed. [15 points] A good king has a cellar with 10 bottles of wine. A bad minister who had a deal with the neighboring king decides to kill the good king. He sends his most trustworthy servant to poison the wine bottles. The poison is so strong that even if diluted an unlimited number of times it still can kill a person. The king's guards catch and kill the servant after the servant has poisoned only one bottle. The guards do know that exactly one bottle is poisoned but do not know which one. The guards also know that it takes a day for the poison to have its effect. The king decides to get some rats to taste the wines and identify the poisoned bottle. What strategy can the king use to identify the poisoned bottle in 1 day and minimizing the total number of rats used? Draw the table to show which rats sip wine from which bottle; give the method of finding the poisoned bottle from the rats; and find the number of rats required and report how many of them can die in the worst case. [15 points] There is a switch room and a light room. There are 10 switches in the switch room and 10 bulbs in the light room. There is a long corridor between the switch and the bulb room. One cannot see the contents/state in one room being in another room. It is not known which switch corresponds to which bulb. Assume that you are initially in the switch room, all switches are off, and hence all bulbs are off. How do you find the one-to-one correspondence between the switches and the bulbs minimizing the number of trips to the light room? Extensively use diagrams and tables to explain your method/approach. [15 points] We want to measure any integer weight in the range [1, 30] using a two-sided weighing balance using a minimum number of weights. Explain how can we solve the problem assuming: (a) we can place weights only on one side, and (b) we can place weights on either side of the weighing balance. [10 points] Explain in detail: (i) What is your favorite puzzle (irrespective of whether it is covered in this course or not) and why? and (ii) What puzzle-solving techniques did you learn in this course?

Homework

[15 points] A farmer went to a market and purchased a wolf, a goat, and a cabbage. There is a river the farmer has to cross to bring the three things home. The farmer owns a boat. The boat capacity is two. Only the farmer can row the boat. In the absence of the farmer, the wolf eats the goat or the goat eats the cabbage. What is the strategy to transport the farmer and all three purchases to the other side of the river safely? Construct a state diagram; give two solutions; and find the number of trips.
[15 points] There are two empty containers: a 3-liter container and a 5-liter container. There is a fresh pond with water that can be used to either fill up or empty a container. Three operations are allowed: fill, empty, and transfer. How would you measure exactly 4 liters of water using the two containers and the pond in the minimum number of steps/operations? Construct a state diagram; give an optimal solution; and find the number of steps/operations.
[15 points] There are 9 identical-looking coins; one of these coins is defective and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the lighter coin with a two-arm weighing balance scale? Draw the decision tree showing all possible options similar to what we discussed in the class; write the solution clearly in words using step-by-step instructions; and write the minimum number of weighings needed.
[15 points] A good king has a cellar with 10 bottles of wine. A bad minister who had a deal with the neighboring king decides to kill the good king. He sends his most trustworthy servant to poison the wine bottles. The poison is so strong that even if diluted an unlimited number of times it still can kill a person. The king's guards catch and kill the servant after the servant has poisoned only one bottle. The guards do know that exactly one bottle is poisoned but do not know which one. The guards also know that it takes a day for the poison to have its effect. The king decides to get some rats to taste the wines and identify the poisoned bottle. What strategy can the king use to identify the poisoned bottle in 1 day and minimizing the total number of rats used? Draw the table to show which rats sip wine from which bottle; give the method of finding the poisoned bottle from the rats; and find the number of rats required and report how many of them can die in the worst case.
[15 points] There is a switch room and a light room. There are 10 switches in the switch room and 10 bulbs in the light room. There is a long corridor between the switch and the bulb room. One cannot see the contents/state in one room being in another room. It is not known which switch corresponds to which bulb. Assume that you are initially in the switch room, all switches are off, and hence all bulbs are off. How do you find the one-to-one correspondence between the switches and the bulbs minimizing the number of trips to the light room? Extensively use diagrams and tables to explain your method/approach.
[15 points] We want to measure any integer weight in the range [1, 30] using a two-sided weighing balance using a minimum number of weights. Explain how can we solve the problem assuming: (a) we can place weights only on one side, and (b) we can place weights on either side of the weighing balance.
[10 points] Explain in detail: (i) What is your favorite puzzle (irrespective of whether it is covered in this course or not) and why? and (ii) What puzzle-solving techniques did you learn in this course?