|
Archive-name: puzzles/archive/geometry/part1
Last-modified: 17 Aug 1993 Version: 4 See reader questions & answers on this topic! - Help others by sharing your knowledge
==> geometry/K3,3.p <==
Can three houses be connected to three utilities without the pipes crossing?
_______ _______ _______
| oil | |water| | gas |
|_____| |_____| |_____|
_______ _______ _______
|HOUSE| |HOUSE| |HOUSE|
| one | | two | |three|
==> geometry/K3,3.s <==
The problem you describe is to draw a bipartite graph of 3 nodes
connected in all ways to 3 nodes, all embedded in the plane. The graph
is called K3,3. A famous theorem of Kuratowsky says that all graphs
can be embedded in the plane, EXCEPT those containing a subgraph that
is topologically equivalent to K3,3 or K5 (the complete graph on 5
vertices, i.e., the graph with 5 nodes and 10 edges). So your problem
is a minimal example of a graph that cannot be embedded in the plane.
The proofs that K5 and K3,3 are non-planar are really quite easy, and
only depend on Euler's Theorem that F-E+V=2 for a planar graph. For
K3,3 V is 6 and E is 9, so F would have to be 5. But each face has at
least 4 edges, so E >= (F*4)/2 = 10, contradiction. For K5 V is 5 and
E is 10, so F = 7. In this case each face has at least 3 edges, so E >=
(F*3)/2 = 10.5, contradiction.
The difficult part of Kuratowsky is the proof in the other direction!
A quick, informal proof by contradiction without assuming Euler's Theorem:
Using a map in which the houses are 1, 2, and 3 and the utilities are
A, B, and C, there must be continuous lines that connect the buildings and
divide the area into three sections bounded by the loops A-1-B-2-A,
A-1-B-3-A, and A-2-B-3-A. (One of the areas is the infinite plane *around*
whichever loop is the outer edge of the network.) C must be in one of these
three areas; whichever area it is in, either 1, or 2, or 3, is *not* part of
the loop that rings its area and hence is inaccessible to C.
The usual quibble is to solve the puzzle by running one of the pipes
underneath one of houses on its way to another house; the puzzle's
instructions forbid crossing other *pipes*, but not crossing other *houses*.
==> geometry/bear.p <==
If a hunter goes out his front door, goes 50 miles south, then goes 50
miles west, shoots a bear, goes 50 miles north and ends up in front of
his house. What color was the bear?
==> geometry/bear.s <==
The hunter's door is in one of two locations. One is a foot or so from the
North Pole, facing north, such that his position in front of the door is
precisely upon the North Pole. Since that's a ridiculous place to build a
house and since bears do not roam within fifty miles of the pole, the bear
is either imaginary or imported, and there is no telling what color it is.
There is another place (actually a whole set) on earth from which one
can go fifty miles south, fifty miles west, and fifty miles north and
end up where one started. Consider the parallel of latitude close
enough to the South Pole that its length is 50/n miles, for some
integer n.
Take any point on that parallel of latitude and pick the point fifty miles
north of it. Situate the hunter's front porch there. The hunter goes fifty
miles south from his porch and is at a point we'll call A. He travels fifty
miles west, circling the South Pole n times, and is at A again, where he shoots
the bear. Fifty miles north from A he is back home. Since bears are not
indigenous to the Antarctic, again the bear is either imaginary or imported
and there is no telling what color it might be.
==> geometry/bisector.p <==
Prove if two angle bisectors of a triangle are equal, then the triangle is
isosceles (more specifically, the sides opposite to the two angles
being bisected are equal).
==> geometry/bisector.s <==
PROVE: <ABC = <BCA (i.e. triangle ABC is an isosceles triangle)
A
/ \
/ \
D E XP normal to AB
/ \ / \ XQ normal to AC
P /----X----\ Q
/ / \ \
/ / \ \
/ / \ \
B/_______________\C
PROOF :
Let XP and XQ be normals to AC and AB.
Since the three angle bisectors are concurrent, AX bisects angle A
also and therefore XP = XQ.
Let's assume XD > XE.
Then ang(PDX) < ang(QEX)
Now considering triangles BXD and CXE,
the last condition requires that
ang(DBX) > ang(ECX)
OR ang(XBC) > ang(XCB)
OR XC > XB
Thus our assumption leads to :
XC + XD > XE + XB
OR CD > BE
which is a contradiction.
Similarly, one can show that XD < XE leads to a contradiction too.
Hence XD = XE => CX = BX
From which it is easy to prove that the triangle is isosceles.
-- Manish S Prabhu (mprabhu@magnus.acs.ohio-state.edu)
==> geometry/calendar.p <==
Build a calendar from two sets of cubes. On the first set, spell the
months with a letter on each face of three cubes. Use lowercase
three-letter English abbreviations for the names of all twelve months
(e.g., "jan", "feb", "mar"). On the second set, number the days with a
digit on each face of two cubes (e.g., "01", "02", etc.).
==> geometry/calendar.s <==
First note that there are *nineteen* different letters in the
month abbreviations (abcdef gjlmno prstuv y) so to get them all on the
eighteen faces of 3 cubes, you know right away you're going to have to
resort to trickery.
So I wrote them all down and looked at which ones could be
reversed to make another letter in the set. The only pair that jumped
out at me was the d/p pair. Now I knew that it was at least feasible,
as long as it wasn't necessary to duplicate any letters.
Then I scanned the abbreviations to find ones that had a lot of
common letters. The jan-jun-jul series looked like a good place to
start:
j a n
u l
was a good beginning but I realized
right away that I had no room for duplicate letters and the second cube
had both a and u so aug was going to be impossible. In fact I almost
posted that answer. Then I realized that if Martin Gardner wrote about
it, it must have a solution. :-) So I went back to the letter list.
I don't put tails on my u's so it didn't strike me the first
time through that n and u could be combined.
Cube 1 Cube 2 Cube 3
j a n/u
n/u l
would let me get away with putting the g
on the first cube to get aug, so I did.
j a n/u
g n/u l (1)
Now came the fun part. The a was placed so I had to work around
it for the other months that had an a in them (mar, apr, may).
m a r
d/p y (2)
Now the d/p was placed so I had to work around that for sep and dec.
This one was easy since they shared an e as well.
d/p e s
c (3)
Now the e was placed so feb had to be worked in.
f e b (4)
The two months left (oct, nov) were far more complex. Not only
did they have two "set" letters (c, n/u), there were two possible n/u's
to be set with. That's why I left them for last.
o t c
n/u v (5)
So now I had five pieces to fit together, so that no set would
have more than six letters in it. Trial and error provided:
j a n/u a b e
g n/u l or, c d/p g
r s m alphabetically: f l j
y c d/p n/u m o
e v t s n/u r
o f b v t y
Without some gimmick the days cannot be done. Because of the dates 11 and
22, there must be a 1 and a 2 on each cube. Thus there are 8 remaining spaces
for the 8 remaining numbers, and because of 30, we put 3 and 0 on different
cubes. I don't think the way you allocate the others matter. Now 6 numbers on
each cube can produce at most 36 distinct pairs, and we need 31 distinct pairs
to represent all possible dates. But since 3 each of {4,5,6,7,8,9} are on each
cube, there are at least 9 representable numbers which can't be dates.
Therefore there are at most 27 distinct numbers which are dates on the two
cubes, and it can't be done. In particular, not all of {04,05,06,07,08,09} can
be represented.
The gimmick solution would be to represent the numbers in a stylised format
(like say, on a digital clock or on a computer screen) such that the 6 can be
turned upside down to be a 9. Then you can have 012 on both cubes, and three
each of {3,4,5,6,7,8} on the other faces. Done.
Example: 012468 012357
==> geometry/circles.and.triangles.p <==
Find the radius of the inscribed and circumscribed circles for a triangle.
==> geometry/circles.and.triangles.s <==
Let a, b, and c be the sides of the triangle. Let s be the
semiperimeter, i.e. s = (a + b + c) / 2. Let A be the area
of the triangle, and let x be the radius of the incircle.
Divide the triangle into three smaller triangles by drawing
a line segment from each vertex to the incenter. The areas
of the smaller triangles are ax/2, bx/2, and cx/2. Thus,
A = ax/2 + bx/2 + cx/2, or A = sx.
We use Heron's formula, which is A = sqrt(s(s-a)(s-b)(s-c)).
This gives us x = sqrt((s-a)(s-b)(s-c)/s).
The radius of the circumscribed circle is given by R = abc/4A.
==> geometry/coloring/cheese.cube.p <==
A cube of cheese is divided into 27 subcubes. A mouse starts at one
corner and eats each subcube, one at a time. Can it finish in the middle?
==> geometry/coloring/cheese.cube.s <==
Give the subcubes a checkerboard-like coloring so that no two adjacent
subcubes have the same color. If the corner subcubes are black, the
cube will have 14 black subcubes and 13 white ones. The mouse always
alternates colors and so must end in a black subcube. But the center
subcube is white, so the mouse can't end there.
==> geometry/coloring/triominoes.p <==
There is a chess board (of course with 64 squares). You are given 21
"triominoes" of size 3-by-1 (the size of an individual square on a
chess board is 1-by-1). Which square on the chess board can you cut out
so that the 21 triominoes exactly cover the remaining 63 squares? Or is
it impossible?
==> geometry/coloring/triominoes.s <==
||||||||
||||||||
||||||||
---***+*
---...+*
---*+O+*
---*+...
---*+***
There is only one way to remove a square, aside from rotations and
reflections. To see that there is at most one way, do this: Label
all the squares of the chessboard with A, B or C in sequence by rows
starting from the top:
ABCABCAB
CABCABCA
BCABCABC
ABCABCAB
CABCABCA
BCABCABC
ABCABCAB
CABCABCA
Every triomino must cover one A, one B and one C. There is one extra
A square, so an A must be removed. Now label the board again by
rows starting from the bottom:
CABCABCA
ABCABCAB
BCABCABC
CABCABCA
ABCABCAB
BCABCABC
CABCABCA
ABCABCAB
The square removed must still be an A. The only squares that got
marked with A both times are these:
........
........
..A..A..
........
........
..A..A..
........
........
==> geometry/construction/4.triangles.6.lines.p <==
Can you construct 4 equilateral triangles with 6 toothpicks?
==> geometry/construction/4.triangles.6.lines.s <==
Use the toothpicks as the edges of a tetrahedron.
==> geometry/construction/5.lines.with.4.points.p <==
Arrange 10 points so that they form 5 rows of 4 each.
==> geometry/construction/5.lines.with.4.points.s <==
Draw a 5 pointed star, put a point where any two lines meet.
==> geometry/construction/square.with.compass.p <==
Construct a square with only a compass and a straight edge.
==> geometry/construction/square.with.compass.s <==
Draw a circle (C1 at P1). Now draw a diameter D1 (intersects at P2 and
P3). Set the compass larger than before. From each of points P2 and
P3 draw another larger circle (C2 and C3). Where these two circles
cross, draw a line (D2). This line should go through the center of
circle C1 at a right angle to the original diameter line. This line
should cross circle C1 at P4 and P5. Points P2, P4, P3, P5 form a
square.
For extra credit:
Reset the compass to its original size. From P2 and P4 draw a circle
(C4 and C5). These circles intersect at P6 and P1. Connect P6, P2,
P1, P4 for a square of the same size as the original compass setting.
==> geometry/corner.p <==
A hallway of width A turns through 90 degrees into a hallway of width
B. A ladder is to be passed around the corner. If the movement is
within the horizontal plane, what is the maximum length of the ladder?
==> geometry/corner.s <==
------\---------
B / \.......|..B/sin(theta)
theta\ |
---|-----X |
|\ |
| \...|..A/cos(theta)
| \ |
| \ |
| A \|
Theta is the angle off horizontal.
Minimize length = A/cos(theta) + B/sin(theta)
d(length)/d(theta)
= A*sin(theta)/cos(theta)^2 - B*cos(theta)/sin(theta)^2 (?)
= 0
A*sin(theta)/cos(theta)^2 = B*cos(theta)/sin(theta)^2
B/A = sin(theta)^3/cos(theta()^3 = tan(theta)^3
theta = inverse_tan(cube_root(B/A))
If you use the trigonometric formulas cos^2 x = 1/(1 + tan^2 x)
and sin x = tan x cos x, and plug through the algebra, I believe
that the formula for the length reduces to
(A^(2/3) + B^(2/3))^(3/2)
At any rate this is symmetric in A and B as one would expect, and
has the right values at A=B and as either A-->0 or B-->0.
==> geometry/cover.earth.p <==
A thin membrane covers the surface of the (spherical) earth. One
square meter is added to the area of this membrane to form a larger
sphere. How much is added to the radius and volume of this membrane?
==> geometry/cover.earth.s <==
We know that V = (4/3)*pi*r^3 and A = 4*pi*r^2.
We need to find out how much V increases if A increases by 1 m^2.
dV / dr = 4 * pi * r^2
dA / dr = 8 * pi * r
dV / dA = (dV / dr) / (dA / dr)
= (4 * pi * r^2) / (8 * pi * r)
= r/2
= 3,250,000 m
If the area of the cover is increased by 1 square meter,
then the volume it contains is increased by about 3.25 million cubic meters.
We seem to be getting a lot of mileage out of such a small square of cotton.
However, the new cover would not be very high above the surface of the
planet -- about 6 nanometers (calculate dr/dA).
==> geometry/cycle.polynomial.p <==
What are the cycle polynomials for the Platonic solids?
==> geometry/cycle.polynomial.s <==
For future reference, here are the cycle polynomials for the five platonic
solids (and I threw in the tesseract for good measure). Most combinatoric
coloring problems are simple plug-ins to these polynomials. For details,
see any book on combinatorics that presents Polya counting theory.
tetrahedron: (x1^4+3x2^2+8x1*x3)/12
cube: (x1^6+6x2^3+3x1^2*x2^2+8x3^2+6x1^2*x4)/24
octahedron: (x1^8+9x2^4+8x1^2*x3^2+6x4^2)/24
dodecahedron: (x1^12+15x2^6+20x3^4+24x1^2*x5^2)/60
icosahedron: (x1^20+15x2^10+20x1^2*x3^6+24x5^4)/60
tesseract: (32x6^4+x2^12+48x8^3+x1^24+24x1^2*x2^11+12x2^2*x4^5+32x3^8+12x4^6
+18x1^4*x2^10+12x1^4*x4^5)/192
==> geometry/dissections/disk.p <==
Can a disk be cut into similar pieces without point symmetry about the
midpoint? Can it be done with a finite number of pieces?
==> geometry/dissections/disk.s <==
Yes. Draw a circle inside the circumference of the disk, sharing a
common point on the right. Now draw another circle inside the second,
sharing a point at the left. Now draw another inside the third,
sharing a point at the right. Continue in this way, coloring in every
other region thus generated. Now, all the colored regions touch, so
count this as one piece and the uncolored regions as a second piece.
So the circle has been divided into two similar pieces and there is no
point symmetry about the midpoint. Maybe it is cheating to call these
single pieces, though.
==> geometry/dissections/hexagon.p <==
Divide the hexagon into:
1) 3 identical rhombuses.
2) 6 identical kites(?).
3) 4 identical trapezoids (trapeziums in Britain).
4) 8 identical shapes (any shape).
5) 12 identical shapes (any shape).
==> geometry/dissections/hexagon.s <==
What is considered 'identical' for these questions? If mirror-image shapes
are allowed, these are all pretty trivial. If not, the problems are rather
more difficult...
1. Connect the center to every second vertex.
2. Connect the center to the midpoint of each side.
3. This is the hard one. If you allow mirror images, it's trivial:
bisect the hexagon from vertex to vertex, then bisect with a
perpendicular to that, from midpoint of side to midpoint of side.
4. This one's neat. Let the side length of the hexagon be 2 (WLOG).
We can easily partition the hexagon into equilateral triangles
with side 2 (6 of them), which can in turn be quartered into
equilateral triangles with side 1. Thus, our original hexagon
is partitioned into 24 unit equilateral triangles. Take the
trapezoid formed by 3 of these little triangles. Place one such
trapezoid on the inside of each face of the original hexagon, so
that the long side of the trapezoid coincides with the side of the
hexagon. This uses 6 trapezoids, and leaves a unit hexagon in the
center as yet uncovered. Cover this little hexagon with two of
the trapezoids. Voila. An 8-identical-trapezoid partition.
5. Easy. Do the rhombus partition in #1. Quarter each rhombus by
connecting midpoints of opposite sides. This produces 12 small
rhombi, each of which is equivalent to two adjacent small triangles
as in #4.
Except for #3, all of these partitions can be achieved by breaking up the
hexagon into unit equilateral triangles, and then building these into the
shapes desired. For #3, though, this would require (since there are 24 small
triangles) trapezoids formed from 6 triangles each. The only trapezoid that
can be built from 6 identical triangles is a parallelogram; I assume that the
poster wouldn't have asked for a trapezoid if you could do it with a special
case of trapezoid. At any rate, that parallelogram doesn't work.
==> geometry/dissections/largest.circle.p <==
What is the largest circle that can be assembled from two semicircles cut from
a rectangle with edges a and b?
==> geometry/dissections/largest.circle.s <==
There are two methods:
Method M1:
The diameters of the semicircles have to be on the longer sides,
starting at an endpoint of the rectangle. The two semicircles touch
each other in the middle M of the rectangle.
a
D._______________________.C
| |
| |
b | . M |
| |
| |
|_______.___.___________|
A R X B
R should be the center of the semicircle, and because of RA = RM,
it holds that:
r^2 = (a/2 - r)^2 + (b/2)^2
Solving for r gives:
r = min[b,(a^2+b^2)/(4a)], where a >= b.
Method M2:
We'll cut on the line y = c x, where c will turn out to be slightly
less than d, the slope of the diagonal. We describe the semicircle
lying above the line y = c x, having this line as the straight part of
the semi-circle. The center P of the semicircle will be taken on the
line y = d - x, and will be tangent to the left and top of the
rectangle. Clearly the lower down P is on this line, the better. The
naive solution is not optimal because the upper place where the
semicircle meets the diagonal is interior to the rectangle. So we try
to determine c in such a way that this latter point actually lies
slightly down from the top, on the right side of the rectangle. This
involves solving the quartic:
4r^4 - (4a+16b)r^3 + (16b^2+a^2+8ab)r^2 - (6b^3+4ab^2+2ba^2)r + b^4+(ab)^2 = 0,
where r < b, the details of which will be left to the reader.
The other semicircle is the reflection of the first through the origin.
After a few calculations, we find that the value of r given
by M2 is greater than the one given by M1 only if 1 < a/b < 2.472434.
==> geometry/dissections/square.70.p <==
Since 1^2 + 2^2 + 3^2 + ... + 24^2 = 70^2, can a 70x70 square be dissected into
24 squares of size 1x1, 2x2, 3x3, etc.?
==> geometry/dissections/square.70.s <==
Martin Gardner asked this in his Mathematical Games column in the
September 1966 issue of Scientific American. William Cutler was the first
of 24 readers who reduced the uncovered area to 49, using all but the 7x7
square. All the patterns were the same except for interchanging the
squares of orders 17 and 18 and rearranging the squares of orders 1, ...,
6, 8, 9, and 10. Nobody proved that the solution is minimal.
+----------------+-------------+----------------------+---------------------+
| | | | |
| | | | |
| | 11 | | |
| | | | |
| 16 | | | |
| +-----+--+----+ 22 | 21 |
| | | 2| | | |
| | 5 +--+----+ | |
| | | | | |
+----------------+--+--+ 6 | | |
| | 3| | | |
| ++-+-------+ | |
| || | ++--------------------+
| || 8 +----------------------++ |
| 18 || | | |
| || | | |
| ++---------+ | |
| | | | 20 |
| | 9 | | |
+------------------++ | 23 | |
| || | | |
| ++----------+ | |
| | | +---++---------------+
| | | | || |
| 17 | 10 | | 4 || |
| | +---------------+-------+---++ |
| +-+---------+---------------+ | 15 |
| | | | | |
| | | | 12 | |
+------------------+-+ | +-+-------------+
| | | |1| |
| | +------------+-+ |
| | 24 | | |
| | | | |
| 19 | | 13 | 14 |
| | | | |
| | | | |
| | | | |
+--------------------+-------------------------+--------------+-------------+
==> geometry/dissections/square.five.p <==
Can you dissect a square into 5 parts of equal area with just a straight edge?
==> geometry/dissections/square.five.s <==
1. Prove you can reflect points which lie on the sides of the square
about the diagonals.
2. Construct two different rectangles whose vertices lie on the square
and whose sides are parallel to the diagonals.
3. Construct points A, A', B, B' on one (extended) side of the square
such that A/A' and B/B' are mirror image pairs with respect to another
side of the square.
4. Construct the mirror image of the center of the square in one
of the sides.
5. Divide the original square into 4 equal squares whose sides are
parallel to the sides of the original square.
6. Divide one side of the square into 8 equal segments.
7. Construct a trapezoid in which one base is a square side and one
base is 5/8 of the opposite square side.
8. Divide one side of the square into 5 equal segments.
9. Divide the square into 5 equal rectangles.
==> geometry/dissections/tesseract.p <==
If you suspend a cube by one corner and slice it in half with a
horizontal plane through its centre of gravity, the section face is a
hexagon. Now suspend a tesseract (a four dimensional hypercube) by one
corner and slice it in half with a hyper-horizontal hyperplane through
its centre of hypergravity. What is the shape of the section
hyper-face?
==> geometry/dissections/tesseract.s <==
The 4-cube is the set of all points in [-1,1]^4 .
The hyperplane { (x,y,z,w) : x + y + z + w = 0 } cuts the 4-cube
in the desired manner.
Now, { (.5,.5,-.5,-.5), (.5,-.5,.5,-.5), (.5,-.5,-.5,.5) } is an
orthonormal basis for the hyperplane. Let (a,b,c) be a point on the
hyperplane with respect to this basis. (a,b,c) is in the 4-cube if and
only if |a| + |b| + |c| <= 2. The shape of the intersection is a
regular octahedron.
==> geometry/duck.and.fox.p <==
A duck is swimming about in a circular pond. A ravenous fox (who cannot
swim) is roaming the edges of the pond, waiting for the duck to come close.
The fox can run faster than the duck can swim. In order to escape,
the duck must swim to the edge of the pond before flying away. Assume that
the duck can't fly until it has reached the edge of the pond.
How much faster must the fox run that the duck swims in order to be always
able to catch the duck?
==> geometry/duck.and.fox.s <==
Assume the ratio of the fox's speed to the duck's is a, and the radius
of the pond is r. The duck's best strategy is:
1. Swim around a circle of radius (r/a - delta) concentric with the
pond until you are diametrically opposite the fox (you, the fox, and
the center of the pond are colinear).
2. Swim a distance delta along a radial line toward the bank opposite
the fox.
3. Observe which way the fox has started to run around the circle.
Turn at a RIGHT ANGLE in the opposite direction (i.e. if you started
swimming due south in step 2 and the fox started running to the east,
i.e. clockwise around the pond, then start swimming due west). (Note:
If at the beginning of step 3 the fox is still in the same location as
at the start of step 2, i.e. directly opposite you, repeat step 2
instead of turning.)
4. While on your new course, keep track of the fox. If the fox slows
down or reverses direction, so that you again become diametrically
opposite the fox, go back to step 2. Otherwise continue in a straight
line until you reach the bank.
5. Fly away.
The duck should make delta as small as necessary in order to be able
to escape the fox.
The key to this strategy is that the duck initially follows a
radial path away from the fox until the fox commits to running either
clockwise or counterclockwise around the pond. The duck then turns onto
a new course that intersects the circle at a point MORE than halfway
around the circle from the fox's starting position. In fact, the duck
swims along a tangent of the circle of radius r/a. Let
theta = arc cos (1/a)
then the duck swims a path of length
r sin theta + delta
but the fox has to run a path of length
r*(pi + theta) - a*delta
around the circle. In the limit as delta goes to 0, the duck will
escape as long as
r*(pi + theta) < a*r sin theta
that is,
pi + arc cos (1/a) - a * sqrt(a^2 - 1) < 0
Maximize a in the above: a = 4.6033388487517003525565820291030165130674...
The fox can catch the duck as long as he can run about 4.6 times as fast as
the duck can swim.
"But wait," I hear you cry, "When the duck heads off to that spot
'more than halfway' around the circle, why doesn't the fox just double
back? That way he'll reach that spot much quicker." That is why the
duck's strategy has instructions to repeat step 2 under certain
circumstances. Note that at the end of step 2, if the fox has started
to run to head off the duck, say in a clockwise direction, he and the
duck are now on the same side of some diameter of the circle. This
continues to be true as long as both travel along their chosen paths
at full speed. But if the fox were now to try to reach the duck's
destination in a counterclockwise direction, then at some instant he
and the duck must be on a diameter of the pond. At that instant, they
have exactly returned to the situation that existed at the end of step
1, except that the duck is a little closer to the edge than she was
before. That's why the duck always repeats step 2 if the fox is ever
diametrically opposite her. Then the fox must commit again to go one
way or the other. Every time the fox fails to commit, or reverses his
commitment, the duck gets a distance delta closer to the edge. This
is a losing strategy for the fox.
The limiting ratio of velocities that this strategy works against
cannot be improved by any other strategy, i.e., if the ratio of
the duck's speed to the fox's speed is less than a then the duck
cannot escape given the best fox strategy.
Given a ratio R of speeds less than the above a, the fox is sure to
catch the duck (or keep it in water indefinitely) by pursuing the
following strategy:
Do nothing so long as the duck is in a radius of R around the centre.
As soon as it emerges from this circle, run at top speed around the
circumference. If the duck is foolish enough not to position itself
across from the center when it comes out of this circle, run "the short
way around", otherwise run in either direction.
To see this it is enough to verify that at the circumference of the
circle of radius R, all straight lines connecting the duck to points
on the circumference (in the smaller segment of the circle cut out
by the tangent to the smaller circle) bear a ratio greater than R
with the corresponding arc the fox must follow. That this is enough
follows from the observation that the shortest curve from a point on
a circle to a point on a larger concentric circle (shortest among all
curves that don't intersect the interior of the smaller circle) is
either a straight line or an arc of the smaller circle followed by a
tangential straight line.
==> geometry/earth.band.p <==
How much will a band around the equator rise above the surface if it is
made one meter longer? Assume the equator is a circle.
==> geometry/earth.band.s <==
The formula for the circumference of a circle is 2 * pi * radius. Therefore,
if you increase the circumference by 1 meter, you increase the radius by
1/(2 * pi) meters, or about 0.16 meters.
==> geometry/fence.p <==
A farmer wishes to enclose the maximum possible area with 100 meters of fence.
The pasture is bordered by a straight cliff, which may be used as part of the
fence. What is the maximum area that can be enclosed?
==> geometry/fence.s <==
A circle is the plane figure with highest ratio of area to perimeter.
The cliff can be used to bisect a circle of radius 100/pi meters. By
symmetry, this will form the pen of largest area. The resulting pen
will contain 5000/pi meters squared.
==> geometry/ham.sandwich.p <==
Consider a ham sandwich, consisting of two pieces of bread and one of
ham. Suppose the sandwich was dropped into a machine and spindled,
torn and mutilated. Is it still possible to divide the ham sandwich
with a straight knife cut such that both the ham and each slice of
bread are divided in two parts of equal volume?
==> geometry/ham.sandwich.s <==
Yes. There is a theorem in topology called the Ham Sandwich Theorem,
which says: Given 3 (finite) volumes (each may be of any shape, and in
several pieces), there is a plane that cuts each volume in half. You
would learn about it typically in a first course in algebraic topology,
or maybe in a course on introductory topology (if you studied the
fundamental group).
==> geometry/hike.p <==
You are hiking in a half-planar woods, exactly 1 mile from the edge,
when you suddenly trip and lose your sense of direction. What's the
shortest path that's guaranteed to take you out of the woods? Assume
that you can navigate perfectly relative to your current location and
(unknown) heading.
==> geometry/hike.s <==
Go 2/sqrt(3) away from the starting point, turn 120 degrees and head
1/sqrt(3) along a tangent to the unit circle, then traverse an arc of
length 7*pi/6 along this circle, then head off on a tangent 1 mile.
This gives a minimum of sqrt(3) + 7*pi/6 + 1 = 6.397...
It remains to prove this is the optimal answer.
==> geometry/hole.in.sphere.p <==
Old Boniface he took his cheer,
Then he bored a hole through a solid sphere,
Clear through the center, straight and strong,
And the hole was just six inches long.
Now tell me, when the end was gained,
What volume in the sphere remained?
Sounds like I haven't told enough,
But I have, and the answer isn't tough!
==> geometry/hole.in.sphere.s <==
The volume of the leftover material is equal to the volume of a 6" sphere.
First, lets look at the 2 dimensional equivalent of this problem. Two
concentric circles where the chord of the outer circle that is tangent
to the inner circle has length D. What is the annular area between the
circles?
It is pi * (D/2)^2. The same area as a circle with that diameter.
Proof:
big circle radius is R
little circle radius is r
2 2
area of donut = pi * R - pi * r
2 2
= pi * (R - r )
Draw a right triangle and apply the Pythagorean Theorem to see that
2 2 2
R - r = (D/2)
so the area is
2
= pi * (D/2)
Start with a sphere of radius R (where R > 6"), drill out the 6"
high hole. We will now place this large "ring" on a plane. Next to it
place a 6" high sphere. By Archemedes' theorem, it suffices
to show that for any plane parallel to the base plane, the cross-
sectional area of these two solids is the same.
Take a general plane at height h above (or below) the center
of the solids. The radius of the circle of intersection on the sphere is
radius = srqt(3^2 - h^2)
so the area is
pi * ( 3^2 - h^2 )
For the ring, once again we are looking at the area between two concentric
circles. The outer circle has radius sqrt(R^2 - h^2),
The area of the outer circle is therefore
pi (R^2 - h^2)
The inner circle has
radius sqrt(R^2 - 3^2). So the area of the inner circle is
pi * ( R^2 - 3^2 )
the area of the doughnut is therefore
pi(R^2 - h^2) - pi( R^2 - 3^2 )
= pi (R^2 - h^2 - R^2 + 3^2)
= pi (3^2 - h^2)
Therefore the areas are the same for every plane intersecting the solids.
Therefore their volumes are the same.
QED
There also is a meta-theoretic answer to this puzzle. Assume the puzzle
can be solved. Then it must be solvable with a hole of any diameter, even
zero. But if you drill a hole of zero diameter that is six inches long,
you leave behind the volume of a six inch diameter sphere.
==> geometry/hypercube.p <==
How many vertices, edges, faces, etc. does a hypercube have?
==> geometry/hypercube.s <==
Take any vertex of the hypercube, and ask how many k-V's it
participates in. To make a k-V it needs to combine with k adjacent and
orthogonal vertices, and there are (nCk) distinct ways of doing this
[that is, choose k directions out of n possible ones]. Then multiply
by 2^n, the total number of vertices. But this involves multiple
counting, since each k-V is shared by 2^k vertices. So divide by 2^k,
and this yields the answer: (nCk)*2^{n-k}.
For example, 12d hypercube:
0-v: 4,096
1-v: 24,576
2-v: 67,584
3-v: 112,640
4-v: 126,720
5-v: 101,376
6-v: 59,136
7-v: 25,344
8-v: 7,920
9-v: 1,760
10-v: 264
11-v: 24
12-v: 1
==> geometry/kissing.number.p <==
How many n-dimensional unit spheres can be packed around one unit sphere?
==> geometry/kissing.number.s <==
From the Feb. 1992 issue of Scientific American:
Kissing Numbers
Dimension Lower limit Upper limit
1* 2 2
2* 6 6
3* 12 12
4 24 25
5 40 46
6 72 82
7 126 140
8* 240 240
9 306 380
10 500 595
11 582 915
12 840 1,416
13 1,130 2,233
14 1,582 3,492
15 2,564 5,431
16 4,320 8,313
17 5,346 12,215
18 7,398 17,877
19 10,688 25,901
20 17,400 37,974
21 27,720 56,852
22 49,896 86,537
23 93,150 128,096
24* 196,560 196,560
* = dimensions for which the answer is known.
REFERENCES (from the Sci. Am. article)
The Problem of the Thirteen Spheres. John Leech in Mathematical Gazette,
Vol. 40, No. 331, pages 22-23; February 1956
Sphere Packings, Lattics and Groups. John Horton Conway and Neil J. A.
Sloane. Springer-Verlag, 1988.
Sphere Packings and Spherical Geometry--Kepler's Conjecture and Beyond,
preprint. Wu-Yi Hsiang. Center for Pure and Applied Mathematics,
University of California, Berkeley, July 1991.
--
David Radcliffe
radcliff@csd4.csd.uwm.edu
==> geometry/konigsberg.p <==
Can you draw a line through each edge on the diagram below without crossing
any edge twice and without lifting your pencil from the paper?
+---+---+---+
| | | |
+---+-+-+---+
| | |
+-----+-----+
==> geometry/konigsberg.s <==
This is solved in the same way as the famous "Seven Bridges of
Konigsberg" problem first solved by Euler. In that problem, the task
was to find a closed path that crossed each of the seven bridges of
Konigsberg (now Kaliningrad, Russia) exactly once. For reasons given
below, no such path existed. In this version, you cannot draw such a
line without cheating by:
(1) drawing a line along one of the edges, or
(2) inscribing the diagram on a torus, or
(3) defining a line segment as the entire length of each straight line, or
(4) adding a vertex on one of the line segemnts, or
(5) defining "crossing" as touching the endpoint of a segment.
The method for determining if paths exist in all similar problems is
given below.
Turn each "room" into a point. Turn each line segment into a line
connecting the two points representing the rooms it abuts. You should
be able to see that drawing one continuous line across all segments in
your drawing is equivalent to traversing all the edges in the resulting
graph. Euler's Theorem states that for a graph to be traversable, the
number of vertices with an odd number of edges proceeding from them
must be either zero or two. For this graph, that number is four, and it
cannot be traversed.
+---+---+---+
| 1 | 2 | 3 |
+---+-+-+---+ 6 (outside)
| 4 | 5 |
+-----+-----+
Number of edges proceeding from each vertex:
1: 4
2: 5 (*odd*)
3: 4
4: 5 (*odd*)
5: 5 (*odd*)
6: 9 (*odd*)
To prove Euler's Theorem, think of walking along the graph from vertex to
vertex. Each vertex must be entered as many times as it is exited, except
for where you start and where you end. So, each vertex must have an
even number of edges, except possibly for two vertices. And if there are
two vertices with an odd number of edges, the path must start at one and
end at the other.
==> geometry/ladders.p <==
Two ladders form a rough X in an alley. The ladders are 11 and 13 meters
long and they cross 4 meters off the ground. How wide is the alley?
==> geometry/ladders.s <==
Ladders 1 and 2, denoted L1 and L2, respectively, will rest along two
walls (taken to be perpendicular to the ground), and they will
intersect at a point O = (a,s), a height s from the ground. Find the
largest s such that this is possible. Then find the width of the
alley, w = a+b, in terms of L1, L2, and s. This diagram is not to
scale.
B D
|\ L1 L2 /|
| \ / | BC = length of L1
| \ / | AD = length of L2
| \ O / | s = height of intersection
x| \ / |y A = (0,0)
| /|\ | AE = a
| m / | \ n | EC = b
| / |s \ | AO = m
| / | \ | CO = n
|/________|________\|
(0,0) = A a E b C
-----------------------------------------------------------------------------
Without loss of generality, let L2 >= L1.
Observe that triangles AOB and DOC are similar. Let r be the ratio of
similitude, so that x=ry. Consider right triangles CAB and ACD. By
the Pythagorean theorem, L1^2 - x^2 = L2^2 - y^2. Substituting x=ry,
this becomes y^2(1-r^2) = L2^2 - L1^2. Letting L= L2^2 -L1^2 (L>=0),
and factoring, this becomes
(*) y^2 (1+r)(1-r) = L
Now, because parallel lines cut L1 (a transversal) in proportion, r =
x/y = (L1-n)/n, and so L1/n = r+1. Now, x/s = L1/n = r+1, so ry = x =
s(r+1). Solving for r, one obtains the formula r = s/(y-s).
Substitute this into (*) to get
(**) y^2 (y) (y-2s) = L (y-s)^2
NOTE: Observe that, since L>=0, it must be true that y-2s>=0.
Now, (**) defines a fourth degree polynomial in y. It can be written in the
form (by simply expanding (**))
(***) y^4 - 2s_y^3 - L_y^2 + 2sL_y - Ls^2 = 0
L1 and L2 are given, and so L is a constant. How large can s be? Given L,
the value s=k is possible if and only if there exists a real solution, y',
to (***), such that 2k <= y' < L2. Now that s has been chosen, L and s are
constants, and (***) gives the desired value of y. (Make sure to choose the
value satisfying 2s <= y' < L2. If the value of s is "admissible" (i.e.,
feasible), then there will exist exactly one such solution.)
Now, w = sqrt(L2^2 - y^2), so this concludes the solution.
L1 = 11, L2 = 13, s = 4. L = 13^2-11^2 = 48, so (***) becomes
y^4 - 8_y^3 - 48_y^2 + 384_y - 768 = 0
Numerically find root y ~= 9.70940555, which yields w ~= 8.644504.
==> geometry/lattice/area.p <==
Prove that the area of a triangle formed by three lattice points is integer/2.
==> geometry/lattice/area.s <==
The formula for the area is
A = | x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2 | / 2
If the xi and yi are integers, A is of the form (integer/2)
==> geometry/lattice/equilateral.p <==
Can an equlateral triangle have vertices at integer lattice points?
==> geometry/lattice/equilateral.s <==
No.
Suppose 2 of the vertices are (a,b) and (c,d), where a,b,c,d are integers.
Then the 3rd vertex lies on the line defined by
(x,y) = 1/2 (a+c,b+d) + t ((d-b)/(c-a),-1) (t any real number)
and since the triangle is equilateral, we must have
||t ((d-b)/(c-a),-1)|| = sqrt(3)/2 ||(c,d)-(a,b)||
which yields t = +/- sqrt(3)/2 (c-a). Thus the 3rd vertex is
1/2 (a+c,b+d) +/- sqrt(3)/2 (d-b,a-c)
which must be irrational in at least one coordinate.
==> geometry/manhole.cover.p <==
Why is a manhole cover round?
==> geometry/manhole.cover.s <==
It will not fall into the hole, even if rotated, tipped, etc.
It gives maximal area for a given amount of material.
It does not have to be carried, but can be rolled.
Human beings are roughly round in horizontal cross section.
Orientation of the cover with the access hole is not of concern.
Orientation of the access hole with the ladder in the pipe below is not
of concern.
==> geometry/pentomino.p <==
Arrange pentominos in 3x20, 4x15, 5x12, 6x10, 2x3x10, 2x5x6 and 3x4x5 forms.
==> geometry/pentomino.s <==
I've seen several different naming schemes used for pentominoes. This is
the system I'm using (I think only F & N require a bit of imagination):
FF I L N PP TTT U U V V W W W X X Y ZZ
FF I L NN PP T UUU V V W W X YY Z
F I L N P T V X X Y ZZ
I LL N Y
A 3x20 solution (the other solution is easily obtained by a rotation of
the section from the Z to the L inclusive):
UUXPPPZYYYYWTFNNNVVV
UXXXPPZZZYWWTFFFNNLV
UUXIIIIIZWWTTTFLLLLV
A 4x15 solution:
IIIIINNLLLLTVVV
UUXNNNFZZWLTTTV
UXXXYFFFZWWTPPV
UUXYYYYFZZWWPPP
2 5x6 rectangles. Joined side-to-side, end-to-end, or stacked, these
enable construction of the 6x10 & 5x12 rectangles, and the 2x5x6 prism:
NFVVV YYYYI
NFFFV LLYZI
NNFXV LZZZI
PNXXX LZWTI
PPUXU LWWTI
PPUUU WWTTT
The 2x3x10 and 3x4x5 solutions are tricky to show - I hope these diagrams
make sense:
A 2x3x10 solution (shown as 2 layers; Y and L are shared between the
2 layers):
VVVZIIIIIF UUXTTTWWPP
VZZZNNNFFF UXXXTWWPPP
VZYYYYNNFL UUXYTWLLLL
A 3x4x5 solution (3 layers, V F W & L shared between 2 or more layers):
VUUXF VZFFF VNYFW
VUXXX TZZZW NNYPW
VUUXW TTTZW NYYPP
IIIII TLLLL NLYPP
--
+------------------- pete@bignode.equinox.gen.nz -------------------+
| The effort to understand the universe is one of the very few things |
| that lifts human life above the level of farce, and gives it some |
| of the grace of tragedy - Steven Weinberg |
+---------------------------------------------------------------------+
==> geometry/points.in.sphere.p <==
What is the expected distance between two random points inside a sphere?
Assume the points are uniformly and independently distributed.
==> geometry/points.in.sphere.s <==
Use spherical polar coordinates, and w.l.o.g. choose the polar axis
through one of the points. Now the distance between the two points is
sqrt ( r1^2 + r2^2 - 2 r1 r2 cos(theta))
and cos(theta) is (conveniently) uniformly distributed between -1 and
+1, while r1 and r2 have densities 3 r1^2 d(r1) and 3 r2^2 d(r2). Split
the total integral into two (equal) parts with r1 < r2 and r1 > r2, and
it all comes down to integrating polynomials.
More generally, the expectation of the n'th power of the distance
between the two points is
2^n . 72 / ((n+3)(n+4)(n+6))
So the various means are:
the (arithmetic) mean distance is 36/35 = 1.028571...
the root mean square distance is sqrt(6/5) = 1.095445...
the geometric mean distance is 2exp(-3/4) = 0.944733...
the harmonic mean distance is 5/6 = 0.833333...
the inverse root mean inverse square distance is
2/3 = 0.666666...
==> geometry/points.on.sphere.p <==
What are the odds that n random points on a sphere lie in the same hemisphere?
==> geometry/points.on.sphere.s <==
1 - [1-(1/2)^(n-2)]^n
where n is the # of points on the sphere.
The question will become a lot easier if you restate it as the following:
What is the probability in finding at least one point such that all the other
points on the sphere are on one side of the great circle going through this
point.
When n=2, the probability= 1 ,
when n=infinity, it becomes 0.
In his Scientific American column which was titled "Curious Maps",
Martin Gardner ponders the fact that most of the land mass of the Earth
is in one hemisphere and refers to a paper which models continents
by small circular caps. He gives the above result.
See "The Probability of Covering a Sphere With N Circular Caps" by
E. N. Gilbert in Biometrika 52, 1965, p323.
==> geometry/revolutions.p <==
A circle with radius 1 rolls without slipping once around a circle with radius
3. How many revolutions does the smaller circle make?
==> geometry/revolutions.s <==
4 if the smaller circle rolls on the outside of the larger circle; 2 if
it rolls on the inside.
Imagine you are rolling a wheel by pushing it along the equator of the
earth. Suppose the circumference of the wheel is one third of that of
the earth. By the time you return to your starting point, the wheel
finishes 3 revolutions relative to you. But do not forget you yourself
also finishes 1 revolution in the same direction. As a result, the
number of absolute revolutions is 3+1=4.
But if the small circle is rolling inside the large circle, the answer
is then 3-1=2, because in this case the wheel makes a counter-revolution
as you walk once around.
==> geometry/rotation.p <==
What is the smallest rotation that returns an object to its original state?
==> geometry/rotation.s <==
720 degrees.
Objects are made of bosons (integer-spin particles) and fermions
(half-odd-integer spin particles), and the wave function of a fermion
changes sign upon being rotated by 360 degrees. To get it back to its
original state you must rotate by another 360 degrees, for a total of
720 degrees. This fact is the basis of Fermi-Dirac statistics, the
Pauli Exclusion Principle, electron orbits, chemistry, and life.
Mathematically, this is due to the continuous double cover of SO(2) by
SO(3), where SO(2) is the internal symmetry group of fermions and SO(3)
is the group of rotations in three dimensional space.
A fermion can be modeled by a sphere with strings attached. It is
possible to see that a 360 degree rotation will entangle the strings,
which another 360 degree rotation will disentangle. You can also
demonstrate this with a tray, which you hold in your right hand with
the arm lowered, then rotate twice as you raise your arm and end up
with the tray above your head, rotated twice about its vertical axis,
but without having twisted your arm.
Hospitals have machines which take out your blood, centrifuge it to take out
certain parts, then return it to your veins. Because of AIDS they must never
let your blood touch the inside of the machine which has touched others'
blood. So the inside is lined with a single piece of disposable branched
plastic tubing. This tube must rotate rapidly in the centrifuge where
several branches come out. Thus the tube should twist and tangle up the
branches. But the machine untwists the branches as in the above discussion.
At several hundred rounds per minute!
References
R. Penrose and W. Rindler
Spinors and Space-time, vol. 1, p. 43
Cambridge University Press, 1984
R. Feynman and S. Weinberg
Elementary Particles and the Laws of Physics, p. 29
Cambridge University Press, 1987
M. Gardner
The New Ambidextrous Universe, Revised (Third) Edition, pp. 329-332
W. H. Freeman, 1990
==> geometry/shephard.piano.p <==
What's the maximum area shape that will fit around a right-angle corner?
==> geometry/shephard.piano.s <==
This problem is unsolved. A simple solution called the "Shephard
piano" has area 2.2074+, but this can be improved upon with local
modifications. A solution exists with area 2.215649+. It is known
that a maximum area exists, but not whether the shape achieving it is
symmetric, smooth, or even unique.
See Problem G5 in Croft, Falconer, and Guy, _Unsolved Porblems in
Geometry_, Springer-Verlag, 1991.
==> geometry/smuggler.p <==
Somewhere on the high sees smuggler S is attempting, without much
luck, to outspeed coast guard G, whose boat can go faster than S's. G
is one mile east of S when a heavy fog descends. It's so heavy that
nobody can see or hear anything further than a few feet. Immediately
after the fog descends, S changes course and attempts to escape at
constant speed under a new, fixed course. Meanwhile, G has lost track
of S. But G happens to know S's speed, that it is constant, and that S
is sticking to some fixed heading, unknown to G.
How does G catch S?
G may change course and speed at will. He knows his own speed and
course at all times. There is no wind, G does not have radio or radar,
there is enough space for maneuvering, etc.
==> geometry/smuggler.s <==
One way G can catch S is as follows (it is not the fastest way).
G waits until he knows that S has traveled for one mile. At that time, both
S and G are somewhere on a circle with radius one mile, and with its center
at the original position of S. G then begins to travel with a velocity that
has a radially outward component equal to that of S, and with a tangential
component as large as possible, given G's own limitation of total speed. By
doing so, G and S will always both be on an identical circle having its
center at the original position of S. Because G has a tangential component
whereas S does not, G will always catch S (actually, this is not proven
until you solve the o.d.e. associated with the problem).
If G can go at 40 mph and S goes at 20 mph, you can work out that it will
take G at most 1h 49m 52s to catch S. On average, G will catch S in:
( -2pi + sqrt(3) ( exp(2pi/sqrt(3)) - 1 )) / 40pi hours,
which is, 27 min and 17 sec.
==> geometry/spiral.p <==
How far must one travel to reach the North Pole if one starts from the
equator and always heads northwest?
==> geometry/spiral.s <==
One can't reach the North Pole by going northwest. If one could, then
one could leave the North Pole by going southeast. But from the Pole
all directions are due south.
If one heads northwest continuously, one will spiral closer and closer
to the North Pole, until finally one can't turn that sharply.
==> geometry/table.in.corner.p <==
Put a round table into a (perpendicular) corner so that the table top
touches both walls and the feet are firmly on the ground. If there is
a point on the perimeter of the table, in the quarter circle between
the two points of contact, which is 10 cm from one wall and 5 cm from
the other, what's the diameter of the table?
==> geometry/table.in.corner.s <==
Consider the +X axis and the +Y axis to be the corner. The table has
radius r which puts the center of the circle at (r,r) and makes the
circle tangent to both axis. The equation of the circle (table's
perimeter) is
(x-r)^2 + (y-r)^2 = r^2 .
This leads to
r^2 - 2(x+y) + x^2 + y^2 = 0
Using x = 10, y = 5 we get the solutions 25 and 5. The former is the
radius of the table. It's diameter is 50 cm.
The latter number is the radius of a table that has a point which
satisfies the conditions but is not on the quarter circle nearest
the corner.
==> geometry/tetrahedron.p <==
Suppose you have a sphere of radius R and you have four planes that are
all tangent to the sphere such that they form an arbitrary tetrahedron
(it can be irregular). What is the ratio of the surface area of the
tetrahedron to its volume?
==> geometry/tetrahedron.s <==
For each face of the tetrahedron, construct a new tetrahedron with that
face as the base and the center of the sphere as the fourth vertex.
Now the original tetrahedron is divided into four smaller ones, each of
height R. The volume of a tetrahedron is Ah/3 where A is the area of
the base and h the height; in this case h=R. Combine the four
tetrahedra algebraically to find that the volume of the original
tetrahedron is R/3 times its surface area.
==> geometry/tiling/count.1x2.p <==
Count the ways to tile an MxN rectangle with 1x2 dominos.
==> geometry/tiling/count.1x2.s <==
The number of ways to tile an MxN rectangle with 1x2 dominos is
2^(M*N/2) times the product of
{ cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4)
over all m,n in the range 0<m<M+1, 0<n<N+1.
[Exercises:
0) Why does this work for M*N odd?
1) When M<3 the count can be determined directly;
check that it agrees with the above formula.
2) Prove directly this formula gives an integer for all M,N, and
further show that if M=N it is a perfect square when 4|N and
twice a square otherwise.
]
Where does this come from? For starters note that, with the usual checker-
board coloring, each domino must cover one light and one dark square. Assume
that M*N is even (but as it happens our formula will work also when both
M,N are odd --- see exercise 0 above). Form a square matrix of size
M*N/2 whose rows and columns are indexed by the light and dark squares,
and whose (j,k) entry is 1 if the j-th light and k-th dark square are
adjacent and zero otherwise. There are now three key ideas:
First, the number of tilings is the number of ways to match each light
square with an adjacent dark square; thus it is the _permanent_ of our
matrix (recall that the permanent of a rxr matrix is a sum of the same
r! terms that occur in its determinant, except without the usual +1/-1
sign factors).
Second, that by modifying this matrix slightly we can convert the
permanent to a determinant; this is nice because determinants are generally
much easier to evaluate than permanents. One way to do this is to replace
all the 1's that correspond to vertical adjacency to i's, and multiply the
whole thing by a suitable power of i (which will disappear when we raise
it to a fourth power).
[Exercise 3: check that this transformation actually works as advertised!]
Third, that we can diagonalize the resulting matrix A --- or, more
conveniently, the square matrix of A' order M*N whose order-(M*N/2)
blocks are 0,A;A-transpose,0 , whence det(A') = +-(det(A))^2. Then
the rows and columns of A' are indexed by squares of either hue on our
generalized checkerboard, and its entries are 1 for horizontally adjacent
squares, i for vertically adjacent ones, and 0 for nonadjacent (including
coincident) squares. This A' can be diagonalized by using the trigonometric
basis of vectors v_ab (a,b as in the formula above) whose coordinate at
the (m,n)-th square is sin(a*m*pi/(M+1)) * sin(b*n*pi/(N+1)).
Exercise 4: verify that these are in fact orthogonal eigenvectors of A',
determine their eigenvalues, and complete the proof of the above formula.
(None of this is new, but it does not seem to be well-known: indeed
each of the above steps seems to have been discovered independently
several times, and I'm not sure whom to credit with the first discovery
of this particular application of the method. For different approaches
to exactly solvable problems involving the enumeration of domino tilings,
see the two papers of G.Kuperberg, Larsen, Propp and myself on
"Alternating-Sign Matrices and Domino Tilings" in the first volume of
the _Journal of Algebraic Combinatorics_.)
--Noam D. Elkies (elkies@zariski.harvard.edu)
Dept. of Mathematics, Harvard University
==> geometry/tiling/rational.sides.p <==
A rectangular region R is divided into rectangular areas. Show that if
each of the rectangles in the region has at least one side with
rational length then the same can be said of R.
==> geometry/tiling/rational.sides.s <==
"Fourteen proofs of a result about tiling a rectangle" (Stan Wagon)
_The American Mathematical Monthly_, Aug-Sep 1987, Vol 94 #7. There
was also a fifteenth proof published a few issues later, attributed to
a (University of Kentucky?) student.
User Contributions:Part1 - Part2 [ Usenet FAQs | Web FAQs | Documents | RFC Index ] Send corrections/additions to the FAQ Maintainer: archive-comment@questrel.questrel.com
Last Update March 27 2014 @ 02:12 PM
|
rec.puzzles Archive (geometry), part 13 of 35
Search the FAQ Archives
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
rec.puzzles Archive (geometry), part 13 of 35
( Part1 - Part2 )[ Usenet FAQs | Web FAQs | Documents | RFC Index | Sex offenders ]
Comment about this article, ask questions, or add new information about this topic: