Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

At the beginning the blackboard contains a single integer $N$. If the blackboard contains some number $x$, then we may additionally write the two numbers $\displaystyle\frac x {x+2} $ and $ 2x + 1 $ on the blackboard. After some time you look at the blackboard and see the number 2016 written on it.

What are the possible starting values $x$ for this story to happen?

share|improve this question
up vote 12 down vote accepted

Obviously we're never going to get an irrational number. So any number we get can be expressed as $\frac{p}{q}$, where $p$ and $q$ are relatively prime integers ($q$ can be $1$, if the number is an integer). When we have $\frac{p}{q}$, we can write $\frac{2p+q}{q}$ and $\frac{p}{p+2q}$.

If $p$ and $q$ are both odd, $2p+q$ and $p+2q$ are also odd, so any fraction we get from there will have an odd numerator and denominator. Since we want $\frac{2016}{1}$, which has an even numerator, a fraction with $p$ and $q$ odd is useless.

If $p$ is odd and $q$ is even, then $2p+q$ is even and $p+2q$ is odd. The fraction $\frac{p}{p+2q}$ will have an odd numerator and denominator, so it is useless. Similarly, if $p$ is even and $q$ is odd, $\frac{2p+q}{q}$ is useless.

Note that we never get more than one useful fraction at a time. If $p$ is odd and $q$ even, we get $\frac{2p+q}{q}$, while if $q$ is odd and $p$ even, we get $\frac{p}{p+2q}$.

Consider the case with $p$ odd and $q=2k$ (the other case is symmetrical). Then $\frac{2p+q}{q}=\frac{2p+2k}{2k}=\frac{p+k}{k}$ (which can't be reduced further because $p$ and $k=\frac{q}{2}$ are relatively prime). Note that the sum of the numerator and denominator is $p+k+k=p+q$, so it didn't change. Useful moves don't change the sum of the numerator and denominator. We need to get $\frac{2016}{1}$, so the sum of the numerator and the denominator is $2017$. The only integer possibilities for $N$ are $\frac{2016}{1}=2016$ and $\frac{2018}{-1}=-2018$.

$2016$ obviously works. Running it with a computer shows that $-2018$ also works after 168 steps.

share|improve this answer

Obviously we have $x=2016$.

Let $x=2$, then we can write $\dfrac24$.

With $x=4$ we can write $\dfrac46$, etc...

So any even number $\lt2016$.

share|improve this answer
    
How will having 1/2 and 2/3 help you get to 2016? – Deusovi Feb 27 at 17:27
1  
It says to write the number, not the two numbers $x$ and $x+2$. Numbers do not change when you represent them differently. – Deusovi Feb 27 at 17:32
1  
that's not how i interpret the Q. anyway, we could have N=43284201624928, which sort of blows the answer to kingdom come – Jon Mark Perry Feb 27 at 17:35
1  
I feel like this is the best answer. If 2/4 is written in the board, then the blackboard contains the integers 2 and 4. – Will Sherwood Feb 27 at 21:28
1  
Agreed with @WillSherwood and Jon Mark Perry - the question only says "...you look at the blackboard and see the number 2016 written on it.", not that 2016 is result of a computation. – question_asker Mar 3 at 15:57

I tried tackling the problem numerically. I found that up to 13 layers of depth(the furthest I could go), there was no solution. First I inverted

$ f(x) = 2x+1 -> f^{-1}(x) = \frac{x-1}{2}$

$ g(x) = \frac{x}{x+2} -> g^{-1}(x) = \frac{2x}{1-x}$

Next, I want to consider all possible inversions of 2016 at a depth n. The question we are trying to answer:

is

$ h_1 ( h_2 ( h_3 ( h_4 ( h_5 ... h_n (2016 ))))))) \in \Z $

Where $h_i$ is either $f^{-1}(x)$ or $g^{-1}(x)$.

What I did was considered all possible permutations of $f^{-1}$ and $g^{-1}$, and I find that up to n=13 there is no solution. That is, there is no integer which application of f(x) and g(x) reaches the value 2016.

for instance

$f^{-1}(2016) = 1007.5$

$g^{-1}(2016) = -2.00099$

$f^{-1}(f^{-1}(2016))=503.25$

$g^{-1}(f^{-1}(2016))=-2.00199$

$f^{-1}(g^{-1}(2016))=-1.5005$

$g^{-1}(g^{-1}(2016))=-1.33355$

code:

#include <stdio.h>


double finverse(double x)
{
return (x-1)/2;
}

double ginverse(double x)
{

return 2 * x/(1-x);
}

void printBits(size_t const size, void const * const ptr)
{
unsigned char *b = (unsigned char*) ptr;
unsigned char byte;
int i, j;

for (i=size-1;i>=0;i--)
{
    for (j=7;j>=0;j--)
    {
        byte = b[i] & (1<<j);
        byte >>= j;
        printf("%u", byte);
    }
}
puts("");
}

int main(int argc, char **argv)
{
int num = 1;
int index;
double *previous = malloc(sizeof(double));
*previous = 2016;
double *current;
for(num=1;num<10;num++)
{
    printf("Depth is %d\n",num);

current = malloc((int)pow(2,num)*sizeof(int));
for(index=0;index<pow(2,num);index++)
{
    //printf("Index is %d\n",index);
    if(index %2 == 0)
    *(current + index) = finverse(*(previous+index/2));
    else
    *(current + index) = ginverse(*(previous+index/2));

    printf("Value is %g\n",*(current+index));
    if(*(current+index) == (int)(*(current+index)))
    {
        printf("\n\n\n\SOLUTION HAS BEEN FOUND\n\n\n");
        printf("%g ",*(current+index));
        printBits(sizeof(int),&index);
        printf("\n");
    }

}
previous = current;
}
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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