5
$\begingroup$

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

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

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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;
    }
}
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.