"silver" coins of the same weight. One of them is however fake and it weighs less. In other words we have silver coins of equal weight and one fake of lesser weight. We also have a balance scale. We can put any number of coins on each side of the scale at the same time, and the scale will indicate whether the two sides are the same weight or which side is lighter.Suppose we have
Suppose we devise an algorithm that locates the fake coin using the balance scale as few times as possible. What is the maximum number of weighing operations necessary to find the odd coin out?
How many weighing operations would be required for 243 coins if we are as unlucky as possible but we use the optimal algorithm?
Consider the task of drawing the markings on a ruler: there is a mark at the halfway point, slightly shorter marks at the quarter intervals and still shorter marks at the eighth intervals. If our desired precision is (arbitrary units), we put a mark at every point between and . The middle mark should be units high the quarter marks should be high, etc. Assuming we have a function
mark(x, h) to make a mark units high at position , the following program does the job of marking a ruler:
1 2 3 4 5 6 7 8
rule(left, right, height) is recursive we know that it will call itself. Suppose that we call
rule(left=0, right=2**10, height=10). During recursive call number to
rule (do not include the initial user call), it will make a mark at position . What is the value of ?
The Pascal triangle, shown below, has an interesting property. Every entry is equal to the sum of the two entries above it, except along the left and right edges where the value is always equal to .
Write a recursive algorithm that outputs the sum of the numbers on each line. For example the sum of the numbers on the rd line is . What is the sum of the numbers on the rd line?
1 2 3 4 5
Consider the above recursive algorithm, predict what it will output when .
1 2 3 4 5 6 7
Consider the square grid above. Suppose a person wants to move from the top left corner towards the bottom right corner. To move, a person can go down or right. Let be the path traversed such that the sum of the cells in the path is minimized. What is the value of ?