Minimum steps on a numberline

Given an infinite numberline, you start at zero. On every i'th move you can either move i places to the right, or i places to the left. How, in general, would you calculate the minimum number of moves to get to a target point x? For example:

if x = 9:

move 1: starting at zero, move to 1

move 2: starting at 1, move to 3

move 3: starting at 3, move to 0

move 4: starting at 0, move to 4

move 5: starting at 4, move to 5

• This seems like another mathbook-type problem to me. – Mithical Aug 25 '16 at 11:47
• @Mithrandir I think so. VTC. – IAmInPLS Aug 25 '16 at 11:50
• I say "don't close" -- unless it is mandatory to have a real-life story enclosing the real puzzle to be solved. – Rosie F Aug 26 '16 at 3:15
• I want to go to school with these VTCers; clearly their textbooks have much more interesting problems than mine. – ffao Aug 26 '16 at 3:28
• Shouldn't the last line end with "move to 9"? – celtschk Aug 26 '16 at 9:23

3 Answers

First,

you need to find $n$, for which $S_n=1+2+\dots+n=\frac{n(n+1)}2\ge x$

Then,

find a subset of the numbers in range $[1, n]$ which sum to $\frac{S_n-x}2$. This can always be done if the parity of $S_n$ is the same as the parity for $x$. This means, that if $m$ is the lowest number for which $S_m\ge x$, then at least one of $S_m$, $S_{m+1}$ or $S_{m+2}$ will do the work.

With the help of this

adding the rest, and subtracting the above will give you the desired solution

First you calculate the smallest $n$ with $\frac{1}{2}n(n+1) \geq x$

if $\frac{1}{2}n(n+1)-x$ is odd then increase $n$ by $1$ if $n$ is even or increase $n$ by $2$ if $n$ is odd.

Now $\frac{1}{2}n(n+1)-x$ is even

Now you can put a minus sign before some numbers that have the sum $\frac{1}{2} (\frac{1}{2}n(n+1)-x)$ and you are done.

Example:

$x=23$

The smallest $n$ with $\frac{1}{2}n(n+1) \geq x$ is $n=7$

$\frac{1}{2}n(n+1)-x = 28-23 = 5$ is odd and $n$ is also odd so we have to increase $n$ by $2$.

That means $n=9$

$\frac{1}{2}(\frac{1}{2}n(n+1)-x) = \frac{1}{2}(45-23) = 11$

So we have to put a minus in front of numbers with the sum $11$. For example $2$ and $9$.

Result: 1-2+3+4+5+6+7+8-9

It comes out to be a better puzzle than it was voted to close for!

One thing is for sure, if the given number $x$ is a triangular number, the answer is its position in the sequence 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66
which is given by

$$\left\lfloor\dfrac{\sqrt{1+8x}-1}{2}\right\rfloor$$

Also:

here is my code, which gives a very interesting pattern,

output:  For x=1, ans : 1 For x=2, ans : 3 For x=3, ans : 2 For x=4, ans : 3 For x=5, ans : 5 For x=6, ans : 3 For x=7, ans : 5 For x=8, ans : 4 For x=9, ans : 5 For x=10, ans : 4 For x=11, ans : 5 For x=12, ans : 7 For x=13, ans : 5 For x=14, ans : 7 For x=15, ans : 5 For x=16, ans : 7 For x=17, ans : 6 For x=18, ans : 7 For x=19, ans : 6 For x=20, ans : 7 For x=21, ans : 6 For x=22, ans : 7 For x=23, ans : 9 For x=24, ans : 7 For x=25, ans : 9 For x=26, ans : 7 
which is :
$1,3,2,3,5,3,5,4,5,4,5,7,5,7,5,7,6,7,6,7,6,7,9,7,9,7,9$,... OEIS/A140358
check the values up to $1000$ here. see this final code

#include<bits/stdc++.h>
using namespace std;

int i,n,t;
int main()
{   int x,ans;

for(cin>>t;t;t--)
{   cin>>x;
n=floor((sqrt(1+8*x)-1)/2);
//cout<<n<<endl;
i=(n*(n+1))/2;
//cout<<x<<", sum:"<<i<<", N:"<<n<<endl;
if(n%2) //n is odd
{
if((x-i)%2) ans=n+2;
else ans=n+1;
}
else
{
if((x-i)%2) ans=n+1;
else ans=n+3;
}
cout<<">! For x="<<x<<", ans : "<<ans<<endl;
}
}