Booth Id:
MATH009
Category:
Mathematics
Year:
2026
Finalist Names:
Lin, Jia-Ying (School: Taipei First Girls High School)
Abstract:
The classical Josephus problem involves eliminating individuals in a circle based on a fixed skip number. This research uses a similar rule, allowing skip numbers to vary according to a permutation. This defines a Josephus transformation, creating a mapping among all permutations of length n.
We use these transformations to define the directed edges of a digraph (directed graph) where each permutation serves as a vertex. As n increases, the structure of the digraph becomes increasingly complex. To analyze the digraph's structure, we investigate in-degrees and cycles, proving any cycle's length is always a multiple of n. By reformulating reverse transformations as a System of Distinct Representatives (SDR) problem alongside congruence-set methods, we classify vertices, deeply analyze vertices with any fixed in-degree, and uncover significant structural symmetries, parity properties, and quantitative patterns emerging despite the digraph's chaotic nature.
Through this investigation, we found that classifying the vertices of in-degree i by their first entry reveals symmetry. The most striking result is discovering a special vertex whose in-degree admits a precise arithmetic characterization rather than a purely combinatorial one. Specifically, its in-degree equals sum of the number of ordered factorizations for integers from 1 to n-1. We conjecture that this vertex attains the maximum in-degree and can be expressed in closed form.
This study initiates a new combinatorial dynamical system on permutations, bridging combinatorial dynamics with number theory. We reveal that the Josephus transformation's complex behavior is ultimately governed by elegant arithmetic properties.
Awards Won:
The Scientific and Technological Research Council of Türkiye TUBITAK: 1st Prize Award
American Mathematical Society: Honorable Mention and One-Year Membership to AMS (for 5 projects with up to 3 team members per project)