CS4104 Homework Assignment 1

Due at 11:00pm on Wednesday, September 1
30 Points

See the General Guidelines for homework assignments.

1. A knight fights a dragon with 100 heads. The knight can cut off 15, 17, 20, or 5 heads with one blow of his sword; however, in each of these cases a number of new heads will immediately grow back: 24, 2, 14, or 17 heads, respectively. (In other words, if the knight cuts off 15 heads, then 24 new heads will grow back; if the knight cuts off 17 heads, then only 2 new heads will grow back, and so on). The dragon dies only if all of his heads are cut off (and the last blow of the sword must cut off exactly 15, 17, 20, or 5 heads). Is it possible to kill the dragon? Either show a series of cuts that kills the dragon, or explain why it is not possible.

2. Suppose you wish to know which floors in a 36-story building are safe to drop eggs from (in a special egg-dropping container) and which will cause the eggs to break on landing. We assume the following:

• An egg that survives a drop can be used again (no harm is done, and the egg is not weaker).
• A broken egg cannot be used again.
• If an egg breaks when dropped from some floor, it would also break if dropped from any higher floor.
• If an egg survives a fall when dropped from some floor, it would also survive if dropped from a lower floor.

We know nothing in advance about which floor will cause eggs to break: Possibly the eggs break on floor 1, or don't even break on floor 36. If you had only one egg, the only thing you could do is start at floor 1 and go up until the egg breaks. If it breaks on floor n, that would need n tries (up to 36).

Now, assume that you have two eggs. You are to devise a process that allows you to determine the egg-breaking floor, using the least possible number of egg drops in the worst case, no matter which floor it is.