NCO (Cyber Olympiad) /Logical Reasoning

Paper Folding and Cutting

Non-Verbal Reasoning · free study notes

Paper‑Folding and Cutting – Logical Reasoning Study Notes

(MIT‑Level Treatment for the NCO Cyber Olympiad)


1. Introduction

Paper‑folding and cutting problems are a classic family of logical‑reasoning puzzles.
They combine combinatorial geometry, topology, and discrete mathematics in a single, seemingly simple activity.
Typical tasks ask: “After a series of folds and cuts, how many pieces do we obtain?” or “What is the shape of the final cut?”

These notes present a rigorous, first‑principles framework for analyzing such puzzles.
We cover:

  1. Mathematical prerequisites – planar graphs, Euler’s formula, combinatorial topology.
  2. Formal model – paper as a 2‑manifold, folds as homeomorphisms, cuts as 1‑dimensional submanifolds.
  3. Counting arguments – how many pieces, how many edges, how many vertices.
  4. Edge cases – overlapping folds, non‑planar cuts, self‑intersections.
  5. Advanced tools – dual graphs, medial graphs, Euler characteristic invariants.
  6. Challenging problem – an open‑style question for deeper exploration.

2. Mathematical Prerequisites

Concept Definition Relevance
Planar graph A graph drawn in the plane with no crossing edges. Folds and cuts can be represented as planar graphs.
Euler’s formula For a connected planar graph, (V - E + F = 2). Allows counting pieces (faces) after cuts.
Faces Maximal connected regions bounded by edges. Each face corresponds to a paper piece.
Dual graph Vertices correspond to faces of the primal; edges cross primal edges. Useful when cuts are many and intertwined.
Medial graph Vertices at edge midpoints; edges connect adjacent midpoints. Captures adjacency of cuts.
Euler characteristic (\chi = V - E + F) for surfaces; invariant under homeomorphisms. Folding preserves (\chi).

3. Formal Model

3.1 Paper as a 2‑Manifold

  • Let (P) be a closed, orientable 2‑manifold (the paper).
  • Initially (P) is a disk: (V=1) (interior vertex), (E=0), (F=1).
  • Folding: a homeomorphism (f: P \to P) that identifies two regions along a line (the fold line).
  • Cutting: a simple closed curve (\gamma\subset P) (or a set of such curves).

3.2 Folds as Edge Identifications

When folding along a line (L) (a straight segment), we identify points (x\in L) with their reflection (x').
This introduces a new edge in the underlying graph: the fold edge.
If the fold is performed twice or more, we may get multiple edges between the same pair of vertices.

3.3 Cuts as Graph Edges

A cut (\gamma) splits the surface along (\gamma).
Topologically, cutting removes the interior of (\gamma) and adds two boundary edges (the two sides of the cut).
If (\gamma) self‑intersects, each intersection becomes a vertex in the graph.


4. Counting Pieces – Euler’s Formula in Action

After all folds and cuts, we obtain a planar graph (G=(V,E,F)).
Our goal: compute (F), the number of paper pieces.

4.1 Basic Formula

For a connected configuration:

[ F = E - V + 2 . ]

  • Vertices (V):

    • All fold midpoints (fold vertices).
    • All cut intersection points.
    • Endpoints of cuts touching the paper boundary.
  • Edges (E):

    • Segments of cuts between vertices.
    • Fold lines (treated as edges).
    • Boundary edges (the outer perimeter of paper).

4.2 Example

Fold the paper once along a straight line, then cut a single straight line perpendicular to it crossing the fold.

  • (V = 1) (intersection of cut and fold).
  • (E = 4) (two cut segments + two fold segments).
  • (F = 4 - 1 + 2 = 5).

Indeed we obtain 5 pieces: 4 quadrants plus the central cross‑cut piece.


5. Edge Cases & Special Situations

Case Issue Resolution
Overlapping folds Two folds may superimpose, creating a single edge counted twice. Merge edges; treat as a single edge in (E).
Non‑planar cuts Cuts that go over other cuts (i.e., a cut passes through a fold). Model as cross‑overs in the graph; add a vertex at the crossing.
Self‑intersecting cuts A cut may loop and intersect itself. Each self‑intersection is a vertex; recompute (V,E).
Disconnected paper After many cuts, the paper may split into several components. Apply Euler’s formula to each component separately; sum (F).
Infinite folds Repeated folding can lead to an infinite graph. Use limiting arguments; often the number of pieces stabilizes.

6. Advanced Tools

6.1 Dual Graph Approach

The dual graph (G^*) has a vertex for each face.
Edges connect adjacent faces across shared edges.
Useful when the number of pieces is large: instead of counting faces directly, count vertices in the dual.

6.2 Medial Graph & Knot Theory

When cuts form closed loops that cross each other (like knot diagrams), the medial graph encodes adjacency of edges.
Knot invariants (e.g., crossing number) can help bound the number of pieces.

6.3 Euler Characteristic Invariance

Folding does not change (\chi); cutting adds to (\chi) because each cut increases (E) and (F) by 1.
Hence, after (k) cuts (ignoring intersections), we have (\chi' = \chi + k).
For a disk, (\chi=1), so (F = k + 1) when cuts are disjoint.


7. Challenging Problem

**

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.