A Christmas Puzzle

I was given “The Big Book of Brain Games” by Ivan Moscovich for Xmas. Most are too easy but here is a nice one (number 331):

Construct a square from four identical linkages hinged at the corners. Such a figure is capable of moving on its hinges to become a rhombus. How many linkages of the same length must be added to make the square rigid? The linkages must be in the same plane as the square and each one can be connected only at the hinges.

My best solution so far has 43 extra linkages which must be far too many.

Update 28-Dec-2010: Lubos has given a nice solution with no overlapping links which requires only 31 extra edges or 29 if you allow the links to cross. However I have found out that this is still not the best solution for the case where overlaps are allowed! so keep trying.

Final Update: Since posting this puzzle I have learnt that a version of it was posed in Martin Gardner’s SciAm column in 1963. His version required that the bracing links do not overlap. Seven readers sent in the solution with 23 added links shown below.

Erich Friedman considered the case where links can cross in 2000 and posted results on his Math Magic website. His best solution had 17 extra links. However, someone later informed him that Andrei Khodulyov had found a solution some time ago with just 15 extra links.

Well done to all those who posted solutions here and over at The Reference Frame.

 

 

 

40 Responses to A Christmas Puzzle

  1. Bill K says:

    Well, I’ve got a solution which is probably the same as yours. I used trusses of equilateral triangles to build a large 3-4-5 triangle, and put the square at the inside corner.

  2. Michael Baker says:

    I think I’ve got one using 13 extra linkages, but it’s 3am so I should check it in the morning.

  3. Luboš Motl says:

    Could you please draw at least one solution for me? I spent hours at night, being excited about 10 solutions with various numbers of extra linkages (13,40,43, and many others), diverse symmetries, etc., except that I could always prove that the thing can still get tilted after some attempts. ;-)

  4. Philip Gibbs says:

    My solution was as described by Bill, I’ll try to do a crude picture

  5. Luboš Motl says:

    Oh, Bill is right, that’s funny. ;-) It works. Here is the graphics – so that everyone can see what he means. It’s encoded in his words, anyway:

    http://picasaweb.google.com/lubos.motl/TheReferenceFrame3#5555289320073368914

    The previous pictures (click the left arrow) show the kind of patterns that are totally hopeless and that you can waste hours with. For everyone, if you draw a skeleton whose all internal angles are multiples of 15 degrees, chances are that it can be proved that such a structure cannot be made rigid haha.

  6. Philip Gibbs says:

    I added a picture to the main post

  7. Luboš Motl says:

    I found a rather incredible solution, generalizing the Phil/Bill concept just a little bit beyond the simplest Pythagorean solutions, that uses 7+11+13+2-4 = 29 extra linkages only. :-)

    Mathematica was needed. Let me draw it…

  8. Luboš Motl says:

    Here is my simpler solution:

    http://picasaweb.google.com/lubos.motl/TheReferenceFrame3#5555325577430213618

    Note that instead of the 3-4-5 Pythagorean triangle, I have a 2-3-Sqrt(13) triangle. ;-) That’s OK because I can also produce Sqrt(13) distance from a network of equilateral triangles.

    It’s because the relevant network makes 3 steps to the right and 1 smaller step to the top, so the difference between the coordinates of the two relevant vertices is

    (3+1/2, sqrt(3)/2)

    The length of this vector is 12.25+0.75 = 13 as well. ;-)

    I will also prepare a modified picture for those who are offended by the intersecting lines on the solution above.

  9. Luboš Motl says:

    If you don’t allow (movable) intersections, here is a solution with 15+11+7+2-4=31 extra linkages. On the long side, I had to make a longer detour which added a small equilateral triangle, i.e. two extra linkages were needed:

    http://picasaweb.google.com/lubos.motl/TheReferenceFrame3#5555327814233838274

  10. Luboš Motl says:

    I think it’s fair to repost the Mathematica code that allowed me to find the combination without much mechanical work:

    finds = {{0, 0, 0, 0, 0, 0, 0}};

    For[a = 1, a <= 7, a++,
    For[b = -7, b <= 7, b++,

    v = {a, 0} + b*{1/2, Sqrt[3]/2};
    lenVsq = v[[1]]*v[[1]] + v[[2]]*v[[2]];

    For[c = -5, c <= 5, c++,
    For[d = -5, d <= 5, d++,
    For[e = -5, e <= 5, e++,
    For[f = -5, f <= 5, f++,

    u = {d/2 + c, d*Sqrt[3]/2} – {f*Sqrt[3]/2, f/2 + e};
    lenUsq = u[[1]]*u[[1]] + u[[2]]*u[[2]];

    finds =
    If[(c*c + d*d)*(e*e + f*f) != 0 &&
    Abs[lenUsq - lenVsq] < 0.00001,
    finds~Join~{{a, b, lenVsq, c, d, e, f}}, finds];

    ]
    ]
    ]
    ]
    ]
    ]

    Dynamic[MatrixForm[finds]]

  11. Luboš Motl says:

    My TRF text about it:

    http://motls.blogspot.com/2010/12/big-book-of-brain-games-puzzle.html

    Please let me know after a few days – to get the credit you deserve, Phil.

  12. Lawrence B. Crowell says:

    Wow,

    I missed this one yesterday. It appears that Phil’s solution can be reduced by the removal of 8 triangles and 16 edge links at the two 45-deg corner “trusses.” This leaves 27 edgelinks. The problem with Lubos’ solution is that the overlapping edgelinks can imply moving up a dimension, which the rules forbid. Unless these edgelinks can pass through each other there is a problem of edgelinks lying on top of each other — implying an epsilon distance in the z direction.

    • Philip Gibbs says:

      For the record I would allow solutions with crossing links, but the original statement of the problem does not make it clear if this would be acceptable

  13. Luboš Motl says:

    Dear Lawrence,

    I think you are deeply confused about all points you wrote. There are no 45-degree tilted lines in any corners or trusses anywhere in Bill/Phil’s solution. So I don’t think you have found a way to reduce the number to 27 linkages.

    Also, almost one hour before your complaint about the intersections in my solution, I posted a 31-extra-linkage solution without any intersections, based on the same mathematical identity.

    By the way, the program above searched for the generalized solution with triangles with 3 edges. Aside from the 3-4-5 triangle whose long side is sqrt(25) and my 2-3-sqrt(13) whose long side is sqrt(13), there is another, highly non-minimal solution in the interval with up to 5+5 steps on each of the three sides, one whose top length is sqrt(39). All three sides in this solution have to use steps in both directions of the triangular truss. ;-)

    This is a complete list of solutions where you use up to 5+5, 5+5, 7+7 steps in the three triangular trusses.

    Best wishes
    Lubos

  14. Lawrence B. Crowell says:

    I was eyeballing the picture first thing in the morning, but the problem is that I am violating the need for a Pythagorean triplet. This problem is slightly infecting, and gnawing on this was not in my plans for the day.

  15. Luboš Motl says:

    Didn’t you confuse the author, Phil? A book by the same name

    was written by Ivan Moscovitch and Will Shortz was a journalist who reviewed it (or its previous version) in the New York Times. ;-)

  16. Luboš Motl says:

    Dear Phil, your new priority claim is exciting but will you kindly reveal your secret know-how? I would like to know where my “almost rigorous proof” that your configuration can’t exist went wrong. ;-)

    There are a few loopholes in the proof where the assumptions look plausible but are not quite rigorously proved.

    • Philip Gibbs says:

      Sadly I can’t claim any priority. I learnt about some existing solutions by other people who must have spent a lot of time thinking about it. You will kick yourself when you see the solutions (I did). I don’t want to give them away yet but I will try to think of a good hint. I’ll look at your “almost proof” again and see if I can pinpoint the wrong assumption.

      • Luboš Motl says:

        It seems drastic but based on the triangular truss search that is kind of exhaustive, my guess is that it won’t be a simple union of triangular trusses at all.

        Consequently, there will be more than two hinges in the secret new solution with angles being different than multiples of 30 degrees, and many other things may therefore be different than I secretly assumed, too. ;-)

      • Luboš Motl says:

        Maybe I found a terrible new loophole. One can add angles.

        Note that pi/4 may be calculated from my favorite exact formula

        pi/4 = 4 arctan(1/5) – arctan(1/239)

        and similar, simpler identities. Especially if I allow sqrt(3) to appear in the arguments, I can probably get simpler prescriptions like that.

        So one can perhaps connect several triangular trusses on top of each other, and each of them will be rotated by some angle relatively to the other truss, and at the end, one may attach the square to some places to ensure 90 degrees haha.

      • Philip Gibbs says:

        Your white list gives lengths of square root of 0,1,3,4,7,…
        If you could get square root of 2 in the list you could use it to hold the diagonal of the square. Making triangles with three of the lengths on your list effectively means overlaying three triangular grids locked together. What are the possible distances then between points on those grids? Is square root of two a possibility?

      • Luboš Motl says:

        It’s a totally new, more invariant way to classify the solutions into categories.

        So far, I classified them by the distance between two hinges with nontrivial angles, and sqrt(13) was the winning distance.

        However, there may be more than two hinges where angles differ from multiples of 30 degrees, and the angles obtained at such hinges may add. So one must allow to remember several angles.

        What one should really remember in the first place is not the distance between two hinges but rather all the angles mod 60 degrees (from the truss) that can be obtained from the trusses. They can be added. And the goal is add such angles that appear in a truss to 90 degrees mod 60 degrees. ;-)

        The previous 3-4-5 or 2-3-sqrt(13) procedures are a simple special case of the new procedure that work with a single angle mod 30 or 60 degrees. But one may need several of them…

      • Luboš Motl says:

        Wow, a reader has posted an amazing solution – look at the colors haha:

        http://js-kit.com/blob/8r0_SqS_JUs2NBGxzK_bgN.jpg

        23 extra linkages, better than 31, no intersections.

      • Philip Gibbs says:

        That is a great solution, but when the links are allowed to cross a result with less links is obtainable.

      • Luboš Motl says:

        Yes, I totally believe you and I may know how to find it.

        The incomplete proof had exactly the bug I expected – there are many more hinges than 2 where the angles aren’t multiples of 30 degrees.

        If you look at the red star solution, it has the upper vertex V of the star which is totally outside the “main grid” – linear combinations of t,u,v,w from my “proof”. The distances of the vertex V from 3 points are determined by linkages or pieces of triangular trusses – the distances are 1, sqrt(3), sqrt(3). These are 3 conditions for 2 coordinates of the new point which is overdetermined, and that’s why the conditions also fix the angle of the square.

        So the “bigger generalization” one has to look for contains N new points outside the integer combinations of t,u,v,w which are attached to points of the t,u,v,w combined basic networks at least by 2N+1 edges or segments of triangular truss. ;-)

        Moreover, I already know that this rather bold generalization of the previous concept – that allowed as complex solutions as the sqrt(13)-based ones – is not a complete one because it still doesn’t allow to add the angles by placing the trusses on top of each other in a sequence of steps. Moreover, a blind addition of angles at one point wouldn’t list all the possibilities, either, because one may combine it with the new points in arbitrary ways. ;-)

      • Luboš Motl says:

        A newer recipe for the Mathematica code to search through the new class inspired by the star:

        This class has a critical point (hinge with non-30k-degree angles, expected to have fixed distances from others) that is not an integer combination of t,u,v,w. However, the squared distances of this new point from 3 points that are integral combinations of t,u,v,w must all be elements of the white list (allowed squared distances between vertices in a triangular truss).

        In practice, one puts the origin to one of these truss-points, and chooses another one. Then he chooses two elements from the white list, and finds the intersection of the two circles – with the right two white-list distances from the origin and the other point of the t,u,v,w “lattice”. Then the program checks whether this new point – away from the t,u,v,w “lattice” – has a white-list distance from another point of the t,u,v,w “lattice”. ;-)

        Obviously, there are many more integers to be varied in this algorithm. On the other hand, one is looking for a pretty thrifty solution now, so many of those integers could be expected to be rather small.

        The star-solution itself has a new point with white-list distances sqrt(3), sqrt(1), sqrt(3) from three points, something like -t+v, 0, t-v – that’s pretty simple already. In fact, I guess that one can make some “straightforward” intersecting simplification of the red star diagram itself.

        But if not, it still shows that all the integers in the solution that beats this one are likely to be pretty small. A funny thing is that if some of the white-list distances are actually integer I and if the 3 links go in pretty much “different” directions, one may choose a simple sequence of I linkages instead of the full truss – because the distance has to be minimized, anyway. ;-)

        This could mean that the distances could be pretty big – if only one of them is large, it could be as big as 6 – not 22 because the “standard” side of the picture would still have to include the truss. ;-)

  17. Philip Gibbs says:

    I’ll post some info here on the history of this puzzle and the solutions at 9pm GMT. You have until then to keep looking.

    • Luboš Motl says:

      Sorry I have to watch Czech TBBT 3×16 now.

    • Vladimir Kalitvianski says:

      Dear Philip,

      In the “Energy conservation” section you do not discuss the RTG by A. Logunov who emphasized its importance in his construction. Comments are already closed. Can you tell you opinion about Logunov’s approach to gravity, please?

      • Philip Gibbs says:

        I made it clear in the energy conservation posts that I would only discuss classical general relativity, anything outside of that would have just confused the issue.

        I never heard of RTG until you mentioned it. I’m sorry I don’t have time to look at RTG just now. The trouble is that I am quite comfortable with GTR so I lack motivation to look at alternatives. There are plenty of people who are less happy with GTR who might be more prepared to look at it.

      • Vladimir Kalitvianski says:

        Dear Philip,

        You may consider RTG as GR in the harmonic coordinates. In other words, it is not too different from GR technically but conceptually. It is GR in the flat Minkowsky space-time. There are conservation laws in there, no pseudotensors, gravitational field is as physical as electromagnetic one, etc.

        A.A. Logunov is a Soviet academician, not a crackpot. Some of his publications are available on arXiv.

  18. Luboš Motl says:

    Yes, I have verified that this “improved JollyJoker’s #1 solution” with 15 edges, intersections allowed, works:

    Start with

    http://js-kit.com/blob/rr4TVxfFDnrQY61_MScD65.gif

    The blue lines are vertical. Add another vertex near the center of the square and attach it by 3 simple edges to the 2 upper endpoints of the blue lines, and to the lower vertex of the square. The distances work, see the reply to this comment.

  19. Luboš Motl says:

    The lower square’s vertex is (0,0), the upper square’s vertex is (0,sqrt(2)). The right vertex is (sqrt(2)/2, sqrt(2),2), and the blue vertex above it is (sqrt(2)/2, sqrt(2)/2+1). Its distance from the left square’s vertex is correctly sqrt(3), to be connected by the basic rhombus (2 small triangles).

    Meanwhile, the new vertex near the middle of the square has coordinates (0,1), so it has the right distance from the lower square’s vertex.

    The distance from the upper right blue endpoint is the length of the difference vector, namely (sqrt(2)/2,sqrt(2)/2) – the term “1″ cancels in the y-coordinate, so the length is equal to 1 as well. The same for the left vertex.

    Moreover, the 6 coordinates of the 3 new points are overdetermined by 7 conditions – two blue “1″ distances for the upper vertices, two sqrt(3) purple/green diagonal distances realized by the rhombi, and the 3 simple-edge distances of the new central point. So it’s overdetermined by 1 condition that freezes the angle of the square.

  20. JollyJoker says:

    I have to point that that although my version of the 15-edge solution was incomplete, Andrei Khodulyov’s version is unreadable due to lack of colors. I’ll call it a draw ;)

  21. Luboš Motl says:

    This is an old story, but a good one. Pretty interesting I’ve never heard about it before.

    Link to your website was added.

    Do you think that with the more complete knowledge, one could prove that no solution better than 15 exists? Or find a better one?

    Thanks for the fun, anyway.

  22. JollyJoker says:

    I’m not sure if one could build a minimality proof from this, but we do know that some solution for getting non-obvious angles has to be used. Every one shown so far is based on a Pythagoran triangle; first Philip’s 3-4-5, then Lubos’s 2-3-sqrt(13), then bbzippo’s 1-sqrt(2)-sqrt(3). Assuming the last is minimal, the “stabilized rhombus” of two equilateral triangles must be used for at least one edge and the diagonal of the square must be the sqrt(2) side. Add one edge and we have something completely unstable using six edges in addition to the square. The distances between points in that construct could give some kind of starting point for a search.

  23. Philip Gibbs says:

    I agree that the variant of the 15 link solution is also valid.

    I don’t know about minimal proofs. It would probably require checking a lot of cases.

Follow

Get every new post delivered to your Inbox.

Join 270 other followers

%d bloggers like this: