From: propp@math.mit.edu (Jim Propp)
Date: 14 Feb 1996 01:51:48 -0500
Newsgroups: sci.math.research
Subject: 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.math
Subject: Max circumference of folded paper (solution)
Date: Tue, 20 Feb 1996 21:30:53 +0100
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: Sat, 02 Mar 1996 04:11:16 -0800
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: 2 Mar 1996 19:18:33 GMT
Organization: University of Wisconsin, Madison
Summary: 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.research
Subject: Re: The Margulis Napkin Problem
Date: 2 Mar 1996 20:46:03 GMT
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: 3 Mar 1996 19:43:07 -0500
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: Mon, 04 Mar 1996 14:15:19 +0100
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: Mon, 04 Mar 1996 17:08:07 +0100
Organization: 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.research
Subject: Re: The Margulis Napkin Problem
Date: 05 Mar 1996 03:14:31 GMT
Organization: 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.edu
Subject: Margulis napkin problem
Date: Tue, 12 May 98 19:33:31 -0400
From: "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 -0400
From: Lars Huttar <lars_huttar@sil.org>
To: eppstein@ics.uci.edu
Subject: 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.com
Subject: 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.com
Subject: 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