The Glitching Orb Problem

I decided today I wanted to create a math problem, as I have been really interested in Bill Gates' "Pancake Flip" problem. I decided to create my own because I wanted something to work on myself-- now if I wanted, I could just work on the pancake flip problem, but what is the fun in that? Anyway, down below is the problem.

Problem Overview

Imagine you are given a list of n orbs. Each orb has:

A unique number from 1 to n

A polarity, either Normal (N) or Reflected (R)

Glitch Flip Operation

You may perform a series of Glitch Flips on any contiguous subarray of the list. A Glitch Flip performs the following steps:

Reverses the selected subarray

Flips the polarity of each orb in the subarray, so:

N becomes R

R becomes N

Adjusting the Number

Each Glitch Flip also modifies the number on each orb:

• If an orb is now Normal (N), increase its number by 1.
• If an orb is now Reflected (R), decrease its number by 1.

All numbers must remain in the valid range [1, n]. If a flip would cause any number to fall outside this range, the flip is considered invalid and cannot be performed.

Goal

The goal is to transform any starting configuration into the following solved state:

[N1, N2, N3, ..., Nn]

That is, the orbs must be in increasing order from 1 to n, and all must have polarity Normal (N).

Mathematical Challenges

1. Minimum Moves Problem

For a given starting configuration, determine the minimum number of Glitch Flips needed to reach the goal state.

2. Worst-Case Function G(n)

Let G(n) represent the maximum number of flips needed to solve any valid configuration of n orbs.

Open questions include:

• What is the growth rate of G(n)?
• Is it linear, polynomial, logarithmic, or exponential?

3. Upper and Lower Bounds

• Lower bound: Prove that at least a certain number of moves are needed in the worst case.
• Upper bound: Show that a valid solution always exists within a certain number of moves.

4. Solvable vs. Unsolvable States

Some starting configurations may be unsolvable due to the interaction of polarity and number limits.

• Can we identify or classify these cases?
• Is there an efficient way to check if a state is solvable?

5. Algorithm Design

• Can you build an algorithm that solves any configuration, even if it's not optimal?
• Can you design one that always solves it in the fewest possible steps?

Known Values of G(n)

Below is a table of known worst-case move counts for small values of n. These were found by testing all configurations manually or via exhaustive search.