|
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)
|
|
