Homework 1

Question 1 [25 points]

 (a) In a certain secret government biology lab, the mad scientists have cloned a giant rat with 100 arms. Unfortunately, this rat turned out to be super powerful, and effectively immortal. It is impervious to all damage, except for its arms. But even if you cut off some arms, they just grow back! Even worse, it has broken loose, and now it is terrorizing the campus!

Fortunately a Hero from the IT Department has fashioned a laser pointer into a mighty weapon that can cut off some of the rat's arms. This laser has four settings, that allow the Hero to cut off 16, 17, 20, or 5 arms. And, because it is such a mighty weapon, not all of the arms will grow back. (Or perhaps even more arms will grow back!) Only 22, 2, 14, or 19 arms will grow back, respectively. (In other words, if the Hero cuts off 16 arms, then 22 new arms will grow back; if the Hero cuts off 17 arms, then only 2 new arms will grow back, and so on.) The rat can be contained only if all of his arms are cut off, and the last swing of the laser must cut off exactly the number of arms cut by that setting, meaning in this case 16, 17, 20, or 5 arms. (There is a perfectly logical bio-mechanical explanation for all of this. But since it is too complicated to explain here, as a concession to the political times that we live in, we'll just call it magic and move on.)

Is it possible to contain the rat? Either show a series of swings that brings the number of the rat's arms to 0, or explain why it is not possible.

b) Assume that things had been different, that the IT Hero's laser had settings to cut off 12, 17, 20, or 5 arms, with 21, 2, 14, or 17 arms growing back, respectively. In this scenario, can the rat be contained?

Question 2 [25 points]

For an engineering class project, you are assigned to create a container that can safely allow water balloons to fall from as high as possible. Part of the assignment is to test the container. Suppose your campus has a special building, built for the purpose (this is a very advance Engineering campus, with buildings built to contain special sensors for water balloon testing). This building has 36 floors. Now, ideally your device would let the water balloon fall from 36 floors without breaking, but very few students in history have ever made a container
that works at this height). There are some rules to the testing, as follows.

• If the water balloon survives a drop, then it can be used again for another test.
• But, if the water balloon breaks, then of course it cannot be used again.
• If a balloon would break when dropped from a given floor, then it would also break if dropped from a higher floor.
• If a balloon can survive when dropped from some floor, then it would also be safe to drop from a lower floor.
  
  

It is possible that your container will break the balloon even when dropped from the first floor, or it is possible that it will work even for floor 36. Now, if you only had one balloon, then you really could not do anything other than start from Floor 1 and work your way up sequentially. But, assume that you have two water balloons available for testing. You must devise some testing order that allows you to determine the lowest floor at which the balloon will break, using the least number of balloon drops in the worst case, no matter which floor happens to be the lowest breaking floor.