A Remarkable Endofunction Involving Compositions
Yeong‐Nan Yeh · Studies in Applied Mathematics · 1995
We define a state as an arbitrary composition of a non‐negative integer n on m circularly labeled positions around a disk. A move is defined as the following endofunction: for each i, 1 ≤ i ≤ m; the value at position i (a non‐negative integer si) is distributed clockwise, one unit at a time, to itself and the following (si − 1) positions. The structures of states keep changing in irregular ways as we perform a series of moves. Definitions and necessary and sufficient conditions for cyclic states, root states, and leaf states are given in this paper. We provide the sharp upper bounds for the length of a path from a given nontrivial state to its nearest leaf state and for the length of a path from a given nontrivial state to its farthest leaf state in T(n, m). Surprisingly, it turns out that regardless of the initial state, one is sure to reach a cyclic state, which has only the values [n/m] and [(n + m − 1)/m] at all positions, in at most m − 1 moves.