More Problems

You are trapped in a room with 10 gumball machines, lots of change, and one digital scale that weighs things in ounces.  Nine of the machines contain gumballs that all weigh exactly one ounce, but one machine is defective and its gumballs weigh only half an ounce.  The scale is highly accurate, but can only be used once.  You have to figure out which gumball machine is defective.  The defective gumballs look, feel, and taste just like normal gumballs.

You can drop a nut from any floor of a 100-story building.  A nut will always break when dropped from higher than a certain unknown threshold floor.  You have two identical nuts, and you can experiment by dropping them from different floors, but once a nut is broken, you can’t use it again.  Present an algorithm to find the threshold floor that uses as few drops as possible in the worst case.


Start with 5 short pieces of string.  Pick two ends at random and join them.  Pick two more ends at random and join them.  Keep doing this until there are no more free ends.  What is the expected number of closed loops?  (Think of the “expected number” of closed loops as the average number of loops, if a large number of people each have 5 pieces of string and each carry out this process.  Since it is an average, it may not be a whole number.)