From:propp@math.mit.edu (Jim Propp)Date:14 Feb 1996 01:51:48 -0500Newsgroups:sci.math.researchSubject:The Margulis Napkin Problem

The Margulis Napkin Problem asks one to prove that it is impossible to fold a unit square to form a flat shape who perimeter is greater than 4. Rumor has it that all Russian graduate students of mathematics know how to solve this Problem, but that as soon as they come to the U.S. (as so many of them seem to do!), they forget how it's done. Can anyone offer a rigorous proof? Jim Propp Department of Mathematics M.I.T.

From:Einar Andreas Rodland <einara@math.uio.no>Newsgroups:sci.mathSubject:Max circumference of folded paper (solution)Date:Tue, 20 Feb 1996 21:30:53 +0100Organization:University of Oslo

Someone posted the following question some time ago: If you have a quadratic piece of paper and fold it a number of times, prove that the circumference cannot exceed 4 (the original circumference). I couldn't find the original posting, hence, I quote the Problem as I remember it. ================================================================= SOLUTION: If you have a piece of paper with any shape, I wish to prove that when folding it, the circumference will be reduced. Say that you fold it along a line AB where A and B are the endpoints, and where the line AB is included in the paper before folding. (If there is a hole in the paper or the paper is non-convex, AB may pass over a region which is not included in AB. We will deal with this later.) Now, AB is included in the paper. When folding along AB, the circumference is increase by AB due to the folding. The two components of the paper each have circumference that go from A to B: ie. you may follow the circumference of any component from A to B. When folding this, you get a new circumference: the outermost of these. We may however follow the part of the original circumference that falls inside the folded paper. This, too, gives a curve from A to B and must therefore have length at least AB. Hence, though we gain AB, we loose more than AB. If the line AB is not fully contained in the paper, you may let the intersections between AB and the circumference of the original paper by P_1, ..., P_2n (n components of AB). The 'inner cricumferences' as were constructed above will arise here to, but will connect pairs of points P_i (not neccesarily neighboring points). The conclusion follows as above. Einar -- Einar Andreas Rodland E-mail: einara@math.uio.no University of Oslo, Norway Departement of Mathematics http://www.math.uio.no/~einara

From:Danny Calegari <dannyc@math.berkeley.edu>Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:Sat, 02 Mar 1996 04:11:16 -0800Organization:UC Berkeley

Einar Andreas Rodland wrote: > . . (preamble excised) > > SOLUTION: > > If you have a piece of paper with ANY shape, I wish to prove that > when folding it, the circumference will be reduced. Say that you > fold it along a line AB where A and B are the endpoints, and where > the line AB is included in the paper before folding. > > . . (rest of solution excised) > I think the point of the MNP was that what is folded repeatedly is the original square, not the image of the square at each stage. Certainly the first fold decreases the circumference, but subsequent folds may "unfold" bits that have been folded in, possibly in some strange way. The "foldings" at each stage are locally isometric maps of the square into R^2, and the "circumference" at each stage is the circ. of the image. But it is the square that is folded at each stage (like an origami construction), not its image. Is the Problem known to be true then? (as J. Propp's post suggests) Danny Calegari.

From:lepro@math.wisc.edu (Douglas R Lepro)Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:2 Mar 1996 19:18:33 GMTOrganization:University of Wisconsin, MadisonSummary:not proved yet

Einar Andreas Rodland <einara@math.uio.no> wrote: >Jim Propp wrote: >> The Margulis Napkin Problem asks one to prove that it is impossible to >> fold a unit square to form a flat shape who perimeter is greater than 4. ... (deletia) >> Jim Propp > >SOLUTION: >If you have a piece of paper with ANY shape, I wish to prove that >when folding it, the circumference will be reduced. Say that you > ...(proof that any fold of single thickness shape reduces circumference) > >Hence, folding any shape once reduces the circumference. Then, of >course, repeated folding will reduce the circumference. >-- >Einar Andreas Rodland E-mail: einara@math.uio.no > The above is not a full solution. If your paper likes to stick to itself so much that after any fold you may again consider yourself to have only a single thickness of paper, the above argument works as advertised. However, even the most trivial of origami folds (including a mountain fold somewhere, for example) requires that the paper be partially unfolded at some point. Not all flat folded shapes are achievable from simple folds of the type outlined above. Now, if someone wants to show that the *shadow* of any flat folded figure is achievable with the shadow of a figure including only simple folds, the above is the required final step. However, I don't believe that part about shadow achievability. :-) I think a proof would have to consider an arbitrarily folded flat figure and the prover should be careful with any inductions used. Doug -- lepro@math.wisc.edu -- Douglas R. Lepro lepro@math.wisc.edu

From:greg@math.uiuc.edu (Greg Kuperberg)Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:2 Mar 1996 20:46:03 GMTOrganization:Yale department of mathematics

In article <3136FB25.4F107A44@math.uio.no> Einar Andreas Rodland <einara@math.uio.no> writes: >> The Margulis Napkin Problem asks one to prove that it is impossible to >> fold a unit square to form a flat shape who perimeter is greater than 4. ... >Hence, folding any shape once reduces the circumference. Yes, this is not too hard. >Then, of course, repeated folding will reduce the circumference. This reasoning doesn't work with the intended terms of the question. If by "fold" you mean a composition of maps (x,y) -> (|x|,y), then yes. But in the more usual sense of folding, the perimeter can go back up when you make a second fold: _______ /. | / . | ___/... | | / . | | / . | |/ . | / . | /. . | / .. | /... | | | |________________| So a reasonable rigorous interpretation of the question is: If f is a continuous piecewise isometry from the square [0,1]^2 to the plane R^2, is the perimeter of f([0,1]^2) not more than 4, with equality only for isometries? Also, I'd like to know about a generalization: Does there exist a shape of napkin the can be folded so that its perimeter goes up?

From:propp@math.mit.edu (Jim Propp)Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:3 Mar 1996 19:43:07 -0500Organization:MIT Department of Mathematics

>The Margulis Napkin Problem asks whether it is possible to fold a unit >square to form a flat shape whose perimeter is greater than 4. Several people have submitted incorrect solutions that neglect the fact that parts of the paper that disappear from view can reappear when a subsequent folding takes place. For instance, take a piece of paper and draw two horizontal lines, 4/9 and 5/9 of the way down the page. Make a mountain fold along one line. Now make a valley fold along the other line. The upshot is that the perimeter need not be a decreasing function of time, so simple proofs-by-induction like the one recently posted here will not suffice. Jim Propp

From:Einar Andreas Rodland <einara@math.uio.no>Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:Mon, 04 Mar 1996 14:15:19 +0100Organization:University of Oslo

Einar Andreas Rodland wrote: > > Jim Propp wrote: > > > > The Margulis Napkin Problem asks one to prove that it is impossible to > > fold a unit square to form a flat shape who perimeter is greater than 4. : > > SOLUTION: > > If you have a piece of paper with ANY shape, I wish to prove that > when folding it, the circumference will be reduced. Say that you > fold it along a line AB where A and B are the endpoints, and where > the line AB is included in the paper before folding. (If there is > a hole in the paper or the paper is non-convex, AB may pass over a > region which is not included in AB. We will deal with this later.) > : It has been pointed out to me by several that my proof only covers a group of special cases: foldings that may be described by a line segment and where the paper is folded along that segment. There are several foldings that may not be described this way, in particular cases where only the upmost sheet of paper is folded. I cannot see any way of fixing the proof. So to conclude, I am (we are?) back in the wilderness again. :-) Einar -- Einar Andreas Rodland E-mail: einara@math.uio.no University of Oslo, Norway Departement of Mathematics http://www.math.uio.no/~einara

From:Thomas Mautsch <mautsch@mathematik.hu-berlin.de>Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:Mon, 04 Mar 1996 17:08:07 +0100Organization:Humboldt Universitaet zu Berlin

Einar Andreas Rodland wrote: > > Jim Propp wrote: > > > > The Margulis Napkin Problem asks one to prove that it is impossible to > > fold a unit square to form a flat shape who perimeter is greater than 4. > > ... > > SOLUTION: > > If you have a piece of paper with ANY shape, I wish to prove that > when folding it, the circumference will be reduced. ... This statement cannot be right because, if you folded the result of your folding back into the original state, you would get the piece of paper you started with but this time with smaller circumference (perimeter?). Contradiction. However, I would like to see a proper solution myself. Sorry for the inconvenience Tom -- ------------------------------------------------------------------------------- Thomas Mautsch mautsch@mathematik.hu-berlin.de -------------------------------------------------------------------------------

From:hoey@aic.nrl.navy.mil (Dan Hoey)Newsgroups:sci.math.researchSubject:Re: The Margulis Napkin ProblemDate:05 Mar 1996 03:14:31 GMTOrganization:Navy Center for Artificial Intelligence

propp@math.mit.edu (Jim Propp) writes: > >The Margulis Napkin Problem asks whether it is possible to fold a > >unit square to form a flat shape whose perimeter is greater than 4. > Several people have submitted incorrect solutions that neglect the > fact that parts of the paper that disappear from view can reappear > when a subsequent folding takes place.... Quite so, but it is not even that simple--your mention of a "subsequent folding" suggests an intention to apply one folding at a time to the napkin. But I doubt that every locally isometric map is achievable by a discrete sequence of simple foldings, even when we allow both folding parts together and unfolding previously folded sections. As a candidate for this complication, I offer a shape that I hope will _not_ become known as "Hoey's hankie". Form a radiating fan-fold with apex A whose circumference BCDEFG has repeated z-shaped overlaps. B +---------+_ A The perimeter angle BAG \ '|\-_ should be Pi - 2(DAC + FAE) \ '|`\ -_ so that BAG is a straight \ ' | `\ -_ line when the fans are \ ' | ` \ -_ unfolded. Create a \ ' | ` \ -_ duplicate fanfold with \' | ` \ -_ circumference GHJKLB |\ | ` \ -_ connected to the original | \ | ` \ -_ along BAG. As shown, this | \| ` \ -_ would unfold into some kind | _+ ` \ -_ of decagonal shape | _- C ` \ _+ G BCDEFGHJKL with internal |_- ` \ _- point A, but it can be +-------------------+ E _- trimmed to form a square D | / _- enclosing A. | / _- | /_- I'm pretty sure you can't + fold this one fold at a F time. For another complication, consider that this example can be constructed by manipulations in three-space, using inelastic piecewise flat paper with a finite number of fold lines. But I don't see any reason why the existence of such a construction is guaranteed in general. Could there be a shape that you could not form without temporarily bending the paper into a curve? Could there be one that requires stretching or cutting and pasting? I don't know if these complications lead us toward counterexamples to the original conjecture. They do make the attempts at proofs by "inductive construction" more dubious, though. Dan Hoey This article was e-mailed and also Hoey@AIC.NRL.Navy.Mil submitted for sci.math.research.

To:eppstein@ics.uci.eduSubject:Margulis napkin problemDate:Tue, 12 May 98 19:33:31 -0400From:"Gregory B. Sorkin" <sorkin@watson.ibm.com>

Dear David, Just browsed through your geometry junkyard, whose Margulis napkin problem page leaves the impression that the proposition is true, if not quite proved. As your mathematical origami page points out, it's false, and you might want to give a hint of that in the other page (or throw it out entirely?). Furthermore, it seems that arbitrarily large perimeter is possible. Maybe you already know this, but, imagining a silk handkerchief rather than paper, rule it into an nxn grid, and gather the perimeter of each little square into a point. If you can do this, you have n^2 pillae each of height O(1/n), and sharing a common point as a base; splaying them out to all sides gives perimeter O(n). It seems I was not the first to realize this, and I am assured by Robert Lang that the folding is indeed feasible, and that this is proved by various papers here and there, albeit not all in one place. -Greg

Date:Wed, 11 Oct 2000 23:00:10 -0400From:Lars Huttar <lars_huttar@sil.org>To:eppstein@ics.uci.eduSubject:suggested additions to your page on the Margulis napkin p...

Subject: suggested additions to your page on the Margulis napkin problem --------------------------------- Hello, For a more complete explanation of how the Margulis napkin problem is solved, you might want to add the following exchange to your web page. I got the following from http://origami.kvi.nl/archives/a0028x/arc00282.txt (without permission of the authors).

Date:Fri, 11 Apr 1997 00:54:27 -0300 (ADT)From:Rjlang@aol.comSubject:Re: [propp@math.mit.edu: Margulis napkin problem]

Jeannine Mosely forwarded to origami-L a query from Jim Propp: >>>> Has anyone heard of the "Margulis napkin problem"? (I don't know whether it is indeed due to Margulis.) This innocuous-sounding puzzle merely asks whether it is possible to fold a square piece of paper (no tearing allowed!) so that the resulting flat figure has larger perimeter than the original square did. Can anyone find a proof that it can't be done? <<<< and Mark Casida suggested: >>>> Must the folded figure be convex? Or can it be e.g. star shaped? [What if I take an origami sea urchin and (shudder) press it flat on the table? Won't that have a very large perimeter?] <<<< which is exactly the right strategy. Not only can you make the perimeter of the star-shaped base larger than the original square; you can make it arbitrarily large. If you fold an order-N Sea Urchin (from Origami Sea Life), it has N^2 points, each of length (1/(2(N-1))). If you make the points arbitrarily thin (using lots and lots of sink folds!), when you flatten it, you'll get a total perimeter of N^2/(N-1), which is unbounded as N is large. You don't have to go to this extreme, however. If you thin the points of a Bird Base, you can splay the points out into a shape with a perimeter greater than a square. The trick in either case is to create one or more middle points. Robert J. Lang rjlang@aol.com

Date:Fri, 11 Apr 1997 11:55:20 -0300 (ADT)From:Jeannine Mosely <j9@concentra.com>Subject:Re: [propp@math.mit.edu: Margulis napkin problem]

Robert Lang wrote: Jeannine Mosely forwarded to origami-L a query from Jim Propp: >>>> Has anyone heard of the "Margulis napkin problem"? (I don't know whether it is indeed due to Margulis.) This innocuous-sounding puzzle merely asks whether it is possible to fold a square piece of paper (no tearing allowed!) so that the resulting flat figure has larger perimeter than the original square did. Can anyone find a proof that it can't be done? <<<< and Mark Casida suggested: >>>> Must the folded figure be convex? Or can it be e.g. star shaped? [What if I take an origami sea urchin and (shudder) press it flat on the table? Won't that have a very large perimeter?] <<<< which is exactly the right strategy. Not only can you make the perimeter of the star-shaped base larger than the original square; you can make it arbitrarily large. If you fold an order-N Sea Urchin (from Origami Sea Life), it has N^2 points, each of length (1/(2(N-1))). If you make the points arbitrarily thin (using lots and lots of sink folds!), when you flatten it, you'll get a total perimeter of N^2/(N-1), which is unbounded as N is large. You don't have to go to this extreme, however. If you thin the points of a Bird Base, you can splay the points out into a shape with a perimeter greater than a square. The trick in either case is to create one or more middle points. Not so fast, Robert! When you flatten the sea Urchin, portions of each point overlap neighboring points, reducing the total perimeter. And I can't get the bird base trick to work either, at least not without little tears appearing in the edges of the paper as the points spread apart. Can you check your theory, and give more specific instructions? -- Jeannine Mosely

Date:Sat, 12 Apr 1997 04:38:33 -0300 (ADT)From:Rjlang@aol.comSubject:Re: [propp@math.mit.edu: Margulis napkin problem]

To recap: Jeannine posted a query about whether it's possible to fold a shape with a perimeter larger than the original square; Mark Casida suggested squashing a Sea Urchin; and I observed that: ..you fold an order-N Sea Urchin (from Origami Sea Life). It has N^2 points, each of length (1/(2(N-1))). ****If you make the points arbitrarily thin**** [emphasis added] (using lots and lots of sink folds!), when you flatten it, you'll get a total perimeter of N^2/(N-1), which is unbounded as N is large. and You don't have to go to this extreme, however. ****If you thin the points**** [emphasis added] of a Bird Base, you can splay the points out into a shape with a perimeter greater than [that of] a square. Jeannine takes me to task: >>>> Not so fast, Robert! When you flatten the sea Urchin, portions of each point overlap neighboring points, reducing the total perimeter. And I can't get the bird base trick to work either, at least not without little tears appearing in the edges of the paper as the points spread apart. Can you check your theory, and give more specific instructions? <<<< I added the asterisks to my original comments to emphasize an important point; if you're really going to try this, you definitely have to thin the points, or as Jeannine points out, you'll lose perimeter due to the regions where the points overlap. The thinner you make the flaps, the less you lose. And in fact, as you'll see below, you have to thin them a _lot_ just to reach break-even. To quantify this and to provide a specific example in the case of the Bird Base, take a unit square (I get these from OUSA Supplies) and fold a Bird Base in the all-flaps-down position (kite-shaped). Denote the height of the top triangle by z (z is (Sqrt(2)-1)/2, but that's not important to the argument). Now narrow all four long flaps (and the top flap) by sinking the _sides_ in and out on parallel creases, dividing each side into nths. After sinking, spread-sink one flap on each side, so you end up with a real skinny thing with one flap pointing upward and two flaps on the left and right pointing down. Reverse-fold two of the downward-pointing flaps out to each side, and spread the two remaining downward-pointing flaps slightly so there is a gap between them. Now, your shape lies completely flat and has four long flaps and one shorter one. Because of overlapping layers, each of the long flaps, which ideally would have a perimeter of slightly more than (1), has lost (2z/n) in length. The top flap has a perimeter slightly over (2z). So the total perimeter of the shape is 4(1-2z/n)+2z = 4 + 2z(1-4/n) (actually a teensy bit more because of some angled edges, which I'm neglecting for now). So if you compare this to the perimeter of the original square, you see that for n=4, you've just about broken even; but if you divide into 5ths or more, you'll come out ahead. And if you make the points "arbitrarily thin", which only occurs in pure mathematics and Origami Insects And Their Kin, the perimeter of the Bird Base shape approaches the value 4+2z, or about 4.414. Similar arguments (and many more sinks) apply to the Sea Urchin. Robert J. Lang rjlang@aol.com