Newsgroups: rec.puzzles
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: Fri, 1 Oct 1993 15:44:54 GMT
Subject: Re: Folding a strip of stamps

a...@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, everytime 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 diminesions.  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.

legen...@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