In how many ways can a strip of n blank stamps be folded?
combinatorics/stamp.folding New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
In how many ways can a strip of n blank stamps be folded? [ Editor: problem statement reconstructed from the postings, which discuss Andy Pepperdine's table of the number of ways of folding a strip of stamps, blank on both sides, and its disagreement with the numbers in N. J. A. Sloane's _Handbook of Integer Sequences_ (1973), sequence 576. ]
Show solution
ahp@pact.srf.ac.uk (Andy Pepperdine) notes a discrepancy in reported
numbers of ways of folding a strip of stamps:
> stamps Me Wells Sloane
> 1 1 1 .
> 2 1 1 1
> 3 2 2 2
> 4 5 5 5
> 5 14 14 14
> 6 38 38 39 !!
> 7 120 120 120
> 8 353 353 358 !!
> 9 1148 1148 1176 !!
> 10 3527 3527
The problem with the stamp folding problem is that there is more than
one problem. I'll call them the sticky-stamp folding problem and the
dry-stamp folding problem.
In the sticky-stamp folding problem, every time you make a fold, you
have to flatten it completely, and the stamps on the two sides of the
fold stick together and can't be unfolded later. In the dry-stamp
folding problem you can partially unfold a previous fold to make a new
fold.
The fundamental dry-stamp fold that you can't make with sticky stamps
is the extended S:
________________
________)
(________________
because whichever fold you make first, the second is prohibited.
The smallest completely folded strip you can't form with sticky stamps
is:
_____1_________________
/ _____6_______________
/ (_______5___________ \
( _________4_________) \
\ (___________3_______ )
\_______________2_____) /
_________________7_____/
If you unfold it carefully, using only the inverses of sticky-stamp
folds, you'll find yourself with some variation of the extended S.
This is why you found the discrepancy with a strip of seven stamps.
The situation becomes much more complicated in two dimensions, when
there are folded positions in which a sheet could exist (without
stretching or self-intersection), but which might be difficult or
impossible to create starting with a flat sheet and manipulating it in
three dimensions. Consider a flat tube that swallows its tail
ouroborously, for instance. I have never been able to put together
even a 3x4 example of this, though I imagine it's possible with the
sufficiently smooth paper. With a 3x5 sheet, you can have
interlocking cuffs that may be impossible to build without some sort
of smart paper.
legendre@ens.fr (Stephane Legendre) sent sci.math an article about the
dry-stamp problem in July. He lists the following values:
n | 2 3 4 5 6 7 8 9 10
-----+-----------------------------------------------
b(n) | 1 2 5 14 39 120 358 1176 3527
-----+-----------------------------------------------
n | 11 12 13 14 15 16
-----+------------------------------------------------
b(n) | 11622 36627 121622 389560 1301140 4215748
-----+------------------------------------------------
citing J. E. Koehler 1968, "Folding a strip of stamps", Journal of
Combinatorial Theory 5 (1968) 135-152
I hadn't heard of published material describing the sticky-stamp
problem or the difference between the two models. I am surprised to
hear that _Martin_Gardner's_Sixth_Book_of_Mathematical_Recreations_
uses the sticky numbers, because his book _Wheels,_Life_and_Other_
_Mathematical_Amusements_ uses W. F. Lunnon's results on folding dry
two-dimensional maps.
-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>
I haven't been able to come up with a closed form solution or anything
like that, but I can confirm and extend your table a bit:
11 : 11622
12 : 36627
13 : 121622
14 : 389560
15 : 1301140
16 : 4215748
It looks like it's growing by a pretty constant factor of around 3.2.
My program (in C) runs in decidedly exponential time, taking about 5.2
times longer for each n. n = 16 took 24 hours of processor time (on
this 50MHz 486 based machine).
-- David Gibson <dgibson@cs.uct.ac.za>
[ Editor: Dan Hoey's follow-up, titled "Correction": ]
I wrote:
> The problem with the stamp folding problem is that there is more than
> one problem. I'll call them the sticky-stamp folding problem and the
> dry-stamp folding problem.
which is true as far as it goes, but it is not the source of the
discrepancy. For instance, it does not make a difference until the
number of stamps reaches 7, as careful readers of my message may have
noticed. It seems everyone here has indeed been dealing with the
dry-stamp problem.
According to Stephane Legendre's survey of the (dry) stamp-folding
literature, posted to sci.math three months ago, the following
sequences appear in Sloane's handbook of integer sequences:
n | 2 3 4 5 6 7 8 9 10
-----+------------------------------------------------
b(n) | 1 2 5 14 39? 120 358? 1176? 3527
-----+------------------------------------------------
k(n) | 0 2 4 6 8 18 20 56 48
-----+------------------------------------------------
r(n) | 2 2 4 10 24 66 174 504 1406
n | 11 12 13 14 15 16
-----+------------------------------------------------
b(n) | 11622 36627 121622 389560 1301140 4215748
-----+------------------------------------------------
k(n) | 178 132 574 348 1870 1008
-----+------------------------------------------------
r(n) | 4210 12198 37378 111278 346846 1053874
Where b(n) (Sloane's #576) is the number of ways of folding a strip of
n blank stamps, k(n) (#120) is the number of top-bottom symmetric ways
of folding n marked stamps, and r(n) (#464) is the number of ways of
folding n marked stamps with the first stamp at the top. He remarks
that
b(n) = (n r(n) + k(n))/4,
which is not satisfied by the columns in which question marks appear.
In fact, the numbers for b(n) seem to be in error, as Andy Pepperdine
noticed. Andy's corrected numbers are confirmed by David Gibson, and
reconfirmed by a program I wrote independently. In fact, they are
`confirmed' by the other sequences in Sloane, assuming they are all
listed that far. So the following seems to be the corrected table.
n | 2 3 4 5 6 7 8 9 10
-----+------------------------------------------------
b(n) | 1 2 5 14 38 120 353 1148 3527
-----+------------------------------------------------
k(n) | 0 2 4 6 8 18 20 56 48
-----+------------------------------------------------
r(n) | 2 2 4 10 24 66 174 504 1406
n | 11 12 13 14 15 16
-----+------------------------------------------------
b(n) | 11622 36627 121622 389560 1301140 4215748
-----+------------------------------------------------
k(n) | 178 132 574 348 1870 1008
-----+------------------------------------------------
r(n) | 4210 12198 37378 111278 346846 1053874
-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>
I mentioned this discrepancy in the number of ways n blank stamps can
be folded to Neil Sloane, and he said:
> thanks for telling me about the discussion - i have not seen it
>
> if you feel like it, tell them i am aware of the error,
> that it was corrected a long time ago,
> that there will be a new edition out probably next year,
> and that my email address is njas@research.att.com
>
> the new book will be about twice the length of the first, and i am
> still collecting sequences for it
-- David Applegate <david@research.att.com>, October 1993