Slashdot Mirror
'Carpenters Ruler' Problem Solved
An unnamed correspondent writes: "Three mathematicians just solved the 'carpenters ruler' problem. The carpenters ruler problem is given a chain of linked rods (a carpenters ruler) in two dimensions, can it always be unwound? As it turns out, it can, check here. You might be saying 'so what', but this has potential applications in anything from protein folding to robotic arm movement. Check here for some animations of the carpenters rule in action."
No, it isn't a topological problem, it's a geometric problem. Topologically, it's trivial: every non-self-intersecting polygon is ALREADY untanlged from a topological standpoint, sheesh. Like many people, you've been confused by the zooms in the animation.
...and he has one of these rulers. On one end, there's a telescoping 6-inch length that's about 2 millimeters wide; when I was young, I used to extend this and pretend it was a walkie-talkie. Ah, those were the days.
"Ancillary does not mean you get to rule the world." --U.S. Circuit Judge Harry Edwards, speaking to the FCC's lawyer
Haven't you ever read Dirk Gently? Remember the bit about the sofa in the stairwell...
A tangential discussion on this subject, though offtopic, might still be interesting. Why moderate that down?
Yes. Even more amazingly, if you are allowed to cut the napkin into finite pieces (5 actually), you can form a planar surface with infinite perimeter and area via the Banach-Tarski construction applied to 2-D surfaces. Hausdorff has a similar construction for a unit segment dissection and reassembled into a segment with double (or arbitrarily long) length.
The lives enjoyed by many math mysteries are being shortened by the technological age. Yet we do not create many new questions to be raised. With such a lopsided affair, what will drive future mathematics?
Anyone else think of Jon Katz when they read this sentence?
Connelly is my Math professor for my Linear Algebra class this semester. Pretty cool to see his name pop up on /. :)
--
-Jeff
-Vercingetorix
-Vercingetorix
"Necessitas non habet legem." -St. Augustine
It just so happens that I have a paper napkin right here at my desk, leftover from lunch. I put it down on my desk: lo and behold, it's a plane.
:)
I then unfolded the paper napkin--and keep in mind that unfolding is really just folding in reverse. Lo and behold, it was four layers of thin paper atop each other; unfolded, it had a substantially larger perimeter.
So the simple answer: unfold the damn napkin.
(Extra credit will be given to those who figure out a way to increase the perimeter of an already unfolded napkin!)
On a more personal note the guy is a total hippy, and seems quite intelligent.
Voila... the perimeter is much bigger than your original square (or rectangular) napkin.
+++OK ATH
> what do you propose replacing the Federal Reserve with?
How about with something based one REAL currency with intrinsic value, like silver and gold, or did you forgot the hyperinflation with the German mark, which WILL happen to the "almighty" american dollar, since there is NOTHING backing it.
"Those who fail to learn from the past, are condemned to repeat it."
There's a problem with that, namely that nothing has "intrinsic" value, at least in terms that would make it passable currency.
Diamonds, for example. Currently, they're considered quite valuable. Why? Except for certain inductrial concerns, most of it's marketing; diamonds are not actually particularly rare (emeralds, for example, are much rarer).
While gold has had value historically, there is nothing saying that cannot change. Some new source could be found. Or perhaps some cheap method of synthesizing the stuff might be discovered (scientists actually have turned lead into gold using particle accelerators and other really neat atomic tricks, but there's this little problem of expense at the moment).
Consider, as a final example, checks. The government has actually never declared these as legal tender. Many places will accept them as payment, simply because they are in common usage. Likewise for credit cards; although they are not, strictly speaking, money, they are commonly accepted in place of it.
My point is that tying money to a commodity really doesn't do very much, because in the end it's all subject to the whims of the markets concerning whatever it is backed by. Also interesting to note is that the federal reserve existed long before the US went off the gold/silver standard, so while abolishing the federal reserve would certainly make it necessary to accomplish your goals it's not strictly necessary for that to happen. I do see what you're trying to get at, and frankly I prefer your idea (in theory) to the highly volatile systems in place at the moment. That said, however, I do see potential problems with it.
----------
Gold does not have intrinsic value. Like everything else, it has value based on supply and demand.
You seem to be confused. The normal usage of "intrinsic value" in economics is that people find it valuable even in the absence of laws/regulations/common consent/consensual hallucinations. Gold DOES have intrinsic value (it's pretty, resistant to corrosion, conducts heat very very well, etc.), as opposed, say, to paper US dollars which do not.
The fact that the price of gold depends on the supply and demand has nothing to do with it. The price of everything depends on supply and demand.
And then what happens when, say, Russia floods the world with cheap gold from their huge reserves?
Russia does not have huge reserves and its gold isn't cheap (meaning the costs of production are quite comparable with the West/Australia/South Africa).
Besides, WHAT would happen? The worst is that we'll have a bit of inflation, not much at all compared to paper dollars inflation that we had in the 70s and the 80s. The supply of gold in the world is quite limited, as opposed to the capacity of the government printing presses.
Note that I am not arguing for the return to a gold standard -- this is an idea the time of which has passed long, long time ago. I just want to point out that if you want to argue about a subject, it helps to have some clue about it.
Kaa
Kaa
Kaa's Law: In any sufficiently large group of people most are idiots.
I believe this was a constructive proof; they not only proved it was possible, but also how to solve for motions. The problem's open status suggests that no such solution was known earlier.
perfect convexification of a polygon would produce a reasonable estimation of a circle. A circle is the maximal area with a given length of edge.
A fractal surface is a way of generating an infinite edge length with a finite area. If you were to convexify such a fractalized area, you would end up with a potentially infinite circumference circle generated from a fractal of area 1 (or any other number you might want to choose.).
For a simple counter-example, consider a star. Convexified to a 'circular' polygon, it would be a roughly circular polygon capable of containing the original star. q.e.d.
`ø,,ø`ø,,ø!
Free Software: Like love, it grows best when given away.
--Fesh
"Citizens have rights. Consumers only have wallets." - gilroy
--Fesh
Kill -9 'em all, let root@localhost sort 'em out.
yeah it really is awesome, enough to humble anyone, get u off yer high horse eh? hehe...tis nice to see that it is possible though. will someone please keep tabs on that guy and tell us what he is in 10 years...only then will we really know how much we might or might not want to be like him, hehe
Nanotechnology, man.
So it's a good thing they didn't cheat, but instead zoomed out so you can see the entire thing even though it needs more space when it untangles.
"At the moment, however, the new result appears to have no obvious applications."
Never take moderation advice from sigs, including this one.
This is a topological problem. The rules of topology allow you to resize and reorient lines, surfaces, and volumes, as long as you don't introduce any new holes or break any connections. Just think of it as "stretching" rather than "changing lengths". If you've ever tugged on your shoelaces to get them untied, then you know what I'm talking about.
-- Anne Marie
...this is only two dimensions, and a 2D proof doesn't say much about what the case is in 3D. Applications like protein folding and robotic arm movement take place in the real world, which is unfortunately 3D.
My guess--and this is only a guess, since I don't work in this field--is that new questions are being raised. However, the new questions are more complex than the old ones, so they either cannot be phrased in a way that most non-mathematicians can understand, or if they can, they are certainly cannot be expressed as elegantly as the old questions, and thus fail to capture the popular imagination the way the old questions did, and thus are not as widely reported on as the old questions.
Never take moderation advice from sigs, including this one.
Many of the classical puzzles are easily defined (like this one, the ol' can't trisect and angle with a straight-edge and compass, etc.), which makes them exciting for non-geniuses like myself to study. They deceptively appear as low-hanging fruit because many came from planar geometry and mechanics. At the time, these were advanced subjects, and it took centuries for the baseline standard of intelligence to achieve a level where even the common person knows F=ma. Once we reach that level, then the creme de la creme will be within reach of the real brainbenders.
Think how long it will take for the baseline knowledge to contain quantum theory (assuming quantum theory survives another century).
I think we've had a glimpse of what the future provides. Fermat's Last Theorem (a^x+b^x=c^x has no solution for x > 2, er.. something) took forever to solve and the solution is simply insane. I'm sure there are bucketloads of similar postulates/conjectures/etc... in the math world alone that will sit idle for centuries. Turing 'n von Neumann had all their P/NP conjectures. And gawk knows what kind of weirdness is stirring in the minds of the QM peoples.
Personally, I feel fortunate to be in a time when the problems being solved are easily explained in laymans terms (e.g. carpenter's ruler). Even though I could never solve it, it's fun to grasp the complexity and then skip ahead to the solution.
Now if they could only solve the map-folding problem... oh wait, maps are becoming extinct...
---
Unto the land of the dead shalt thou be sent at last.
Surely thou shalt repent of thy cunning.
https://www.accountkiller.com/removal-requested
I don't see what you describe in your post... which animation are you looking at and where in the animation is it doing this?
Of course the brute-force application of cutting devices to these delicate mysteries will give you a practical "real-world" solution, but it points out the difference between pragmatists and mathematicians.
Maybe the beauty of a perfect sphere can only be appreciated in the mind, but a basketball is a damned good application of the model to a real-world need (i.e.: fun).
Dirk Gently's ill-fated couch not withstanding, it is funny to see the fuss that brute-force methods of solving mathematical problems have produced. The question seems to be this: is an 'elegant' proof tomorrow better than an ugly one today?
Not unless you prefer the process of solving the problem, or maybe you secretly hope the mystery will remain unsolved forever.
Yeah. Unfortunately, my clever proof is much too long to fit on the napkin.
-fb Everything not expressly forbidden is now mandatory.
How about with something based one REAL currency with intrinsic value, like silver and gold,
And then what happens when, say, Russia floods the world with cheap gold from their huge reserves? [which was a very real possibility that was floated during the Y2K thing, which was why smart people did NOT put their money into gold]
Gold does not have intrinsic value. Like everything else, it has value based on supply and demand. Dollars have value because of common consent. The difference is that we, as a country, control the supply and aren't at the mercy of a foreign power who might flood the market with gold.
The Federal Reserve may not be a perfect system, but it's way better than basing it on arbitrary metals. Heck, how about basing the currency on oil? Think about how insane that would be, and apply the same thinking to gold or silver.
--
Sometimes it's best to just let stupid people be stupid.
It is actually not hard to see why the problem is quite simple to solve if expansions would be allowed:
-
First, note that allowing expansions is equivalent to allowing contractions.
-
Then, realize that each polygon has at least two adjacent edges A-B, B-C that define a triangle A-B-C, which is completely on the inside of the polyon. By moving the center vertex B to the midpoint of A-C, one vertex of the polygon is eliminated (in general, this causes two contractions). Proceed till only a triangle ist left.
q.e.d.Intrinsic value of gold?
Most of the "value" of gold isn't intrinsic, but merely traditional. If people stopped valuing it just because it's gold, its price would drop to about $120/oz. overnight, entirely supported by its rarity and the handful of industrial applications where it is the best material.
Now, admittedly it would be a lot harder to inflate supplies of gold, but there isn't any real way to stop the government from reducing the gold-per-dollar by law, repudiating debt, delinking the dollar from gold again, or any of a dozen other ways which one can learn about by looking at the history of the gold standard.
So, the value of a gold-backed dollar is no more secure than that of one backed by nothing; continued value of each depends on political will to maintain that value.
There's no "we" in team, only "me"
-Vercingetorix
-Vercingetorix
"Necessitas non habet legem." -St. Augustine
Number theory will always have deceptively simple sounding conjectures that are surprisingly hard. Try Goldbach's Conjecture - every even number is the sum of two primes. That has been a rich field for crackpots - er, I mean non-geniuses like you - to study.
If you're a little more ambitious you can try the Riemann Conjecture. That has all kinds of nice implications like the distribution of primes etc.
Unlimited growth == Cancer.
So what, I'm exp!
That's unlikely to happen with Gold, since gold is simply hard to find. Although it's possible to go off of the gold standard, it requires a conscious effort, rather than simple stupidity.
There is, however, at least one counter-example which almost proves the point. History records A gold-standard inflation problem which occurred when Europe found, and plundered, the New World. Europe's supply of gold expanded massively. Those countries which were not in on the plunder suffered from the sudden shift in the supply/demand curve of gold.
The extra supply, however, consisted of thousands of years worth of americas' gold mining. Once the plunder was complete, things settled down again.
`ø,,ø`ø,,ø!
Free Software: Like love, it grows best when given away.
> folding ever exceed the perimeter of the
> original napkin?
Nope. You're doing two things:
1) A fold that makes reduces the permeter is hiding one or more corners and replacing each with a hypotenuse of the triangle, which is guaranteed to be smaller than the sum of the original two sides.
2) Any fold that increases perimiter is merely reversing the above process, trading in 'hypotenuse' for sections of previously hidden edge. (The "hypotenuse" here can be original edge, or edge created by folding. It still works out the same. You can't get more previously hidden edge than you started with (you can't reveal an edge that wasn't cached in a previous step), and you trade away the extra "hypotenuse" length you added in order to reveal those edges.)
No, this is not a mathematical proof. :)
Rob
That wasn't the impression I got -- I'm not so much of a math head to remember the new questions, but I do recall that new questions seem to be coming up on a fairly regular basis.
And even if we do figure out all of theoretical mathematics (unlikely, imo, at least in the foreseeable future...) there's always quantum physics
I don't think we'll be bored too soon.
Uh. How about having /. servers cache the pages linked to, allowing folks to use them as sort of a proxy service? Or am I missing something here?
[100% ISO 646 Compliant]
SVM, ERGO MONSTRO.
Actually, on the first fold, the numbers are ridiculous:
assume a square 6 units on an edge.
First fold is at the mid-point of height and width; it essentially removes 6 units of perimeter while adding back sq(18) ~ 4.24. Then, fold back so that a triangle that is 1 unit on a side is revealed(trust me; math is simpler).
Now, we have two unit triangles whose hypotenuse is exposed and one whose sides are exposed. This adds up to 2*sq(2) + 2, or 4.83, which, wile larger than the diagonal, is certainly smaller than the original 6.
Premise:
any part of the subdivided segment can be treated independantly.
Any fold that further subdivides affects a localized segment in the same way as the first fold affected the whole segment; it shortens it. Therefore, by the principle of inductance, you will always shorten the perimeter.
Unfortunately, this proof only holds for equilateral triangles. My brain hurts too much to figure one out for any other kind, but I doubt you will find any situation that is significantly different.
I realise that an infinite number of edges is often assumed to give an infinite perimeter, but that breaks down here, as the length of each individual edge decreases faster then the number of edges increases.
This is a bit like the infinite area, finite volume problem, which is easily dealt with on the basis of the fact that the inverse function multiplied against d, the derivative of the area, will approach some constant if you take its limit, whereas the volume function of the same function is constantly decreasing.
A society that will trade a little liberty for a little order will lose both and deserve neither. - Thomas Jefferson
The animation appears to have variable-length rulers... is it supposed to be like that?
________________________________________
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
Okay, I really really want to make an OpenGL screensaver out of that little animation. I mean could you imagine that, only with 3d pipes, ploating around your screen as you return from a much-deserved coffee-break?
--
Feminism is the wild notion that women are human beings.
...but where is the everyday application for it? I mean it looks cool, but that doesn't get us anywhere
How Jaded Are You?
Tarquin's First Question: With X trolls and Y Karma points can -1 always be reached?
The lives enjoyed by many math mysteries are being shortened by the technological age. Yet we do not create many new questions to be raised. With such a lopsided affair, what will drive future mathematics?
Pax Digitalia
Now if they can only do something about carpenter's crack (also applicable to plumbers).
I swear, I've gone through so many quarters that way.
One of the many things I hate. thingsihate.org
Just out of curiosity, what do you propose replacing the Federal Reserve with?
--
Sometimes it's best to just let stupid people be stupid.
Unbeknownst to Taco, Andover pays me to create the impression among Slashdotters that they are cool. One of the many ways I do this is the ddos stuff, it reinforces the mentality that reading Slashdot is the 'in' thing to do because everyone else is doing it. It also help VA sell servers by making it look like Slashdot can handle a lot more traffic than everyone else.
At some point it I will have helped attract a sufficient numbers of visitors to make the Slashdot effect a reality, thus putting myself out of a job. Luckily, I have many other skillz that are in demand at the moment.
Cunning linguists
As noted here, the animation is scaling to fit the limited screen real estate; the individual rods remain the same relative length. In other words, they're not cheating, but rather allowing us to see the mechanism adjusted for a limited medium.
MacOS, Windows, BeOS, GNOME, KDE: they're all just Xerox copies
Perhaps this could be applied to the traveling salesman problem, (TSP). The solution to that problem would be a crinkled polygon that we now know could be blown-up like a baloon into a convex polygon. Suppose we start with the points in the TSP surrounded by a convex polygon consisting of segments of the n-1 shortest distances among the points. We now attempt to run the Carpenter's ruler procedure in reverse, sucking in the polygon and trying to fit the joints to the points as we go. I think we would have to slide the polgon around some. If we seem stuck we may have to replace a link with a longer link from the distances greater than the shortest n-1. This is, of course very vague, but I wanted to get it posted in case somebody could see some merit in it.
"Obtuse Anger is that which is greater than Right Anger" - Lewis Carroll
Now if they could only solve the slashdot effect...
According to the article the problem is only unsolvable in 3 dimensions. This may explain why space is 3 dimensional...
I was reading this article and I was saying "hey, this sounds like Erik's work". And it was. Neat.
:-)
Erik is also very intelligent, and has a professional reputation considerbly higher than most 19 year olds I know
Here's Erik's homepage
I don't know, but whatever it was, it probably has to do with pockets. My set of keys (3 linked rings, each with keys) often becomes inextricably tangled in such a way in my pocket.
All kings is mostly rapscallions. -Mark Twain, The Adventures of Huckleberry Finn
Any geek worth his NaCl should have a subscription to Science News (http://www.sciencenews.org). It's a weekly publication, and covered this a couple of weeks ago.
It also covered a possible loophole in the second law of thermodynamics that might make a perpetual motion machine of the second type possible, using Quantum Dynamics.
Go take a look.
www.eFax.com are spammers
unwind a Keren Carpenter ruler? It is the same problem until the tape stretches thin and becomes brittle.
"Trademarks are the heraldry of the new feudalism."
Dood.. to solve something, you first need to know how to solve it...
:(
You need like a set of steps worked out that when followed, will lead to a solution. It's called an 'algorithm' man! You must first come up with an algorithm, before you can wack it onto a huge Beowulf cluster - and coming up with algorithm is the HARDEST part
They're 30cm (approx 11")
Actually, this conjecture was proven this summer past. How do I know this? Because we studied it for some time in September. It is an interesting breakthrough, but I seem to recall the conjecture being taken for granted, and thus although more faith can be put into the applications that fall from Carpenter's Rule, nothing new has really been generated, other than proof. Am I being cynical? Yes. We have no proof of gravity's existence in 2 hours, but we take it for granted. Such as it was with Carpenter's Rule (well, maybe hindsight is 20:20, but this is the impression I had of it ...)
To let the rulers change lengths seems like cheating to me...
"We can't figure this one out, so let's add a new rule that says we can change the size of the bars."
You can't do that in real life.
Unlike a two-dimensional chain, this knotted, three-dimensional "knitting needle" chain in space can't be untangled.
;-)
Really? So how was it tangled in the first place, then . . .
---
This message has been ROT-13 encrypted twice for higher security.
Here's a vaguely-related problem that is fun to contemplate over dinner. You've got a square napkin. You can fold it however you want provided that the resulting shape lies in a plane. For example, you could fold a corner over, which reduces the perimeter, and then fold a "sub-corner" back (as students do with homeworks when they don't have a stapler. :-) ), which increases the perimeter again. The question is, can the perimeter of the shape you form by folding ever exceed the perimeter of the original napkin?
The answer turns out to be... Oh! Look at the time! Gotta get going! :-)
Yes, one of the fears of Mathematicians was that we would eventually drive mathematics into a formal system to which all possible theorems could be solved by blind computation. However, a formal system exhibiting certain characteristics (for lack of better phrasing, can be encapsulated into itself) cannot derive all true theorems from a given set of finite axioms. In other words, there are truths that can only be found by clever reasoning extending outside the bounds of a formal system, and we cannot have simple algorithms mindlessly permuting symbols to solve every mathematical problem.
Practically, if you go out and read most mathematical journals today, every solution (or even partial solution) to any problem usually concludes with several open problems. I would conjecture that there are more known open problems today then ever before and this number is growing exponentially.
Computer technology enables one to look at many examples sans computation, but the truly interesting material is still to lacking in formalization to be tackled by computer systems. In short, I would say that this may be the most exiting time ever to be in mathematics.
I am sure people said this about imaginary numbers, but how else would people analyse complex circuitry (ask any electronic engineer).
Abstract algebra was an easy target, but see how far a modern chemist will get without their trusty character tables.
This problem sounds like it may have applications in today unknown (or possibly known) areas of analysis and topology. It may be used to prove important future theorems, which will then be used to solve physics problems, and then be integrated into technology. Eventually, they may power several aspects of everyday life, in a manner as mysterious as how character tables from group theory aid chemists in creating the materials we surround ourselves with.
Here's a vaguely-related problem that is fun to contemplate over dinner. You've got a square napkin. You can fold it however you want provided that the resulting shape lies in a plane. For example, you could fold a corner over, which reduces the perimeter, and then fold a sub-corner" back (as students do with homeworks when they don't have a stapler. :-) ), which increases the perimeter again. The question is, can the perimeter of the shape you form by folding ever exceed the perimeter of the original napkin?
Nope. There's only so much of the original parameter, (I'll call this the "sharp" edge) and when you fold the paper over the first time, the "bent" edge is always shorter than the sharp edge you just folded away. Now we'll to try to regain some parameter. When you make the second fold, you gain back a portion of the sharp edge that's larger than the bent edge you are now losing. But look -- you should see a triangle on each side of the folded area, each composed of one line of the bent edge and two of the sharp edges. The "inner" two lines of the triangle are the sharp edge. Still with me? It's a rule that the sum of the length of two sides of a triangle are always longer than the third. So the length of the remaining bent edge on the parameter is smaller than the sharp edge you lost, and the second fold only adds back a fraction of the sharp edge. You can never regain back even the original length. That triangle cost you too much space!
Remember "Bring 'em on"? *sigh
Thanks for clearing that up. I was also a bit confused. =)
<p>
I think it would be more effective for the creator of the gifs to keep the zoom constant. Right now I am a bit distracted by the zooming and not able to see how the structure unfolds. I think it would be interesting to build some of these with a Mecanno set and try them out for myself.