Here's a puzzle game. I call it Reverse the List of Integers. How it works is, you start with a list of positive integers, (e.g. [7, 5, 3]) and your goal is to make the same list, in reverse ([3, 5, 7]). You have two moves you can make:
1) Split an integer into two smaller integers. (e.g. [7, 5, 3] → [6, 1, 5, 3])
2) Combine (add) two integers into a larger one. (e.g. reverse the last e.g.)
There are two restrictions that seem natural for making this into an interesting game:
1) You can never make an integer greater than the largest integer in the original list.
2) You can never make a move that results in the same integer appearing in the list more than once.
With these rules, even pretty simple lists can make non-trivial puzzles. (Try it with [7, 5, 3].) Some questions:
1) What are good algorithms, or even general strategies, for solving these?
2) For a given n, there must be some puzzle where n is the largest number in the list, and the number of moves required to solve the puzzle is maximized. What does the sequence of maximal required moves look like as a function of n? What do the "hardest" puzzles look like? Is there a way to determine either without using brute force?
@two_star Conjecture: if a list of two integers has at least one greater than 6, reversal requires no more or less than four moves.
Notes: By parity on the length of the list, only even numbers of moves can work. Also, two moves can't reverse a list, except by using an invalid position.
Outline: Choose distinct positive integers x, y, z such that the larger integer in the starting list is x+y+z and the smaller is either x or x+y. One of these sequences of steps should work, provided other collisions are avoided:
1. xyz x
xy z x
xy zx
x y zx
x yzx
2. xyz xy
xyz x y
xy z x y
xy zx y
xy zxy