6
$\begingroup$

Let's say you are given some random positive integer. Next, assume you are given the following sequence of integers: $$[1, 2, 3, 4, 5, 6, 7, 8, 9].$$

Now, assume you are allowed to use the following moves: Addition, Subtraction, Multiplication, and Division. Note: multiplication or division by zero is not allowed.

Here's the game: you have to reduce the random positive integer down to $1$ by using your choice of moves. The catch is that you have to use every element in the sequence once and only once. For a concrete example, consider the following set of moves for the number $2752$:

$$2752 \div 8 = 344\ \ \ \ \ [1,2,3,4,5,6,7,9]$$ $$344 - 1 = 343\ \ \ \ \ [2,3,4,5,6,7,9]$$ $$343 \div 7 = 49\ \ \ \ \ [2,3,4,5,6,9]$$ $$49 \times 4 = 196\ \ \ \ \ [2,3,5,6,9]$$ $$196 - 5 = 191\ \ \ \ \ [2,3,6,9]$$ $$191 - 2 = 189\ \ \ \ \ [3,6,9]$$ $$189 \div 9 = 21\ \ \ \ \ [3, 6]$$ $$21 \div 3 = 7\ \ \ \ \ [6]$$ $$7 - 6 = 1$$

I am curious about this sort of game.

I want to know for what integers will this game work? Clearly there is an upper bound, i.e. a maximum integer for which this game, as constructed, will work. In this case, that maximum integer is $ 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 + 1 = 362881$. However, surely not all integers up to $362881$ can be reduced to $1$ given the constraints of this game.

On the other hand, assuming the game always gives you a whole number to reduce, there should be an infinite number of sequences of integers for which that given whole number can be reduced to $1$ using the available moves. This comes from the fact that these whole numbers are, of course, algebraic numbers. However, for now let's assume the only sequence of integers we are allowed to use is $[1,2,3,4,5,6,7,8,9]$.

A weaker version of my question would be something like the following: Am I guaranteed to be able to reduce any 4-digit integer to $1$ using the constraints of this game? If not, then can I reduce any 3-digit integer? In general, is there a method other than brute force to find the greatest integer $x$ such that for all $N \leq x$, $N$ can be reduced to $1$?

$\endgroup$
  • 5
    $\begingroup$ play game in reverse order, start from $1$ and reach all possible number by using $1,2,3,..,9$ $\endgroup$ – mesel Jun 20 '14 at 10:32
  • 5
    $\begingroup$ Actually the maximum would be $2\cdot9!$. $\endgroup$ – punctured dusk Jun 20 '14 at 10:38
  • 2
    $\begingroup$ $9!+1 = 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2 + 1 $ $\endgroup$ – Oleg567 Jun 20 '14 at 12:32
  • 1
    $\begingroup$ One thing that stands out, for me at least, is that it's not immediately clear how whether or not one number $x$ is attainable gives any real information about whether or not some number $y$ is also attainable. So, even if we were given the minimum unattainable number for free, it's not clear how a non-brute force solution would be able to show that every smaller positive integer is attainable. $\endgroup$ – Dennis Meng Jun 21 '14 at 5:03
  • 2
    $\begingroup$ I was way wrong, there are a lot of collisions for almost any number. Here's all of the solutions for the list $[1, 2, 3, 4]$, where $1$ is the target: pastebin.com/zf1QZfED. The solutions for the range $[1, 7]$ was 341MB and the growth is exponential (or maybe worse), so I won't be pasting $[1, 9]$. $\endgroup$ – Tyler Jun 23 '14 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.