# Blackboard problem with 2016

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?

-

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.

-

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$.

-
How will having 1/2 and 2/3 help you get to 2016? – Deusovi Feb 27 at 17:27
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
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
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
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;
}
}

-