Answers to Brain Teasers

 

 

Rowboat and Rock Problem

When in the boat, the rock displaces an amount of water equal to its weight (Archimedes' Principle).  When in the water, the rock displaces an amount of water equal to its volume.  We know that the rock is denser than water, because it sinks.  Therefore, it displaces less water than it did before, so the level in the tank goes down.

Backlinked List Detection

Imagine a sinuous racetrack receding into the misty distance.  Does the track loop back on itself at some point or not?  One geeky way to find out is to race two cars, a fast one and a slow one.  If the track isn't a loop, the slower car will always trail the faster car, and when the faster car reaches the finish line, we'll have our answer.  On the other hand, if at some point the fast car catches the slow car from behind, we know the track is "back-linked."

Expressed in code: In a forever loop, traverse the list using two pointers.  With each iteration, advance one of the pointers (the fast car) by two nodes and the other pointer by a single node.  Since it's moving half as fast through the list, the singly-incremented pointer should never catch the doubly-incremented pointer, and therefore should never point to the same node (i.e., have the same value). If they ever do point to the same node, it's because the fast pointer has taken a backlink and overtaken the slow pointer from behind.  If the fast pointer reaches a terminating node before discovering this condition, the list is okay.  For example, in C++:

typedef struct 
{
    int value;
    MYNODE * pNext;
} MYNODE;

BOOL ListIsHealthy( MYNODE * pHead )
{
    MYNODE * pSlow = pHead;	
    MYNODE * pFast = pHead;	
    while ( TRUE )
    {
        for ( int i = 0; i < 2; i++ )
	{
            pFast = pFast->pNext;	
	    if ( pFast == NULL )       // got all the way to 
	        return TRUE;	     /   the  end, so list is OK	
	    else if ( pFast == pSlow ) // fast overtook slow, so
	        return FALSE;	      // list is  backlinked
        }
	pSlow = pSlow->pNext;
    }
}

Reversing Sentences

First reverse each character in the string without worrying about words.  This yields: "depmuj xof nworb kciuq ehT"  Then, using space as the delimiter, find the start and end points of individual words and reverse each a second time.

Fair Slicing

Hint: All straight lines bisecting a rectangle must pass through the center of a rectangle, and conversely, all lines that pass through the center of a rectangle bisect the rectangle.

Cut the cake on a line connecting the center of the cake and the center of the missing slice.  This works even for interior slices.

Manhole Cover Geometry

If they were any other shape, they could fall into the hole.  1/4 credit:  Round manhole covers can be rolled.

Gas Stations

I'd work the problem like this.  In my town, greater Santa Cruz, California, there are about 40 gas stations (7 or 8 on Mission, 7 or 8 on Ocean, maybe 10 in Scotts Valley/Felton.  Add 15 more for stations hidden here and there.  Our metro population is about 100,000.  The US population is 260,000,000, about 2600 multiples of our population, yielding a rough estimate of 2600 * 40 = 100,000 gas stations nationwide.  I'd double this to account for highways, less densely populated areas of the country, and my intuition that other places I've lived in have more gas stations per capita than here, to a total of 200,000 stations nationwide. 

Tennis Balls

Here's a back-of-the-envelope calculation that may or may not be correct to within an order of magnitude:  A sphere has a volume of 4/3 π r3.  So a, uh, 3 inch tennis ball has a volume of about 14 cubic inches.  Ahem. Assume the Rose Bowl is a slice of a sphere perhaps, wild guess, 250 yards in diameter.  A sphere 9000 inches in diameter has a volume of 4 x 1011 cubic inches.  The Rose Bowl isn't a sphere, it isn't half of a sphere, it's maybe, ah, wild guess, 1/8th of a sphere, with a volume of 5 x1010 cubic inches.  Ignoring the spaces between balls, about  50,000,000,000 / 14 = about 3 billion tennis balls would fit in the Rose Bowl.  For some reason, that feels low to me.

Evolution and the Egg

Not even Bill or Paul know for sure, but egg-shaped is a variation on the sphere, the strong, efficient, birth-canal-friendly shape that encloses maximum volume with a given surface area.  One might speculate that egg-shaped eggs, unlike spherical or symmetrically elongated variations thereof, don't roll out of the nest as easily.

From the peanut gallery at Fark.com:    "... The egg-shaped-means-it-doesn't-roll thing is a myth. If you investigate a range of bird species, there is a correlation between number of eggs laid and shape of egg, in that you can use the first to deduce the second. If it was such a huge advantage that egg-shaped doesn't roll, birds which laid a single egg would lay an egg-shaped egg. They don't. QED."  --Chris Hind

Measuring Quarts

Fill the three quart jug to the brim and pour it into the empty five quart amorphous container.  Now refill the three quart jug, and pour as much as will fit into the five quart jug.  One quart remains in the three quart jug.  Now dump out the larger jug, and pour the quart into it.  Fill the three quart jug a final time, and add it to the quart in the larger container.  That makes four.

 

 

Answer to Food for Thought Problem

Chicken McNuggets come in packages of 6, 9, and 20. What is the largest number of Chicken McNuggets that you cannot buy?

First a simpler case.  Suppose nuggets just came 3 and 10 to a package. Then the largest number you cannot buy is 17. To see this, suppose you want to buy n nuggets, n >= 20. Let k := n mod 3 (i.e., the remainder when n is divided by 3).  Then n-10k is divisible by 3, and so you just buy k 10-packs and the difference in 3-packs.   Thus you can buy all amounts >= 20.  A simple check shows you can also buy 18 and 19, but not 17.

Now, the original problem.  We want to buy n nuggets using 6, 9, and 20.  If n is even and >34, just divide by 2 and the above analysis show you can buy it with just the 6 and 20s. If n is odd, it suffices to assume that there is just one 9-pack.   There must be at least 1 since 6s and 20s will only give even numbers.  And 2 9s could also be obtained as 6 3s. Looking at (n-9)/2 again reduces it to the previous problem, so the maximum is when (n-9)/2=17, or n=43.   (Proof by Roger Schlafly)

 

Home Up

www.CharlieAnderson.com    Since 1998, Your Home for Charlie Anderson Information    Send me email: info@charlieanderson.com 


All Content 1998-2002 Charles R. Anderson    This page was last modified on 11/13/2003