skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on October 8, 2026

Title: The Stamp Folding Problem From a Mountain-Valley Perspective
A strip of square stamps can be folded in many ways such that all of the stamps are stacked in a single pile in the folded state. The stamp folding problem asks for the number of such foldings and has previously been studied extensively. We consider this problem with the additional restriction of fixing the mountain-valley assignment of each crease in the stamp pattern. We provide a closed form for counting the number of legal foldings on specific patterns of mountain-valley assignments, including a surprising appearance of the Catalan numbers. We describe results on upper and lower bounds for the number of ways to fold a given mountain-valley assignment on the strip of stamps, provide experimental evidence suggesting more general results, and include conjectures and open problems. Journal version  more » « less
Award ID(s):
2149647 2428771 2347000
PAR ID:
10641664
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Discrete Mathematics and Theoretical Computer Science (DMTCS) is a non-profit organization governed by the French law of 1901. It is only concerned with the management and distribution of DMTCS.
Date Published:
Journal Name:
Discrete Mathematics & Theoretical Computer Science
Volume:
vol. 27:3
Issue:
Combinatorics
ISSN:
1365-8050
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Given a locally flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on the plane) with a mountain-valley (MV) assignment $$\mu:E\to\{-1,1\}$$ indicating which creases in $$E$$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $$F$$ of $$G$$ to create a new MV assignment $$\mu_F$$ which equals $$\mu$$ except for all creases $$e$$ bordering $$F$$, where we have $$\mu_F(e)=-\mu(e)$$. In this paper we explore the configuration space of face flips that preserve local flat-foldability of the MV assignment for a variety of crease patterns $$G$$ that are tilings of the plane. We prove examples where $$\mu_F$$ results in a MV assignment that is either never, sometimes, or always locally flat-foldable, for various choices of $$F$$. We also consider the problem of finding, given two locally flat-foldable MV assignments $$\mu_1$$ and $$\mu_2$$ of a given crease pattern $$G$$, a minimal sequence of face flips to turn $$\mu_1$$ into $$\mu_2$$. We find polynomial-time algorithms for this in the cases where $$G$$ is either a square grid or the Miura-ori, and show that this problem is NP-complete in the case where $$G$$ is the triangle lattice. 
    more » « less
  2. Bansal, M (Ed.)
    Predicting the secondary structure of RNA is an important problem in molecular biology, providing insights into the function of non-coding Rn As and with broad applications in understanding disease, the development of new drugs, among others. Combinatorial algorithms for predicting RNA foldings can generate an exponentially large number of equally optimal foldings with respect to a given optimization criterion, making it difficult to determine how well any single folding represents the entire space. We provide efficient new algorithms for providing insights into this large space of optimal RNA foldings and a research software tool, toRNAdo, that implements these algorithms. 
    more » « less
  3. Abstract Mountain System Recharge processes are significant natural recharge pathways in many arid and semi‐arid mountainous regions. However, Mountain System Recharge processes are often poorly understood and characterized in hydrologic models. Mountains are the primary water supply source to valley aquifers via lateral groundwater flow from the mountain block (Mountain Block Recharge) and focused recharge from mountain streams contributing to focused Mountain Front Recharge at the piedmont zone. Here, we present a multi‐tool isogeochemical approach to characterize mountain flow paths and Mountain System Recharge in the northern Tulare Basin, California. We used groundwater chemistry data to delineate hydrochemical facies and explain the chemical evolution of groundwater from the Sierra Nevada to the Central Valley aquifer. Stable isotopes and radiogenic groundwater tracers validated Mountain System Recharge processes by differentiating focused from diffuse recharge, and estimating apparent groundwater age, respectively. Novel application of End‐Member Mixing Analysis using conservative chemical components revealed three Mountain System Recharge end‐members: (a) evaporated Ca‐HCO3water type associated with focused Mountain Front Recharge, (b) non‐evaporated Ca‐HCO3and Na‐HCO3water types with short residence times associated with shallow Mountain Block Recharge, and (c) Na‐HCO3groundwater type with long residence time associated with deep Mountain Block Recharge. We quantified the contribution of each Mountain System Recharge process to the valley aquifer by calculating mixing ratios. Our results show that deep Mountain Block Recharge is a significant recharge component, representing 31%–53% of the valley groundwater. Greater hydraulic connectivity between the Sierra Nevada and Central Valley has significant implications for parameterizing groundwater flow models. Our framework is useful for understanding Mountain System Recharge processes in other snow‐dominated mountain watersheds. 
    more » « less
  4. Abstract Midlatitude cyclones approaching coastal mountain ranges experience flow modifications on a variety of scales including orographic lift, blocking, mountain waves, and valley flows. During the 2015/16 Olympic Mountain Experiment (OLYMPEX), a pair of scanning ground radars observed precipitating clouds as they were modified by these orographically induced flows. The DOW radar, positioned to scan up the windward Quinault Valley, conducted RHI scans during 285 h of precipitation, 80% of which contained reversed, down-valley flow at lower levels. The existence of down-valley flow in the Quinault Valley was found to be well correlated with upstream flow blocking and the large-scale sea level pressure gradient orientated down the valley. Deep down-valley flow occurred in environments with high moist static stability and southerly winds, conditions that are common in prefrontal sectors of midlatitude cyclones in the coastal Pacific Northwest. Finally, a case study of prolonged down-valley flow in a prefrontal storm sector was simulated to investigate whether latent heat absorption (cooling) contributed to the event. Three experiments were conducted: a Control simulation and two simulations where the temperature tendencies from melting and evaporation were separately turned off. Results indicated that evaporative cooling had a stronger impact on the event’s down-valley flow than melting, likely because evaporation occurred within the low-level down-valley flow layer. Through these experiments, we show that evaporation helped prolong down-valley flow for several hours past the time of the event’s warm frontal passage. Significance StatementThis paper analyzes the characteristics of down-valley flow over the windward Quinault Valley on the Olympic Peninsula of Washington State using data from OLYMPEX, with an emphasis on regional pressure differences and blocking metrics. Results demonstrate that the location of precipitation over the Olympic Peninsula is shifted upstream during events with deep down-valley flow, consistent with blocked upstream airflow. A case study of down-valley flow highlights the role of evaporative cooling to prolong the flow reversal. 
    more » « less
  5. Abstract Field studies of hyporheic exchange in mountain systems are often conducted using short study reaches and a limited number of observations. It is common practice to assume these study reaches represent hyporheic exchange at larger scales or different sites and to infer general relationships among potential causal mechanisms from the limited number of observations. However, these assumptions of representativeness are rarely tested. In this study, we develop numerical models from four segments of mountain streams in different geomorphologic settings and extract shorter reaches to test how representative exchange metrics are in shorter reaches compared to their reference segments. We also map the locations of the representative reaches to determine if a pattern exists based on location. Finally, we compare variance of these shorter within‐site reaches to 29 additional reaches across the same basin to understand the impacts of inferring causal mechanisms, for example, the expectation that wide and narrow valley bottoms will yield different hyporheic exchange patterns. Our results show that the location and length strategy of the study reach must be considered before assuming an exchange metric to be representative of anything other than the exact segment studied. Further, it is necessary to quantify within and between site variations before making causal inferences based on observable characteristics, such as valley width or stream morphology. Our findings have implications for future field practices and how those practices are translated into models. 
    more » « less