Suddenly everything is clear. When I read the problem and it mentioned "pegs" I thought it was a pegboard problem. Those problems usually tacitly assume the standard move rules for pegboard puzzles, in the same way that chess problems use the standard moves of chess pieces. Since every pegboard puzzle I've ever seen only allowed jumping over adjacent pegs, I thought this was a standard rule and was to be assumed. I was reading too much into the word "peg."

I think if you had said that a peg could jump over another peg and land an equal distance on the other side, I would have understood that the distance was variable, overriding the usual pegboard jump rule.

In the first 4 peg question, you don't really need to mention a background grid at all, just 4 corners of a square and the jump rule. The jump rule will generate the grid of possible positions anyway. Then the solution is perhaps even more surprising, since the reader is initially not thinking in terms of grids at all, but geometry. The grid comes into the analysis in much the same way as auxilliary lines drawn in a geometric proof.

I think you could generalize your argument to different shapes as follows (I haven't thought through all the details yet, this is just an idea): Suppose that the set of points you can reach by the allowed jumping rules forms a regular grid, or can be embedded in a regular grid. Now look at the "vector displacements" between pegs in your original figure, i. e. pairs of integers that tell how many spaces to move along each grid direction to get from one peg to another. Then if the LCM of all these numbers is 1, this figure cannot be shrunk on this grid, and the rest of your agrument follows.

The really funny thing is, you don't actually have to check that the LCM is 1. Suppose it were n>1, for example. Then it appears possible at first that you might shrink the figure. However, if you did so, you would have a new figure with LCM m<n, but similar to the original figure. Therefore, the grid it generates would be finer than the original grid, yet if there are moves that lead to the new figure, the original grid must include every point you can get from the new figure, so it must contain this new finer grid. This is obviously contradictory, so if the points of the figure generate any regular grid at all, it is impossible to rescale the figure.

I think this would also work if the grid were triangular or hexagonal, or even grids that are superpositions of these, or grids that are skewed. Maybe they shouldn't be called grids any more at this level of generality. They are really just point sets that are reachable from the figure's pegs by allowed jumps. It looks like the only way a figure could be scalable is if the grid forms some kind of self-similar fractal, because only then can you embed a shrunken copy of the grid into itself.

Is this even possible for a starting figure with a finite number of pegs? I can't think of a proof, but I suspect that it is impossible to generalte a fractally self-similar grid from a finite set of starting points and the jump rule. If we could prove that, we would get the very interesting result that no finite peg figure can be rescaled by jump moves.

I'll think about this some more and see what I come up with.

--Stuart Anderson

Thankyou

sfwc
<><

Well, this is interesting rather than disappointing. The main idea still stands, I think, that a self-similar grid is the criterion for scalability. Since I was tending to think that my conjecture was true (otherwise, why conjecture at all!) I wasn't looking hard enough for counterexamples. As a matter of fact, I was aware that you could do a trick with the Fibonacci sequence where you kept unfolding the sides of an imaginary box forever and generated the entire sequence. This is clearly the same thing, but using the golden ratio gives you a smooth self-similar set of points that the Fibonacci sequence only approaches in the limit. Somehow, I didn't make the connection between that trick and the present case. Thanks!

Next, I wonder if there are multiple solutions like yours on the real line or is this the only one (up to an arbitrary constant scale factor, of course)? It'seems that your construction depends on the peculiar recursive properties of the golden ratio, such as x^2=X+1, so there may be few counterexamples.

Some features of self-similar grids come to mind: since a pair of pegs can repeatedly jump over each other, every point in the grid is a member of many arithmetic progressions. Perhaps there is always a generating set of arithmetic progressions, with the grid points coming from sums of elements from the progressions ("linear combinations" would be no more general than "sums" since we can take an arbitrary starting point as the origin, so that the arithmetic progressions are closed under addition). The displacements between pegs in the original figure produce such a set of arithmetic progressions, and these must by definition generate the whole grid. This is certainly the form your example has.

Even if there are several of them, the ratio between any two essential arithmetic progressions must be irrational, otherwise the LCM of the grid spacings will give you a minimal grid spacing, contradicting self-similarity. "Essential" means that the two progressions in question are both necessary, so that they generate grid points that can't be generated from any other combination of progressions. Of course, the golden ratio is irrational, and without both progressions, you do not get a self-similar grid.

I think your example grid is dense everywhere. It seems impossible to have a self-similar grid that has just one accumulation point, and becomes sparser as you go away from that point, like the behavior of f(n) = 2^n, because the existence of arithmetic progressions means that once you have a small step size, you can step along the whole real line with steps of that size. Since there is no lower size limit if the grid is self-similar, it must be dense everywhere.

Now I must go think about how all this can be generalized to dimensions >1.

Thank you again for an interesting example.

--Stuart Anderson

This makes sense.

>In the first 4 peg question, you don't really need to
>mention a background grid at all, just 4 corners of a square
>and the jump rule. The jump rule will generate the grid of
>possible positions anyway. Then the solution is perhaps
>even more surprising, since the reader is initially not
>thinking in terms of grids at all, but geometry. The grid
>comes into the analysis in much the same way as auxilliary
>lines drawn in a geometric proof.

The grid serves the sole purpose of better organizing the moves.

>I think you could generalize your argument to different
>shapes as follows (I haven't thought through all the details
>yet, this is just an idea): Suppose that the set of points
>you can reach by the allowed jumping rules forms a regular
>grid, or can be embedded in a regular grid. Now look at the
>"vector displacements" between pegs in your original figure,
>i. e. pairs of integers that tell how many spaces to move
>along each grid direction to get from one peg to another.
>Then if the LCM of all these numbers is 1, this figure
>cannot be shrunk on this grid, and the rest of your agrument
>follows.

LCM is of no consequence, since, as you mentioned, the grid could be dropped altogether.

>Is this even possible for a starting figure with a finite
>number of pegs? I can't think of a proof, but I suspect
>that it is impossible to generalte a fractally self-similar
>grid from a finite set of starting points and the jump rule.
> If we could prove that, we would get the very interesting
>result that no finite peg figure can be rescaled by
>jump moves.

I think that even if you could generate a self-similar grid, this would not solve the question of getting a similar figure. Putting the pegs in a certain position would still remain a formidable task.

Now, a different kind of generalization: add an auxiliary peg. Does this change anything? I.e., there are 4 pegs forming a square and another peg. Is it possible to obtain a square of the size different from the original. The square can be composed of any four pegs.

The fifth peg may be placed on a finer grid than that defined by the square. If so, the original argument does not work. Nonetheless, it does not seem possible to change the square's size.

(I made an applet for experimentation sake

https://www.cut-the-knot.org/Curriculum/Algebra/FourPegs.shtml

but do not yet have a reasonable explanation.

You can do it like this: Start with a square at coordinates xy= 00, 01, 10, 11, and an auxilliary peg at 02. Jump 00 over 10 to 20, jump 10 over 11 to 12, jump 11 over 01 to -11. If 00 hadn't already moved, we could have jumped 01 over it in a nice sort of "pinwheel" pattern of jumps. However, jump the auxilliary peg 02 over 01 to 00, and now we can do the jump we want, 01 over 00 to 0-1. The original 4 pegs now form a tilted square with area = 5.

Note also that the auxilliary peg is in the same grid with the original 4 pegs. No new grid points are introduced. It'seems the whole requirement of self-similar grids is moot when 1 auxilliary peg is provided.

--Stuart Anderson

Looks like it, thank you. What if we restrict the sides of the target square to be parallel to the axis?

We 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.

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.

Now consider the case with an auxilliary peg. Suppose the pegs are initially at (0, 0), (0, n), (n, 0), (n, n) and (x, y). The minimal lattice A of this set is {(an + kx, bn + ky): a, b, k in Z}. Suppose for a contradiction that this lattice contains some square of side m < n with sides parallel to those of the original. Then (0, m) is in A (since A is a lattice) and so x is a rational multiple of n. Similarly so is y. Thus by a suitable rescaling we may assume that m, n, x and y are all integers.

Now let l be the highest common factor of x and y. Then since l is a linear combination of m and n with integer coefficients, (0, 0), (0, l) and (l, 0) are all in A, and so the standard square lattice L which is the minimal lattice of these points is a sublattice of A. Let p be the least positive integer such that px and py are both divisible by l. Then we have L = {(an + kpx, bn + kpy): a, b, k in Z}. Indeed, we may include the restriction 0 <= k < n/l since n/l * (px, py) = (un, vn) for some u, v in Z. But then it follows that the intersection of L with the square <0, n)X[0, n) contains at most n/l points. Since it actually contains (n/l)^2 points we have n/l >= (n/l)^2 and so n/l = 1 and so n|m, which is the desired contradiction.[P>This argument could be aptly illustrated by a java applet which automatically shows you the minimal lattice of a set of points you choose.

Thankyou

sfwc
<><

Very good. Thank you.

>This argument could be aptly illustrated by a java applet
>which automatically shows you the minimal lattice of a set
>of points you choose.

Can be a good exercise doing that, too. A nice illustrtaion for an extended page.

> Let p be the least
>positive integer such that px and py are both divisible by
>l.

Since l is the LCM of x and y already, p=1. Hence your lattice L is
L = {(an + kx, bn + ky): a, b, k in Z}, which is obviously just A, hence l=n directly. From there, the rest follows.

By the way, you assumed that in the linear combination l=cm+dn the coefficients are nonzero. This is true of course, but I thought it worth an explicit mention.

--Stuart Anderson

>By the way, you assumed that in the linear combination
>l=cm+dn the coefficients are nonzero. This is true of
>course, but I thought it worth an explicit mention.
Hmmm.. I don't see why this is relevant. It is important that l itself is nonzero, since otherwise you would have to deal with the special case of a single point lattice. However, since LCM is positive on its domain, this seems trivial enough to not mention.

Thankyou

sfwc
<><

https://www.cut-the-knot.org/proofs/PegSquare.shtml
https://www.cut-the-knot.org/Curriculum/Algebra/FourPegs.shtml

for now with no additional applet.

Thank you,
Alex

Thankyou

sfwc
<><

It's a vicious circle of sorts: it's I who is deeply grateful for your contributions.

>However, your doing this has
>drawn my attention to what seems to be a bug in the software
>you are using. At the bottom of the main page it claims
>there have been no updates since May 5th 2005 even though

My fault. Thank you for pointing this out.

>following the link there produces a wealth of such updates
>(which I will now proceed to browse with great pleasure).

I would rely on

https://www.cut-the-knot.org/changes.shtml

where I catalog all page additions, although not necessarily page modifications.

Well, yes, to begin with it does. But it'seems to me that the crux of the original proof is that you can regard the square as lying on a grid, of which it is a unit cell, hence it cannot be shrunk since peg positions are confined to this grid.

>>Then if the LCM of all these numbers is 1, this figure
>>cannot be shrunk on this grid, and the rest of your agrument
>>follows.
>
>LCM is of no consequence, since, as you mentioned, the grid
>could be dropped altogether.
>

I agree that all mention of the grid could be omitted, but that is because the grid is implicit in the peg positions. It is this implicit grid that makes your original impossibility proof so clean and pretty. What I was after with the LCM was to try to get a proof for general peg figures that would be as much like the original proof as possible. Since the original proof hinged on seeing the given square as the smallest possible square on its grid, I wanted to show that a given general figure was the smallest possible one on its grid. If I could generate a number associated with the figure, then argue that this was the smallest value that this number could have, then I would have shown that this is the smallest possible size the given figure could have on its grid.

For example, consider a figure with pegs at xy = 00, 0a, 0b, where 3a=2b. Then the grid spacing is a/2, and we have a figure that has no edges of length 1 grid-space. That means that the original agrument which applied to the square cannot follow quite as directly in this case, because it is not as obvious that the figure cannot be shrunk. However, since the LCM of 2, 3 and 5 is 1, there is an arithmetic (rather than geometric) feature of this figure which has a minimal value. This is I think, a pretty direct generalization of the original proof to figures more complicated than the square.

I agree, however, that this argument was superseded by the one in the following paragraph of that same post, which used the idea of self-similar grids.

>>Is this even possible for a starting figure with a finite
>>number of pegs? I can't think of a proof, but I suspect
>>that it is impossible to generalte a fractally self-similar
>>grid from a finite set of starting points and the jump rule.
>> If we could prove that, we would get the very interesting
>>result that no finite peg figure can be rescaled by
>>jump moves.
>
>I think that even if you could generate a self-similar grid,
>this would not solve the question of getting a similar
>figure. Putting the pegs in a certain position would still
>remain a formidable task.
>

Yes, I agree that this does not give a method for construction. It is only a criterion for possibility. If the grid is not self-similar, then you know the construction is impossible, which does answer the original question when the answer is negative. If the grid is self-similar, then the question remains open of course, since there may be other, as yet unidentified, impediments to the construction, so the construction might still be impossible. Also, the only way I can see to prove the construction possible, is to actually display the sequence of moves, which as you say, may be very difficult.

>Now, a different kind of generalization: add an auxiliary
>peg. Does this change anything? I.e., there are 4 pegs
>forming a square and another peg. Is it possible to obtain a
>square of the size different from the original. The square
>can be composed of any four pegs.

After succeeding in expanding the square with one extra peg, I tried for a long time this morning to get an expanded square that is not tilted, and I have so far failed to find a way to do this.

--Stuart Anderson

>After succeeding in expanding the square with one extra peg,
>I tried for a long time this morning to get an expanded
>square that is not tilted, and I have so far failed to find
>a way to do this.

Have you ever gotten a situation where, by an otherwise legal move, a peg could land on another peg?

Yes, in fact the starting position in my solution above that produces the tilted square has this property. The auxilliary peg could land on the peg at the origin. I have also run into this in some of my attempts to enlarge the square without tilting it.

This does raise the question of whether such a move should be considered legal. The implication of the word "peg" is a physical understanding that two pegs cannot occupy the same hole, but since our grid is not literally an array of holes, it'seems we must make a decision. If we allow multiple pegs to occupy the same point, perhaps there is an easy way to expand the square without tilting it. I have been avoiding moves of that sort so far. I will take a look.

But if there are four pegs?

I've been mulling this over at odd moments during the day, and I just this moment saw how to prove it impossible. Use a parity argument as follows: First note that all jump moves must move a peg an even number of grid spaces on both x and y axes (because it is double the distance to the peg that was under the jump); hence jumps preserve odd-even parity in both coordinates. Take the original 4 pegs to be at xy = 00, 01, 10, 11. Each point has a unique combination of x and y parities.

Now if any peg lands on another peg, they will then have identical parities in x and y coordinates; therefore it is impossible for one peg ever to land on another.

--Stuart Anderson

Yes, thank you.