Ken's Puzzle of the Week
Lacing (Short) Shoes
| In how many ways can you lace shoes with 2/3/4 pairs of eyelets?
Label the eyelet pairs from top to bottom: |
|
Restrictions:
- Lacing must begin with eyelet A and end with eyelet B. A and B
will be tied across together.
- Each eyelet is used exactly once.
- Laces run straight from one eyelet to another.
- Over/under and top/bottom are not important. Only eyelet-to-eyelet
connections are important. For example, for 2 pairs, ADCB is equivalent to BCDA,
even though the "top" lace would be different between the two in actual
practice.
- Each eyelet must have at least one useful connection across the pairs to
tighten the shoe. Thus, for 3 pairs, AECFDB would not be valid because
E and D do not contribute to tightening. AEFCDB would be valid since A
crosses to B, C to D&F, and E to F.
Feel free to extend this to more pairs. However, I've read of
mathematicians analyzing this problem for seven pairs of eyelets and finding
millions of solutions. Is there a formula or recursive approach to
this?
Source: I didn't find the original source (if you find it, let me know.)
Here are some related links:
Optimum Shoe
Lacing,
Ian's
Shoelace Site.
Solution
Mail to Ken