Elegant, not Elephant : Part II
by Ankoganit, Aug 2, 2016, 5:15 AM
This post is a sequel to my previous blog post: Elegant, not Elephant. As before, I aim to collect and present some more instances of mathematical problems, which are seemingly unassailable but are deceptively simple. The topics vary widely : combinatorics, algebra, geometry -- but a common theme of innate elegance binds them together.
OK, I guess that's enough of a prologue; let's start this off with a rather famous one:
One hundred ants are dropped on a meter stick. Each ant is traveling either to the left or the right with constant speed 
meter per minute. When two ants meet, they bounce off each other and reverse direction. When an ant reaches an end of the stick, it falls off. Over all possible initial configurations, what is the longest amount of time that you would need to wait to guarantee that the stick has no more ants?
A rectangle is called special if at least one of its sides has integer length. Suppose a rectangle is tiled by rectangles each of which is special. Prove that the big rectangle itself is special.
is the median of the triangle 
, and 
and 
are incenters of 
and 
respectively. Given that 
is cyclic, prove that is 
isosceles.
Suppose we can place 
equal disk-shaped coins on a rectangular table such that no two coins overlap and it's impossible to place another coin on the table without causing overlap. Prove that allowing overlap, we can cover the table entirely using no more than 
coins. Note that a coin can stay on the table iff its center lies on the table.
roads on a plane, each a straight line, are in general position so that no two are parallel and no three pass through the same point. Along each road walks a traveler at a constant speed. Their speeds, however, may not be the same. It's known that traveler met with Travelers 
, and each of the other travellers met both Traveller and . Show that any two travellers met each other.
Appendix: Here's another of my favourite ones; I didn't include it above since this proof is disregarded by many mathematicians.
Hex Theorem : The game of Hex cannot end in a draw.
Sources:
6. Su, Francis E., et al. "Ants on a Stick." Math Fun Facts. http://www.math.hmc.edu/funfacts.
7. Stan Wagon, Fourteen Proofs of a Result About Tiling a Rectangle.
8. PDC, India, 2016
9. An AoPS topic here.
10. Four Traveller's Problem at Cut-The-Knot , http://www.cut-the-knot.org/gproblems.shtml
Appendix: http://www.cut-the-knot.org/Curriculum/Games/HexTheory.shtml
OK, I guess that's enough of a prologue; let's start this off with a rather famous one:
One hundred ants are dropped on a meter stick. Each ant is traveling either to the left or the right with constant speed 
meter per minute. When two ants meet, they bounce off each other and reverse direction. When an ant reaches an end of the stick, it falls off. Over all possible initial configurations, what is the longest amount of time that you would need to wait to guarantee that the stick has no more ants?
A rectangle is called special if at least one of its sides has integer length. Suppose a rectangle is tiled by rectangles each of which is special. Prove that the big rectangle itself is special.
different and equally elegant proofs of this, using tools ranging from graph theory and coloring to polynomials and complex double integrals. The "!" sign is left to the reader.
rectangles (with edges parallel to axes) and colour them black and white in a chessboard fashion. Note that a rectangle is special if and only if it contains equal amounts of black and white area. Since the constituent rectangles satisfy this, the whole rectangle must also contain same amount of black and white area, and hence must be special. 
be the set of lattice points which are corners of some tile, and 
be the set of tiles. Consider a bipartite graph on 
with 
and 
joined if and only if 
is a corner of 
or 
,
has odd degree, so there must be some other point with odd degree (sum of degrees is even), which can happen only for corner points of the big rectangle (check it yourself). So some other corner must have integer coordinates, implying the result. 
is the median of the triangle 
, and 
and 
are incenters of 
and 
respectively. Given that 
is cyclic, prove that is 
isosceles.
be the incenter of 
and 
passes through the circumcenter of 
imply that 
.
,
"tilts" on the right side, and so it can't be perpendicular to 
,
has a greater inradius, it has to tilt the opposite way. Contradiction. 
Suppose we can place 
equal disk-shaped coins on a rectangular table such that no two coins overlap and it's impossible to place another coin on the table without causing overlap. Prove that allowing overlap, we can cover the table entirely using no more than 
coins. Note that a coin can stay on the table iff its center lies on the table.
.
times to cover the 
roads on a plane, each a straight line, are in general position so that no two are parallel and no three pass through the same point. Along each road walks a traveler at a constant speed. Their speeds, however, may not be the same. It's known that traveler met with Travelers 
, and each of the other travellers met both Traveller and . Show that any two travellers met each other.
-
a
be the line corresponding to traveller 
.
and 
meet, they describe a plane 
,Appendix: Here's another of my favourite ones; I didn't include it above since this proof is disregarded by many mathematicians.
Hex Theorem : The game of Hex cannot end in a draw.
Sources:
6. Su, Francis E., et al. "Ants on a Stick." Math Fun Facts. http://www.math.hmc.edu/funfacts.
7. Stan Wagon, Fourteen Proofs of a Result About Tiling a Rectangle.
8. PDC, India, 2016
9. An AoPS topic here.
10. Four Traveller's Problem at Cut-The-Knot , http://www.cut-the-knot.org/gproblems.shtml
Appendix: http://www.cut-the-knot.org/Curriculum/Games/HexTheory.shtml
This post has been edited 1 time. Last edited by Ankoganit, Aug 2, 2016, 5:18 AM
though the key idea is relatively small)...
July 2021
April 2018