Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Shopping at the store helps maintain the site. Thank you.
Math & English enrichment at SchoolPlus-Online
HoodaMath: games and movies
Sites for teachers
Sites for parents
Terms of use
Awards
Interactive Activities

CTK Exchange
CTK Wiki Math
CTK Insights - a blog
Math Help

III Millennium Olympiad

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Stories for Young
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Privacy Policy

Guest book
News sites

Recommend this site

Games to relax

Sites for teachers
Sites for parents

Education & Parenting

Manifesto: what CTK is about Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

Four Pegs That Form a Square

Four pegs on a square grid form a square, i.e., the pegs are located at the corners of a grid square. The pegs are allowed to jump over each other so as to land on a grid point across their original position (at the same distance from the jumped over peg.) The jumped over pegs remain in place. Is it possible that after a series of such moves the four pegs form a square larger than the original?

A Java applet is available to experiment with the problem.

Discussion

Copyright © 1996-2009 Alexander Bogomolny

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Four pegs on a square grid form a square, i.e., the pegs are located at the corners of a grid square. The pegs are allowed to jump over each other so as to land on a grid point across their original position. The jumped over pegs remain in place. Is it possible that after a series of such moves the four pegs form a square larger than the original?

The question as it was asked is quite legitimate, although there is a more forthright version. Incidentally, the latter is even more general: Is it possible that after a series of such moves the four pegs form a square of size other than the original? Is that question simpler? In part it is. We may think of the original square as being the unit - the smallest - square of the grid. If so, we may claim outright that it is impossible that a series of moves will result in a smaller square. But, if that's the case, and taking into account that the moves are reversible, it is as much impossible to get a larger square as it is to get a smaller one.

The question, or perhaps its solution, begs for a generalization. What about a triangular or hexagonal grids? Clearly, each sustains a problem with exactly same solution. E.g, three pegs on a triangular grid form an equilateral triangle. They may jump over each other and land on the other side of and at the same distance from, the peg jumped over. Is it possible that after a series of moves they form an equilateral triangle of the size greater than the original?

Nathan Bowler offered a formalization of the foregoing argument:

Define a set S of vectors to be a lattice iff a, b, c (not necessarily distinct) in S implies a + b - c in S. That is, if any 3 corners of a parallelogram are in a lattice then so is the fourth. Since the intersection of any set of lattices is a lattice, for any set of vecotrs there is a minimal lattice containing all of them. (Thus, the minimal lattice of a set of vectors is a subset of any lattice that contains the given set of vectors.)

Lemma

Jumping one point over another in the manner of a peg move does not affect the minimal lattice.

Proof

Let A be the minimal lattice of a set of points. Then A contains all of those points and also (since it is a lattice) contains the new point obtained through the jump. Thus it contains the minimal lattice B of the new set of points. But since peg jumping is reversible, B also contains A. So they are the same lattice.

Now since the minimal lattice of a square is the standard square lattice with that square as one of the cells, it is a trivial consequence of the above lemma that it is impossible to obtain a square of a different size or orientation from the original by peg-jumping moves.

Further generalizations may start with a less regular grid or a number of pegs not necessarily matching the grid's shape. Say, three or five pegs on a "brick wall" grid? Is it possible to get a polygon similar to the original one but of a different size?

References

  1. P. Winkler, Mathematical Puzzles: A Connoiseur's Collection, A K Peters, 2004

Copyright © 1996-2009 Alexander Bogomolny

33062061Page copy protected against web site content infringement by Copyscape


Search:
Keywords:

Google
Web CTK