3
$\begingroup$

Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?

Example: 335 can be deduced from 2000 using division by 2, addition of 5 and division by 3: $((2000/2)+5)/3) = 335$.

I need to prove that 1889 can't be derived from 2019 using the following 3 operations:

  1. $n+7$ ;
  2. $n*2$;
  3. $n/3$ (if divisible).

All I come up with is some sort of breadth-first search.

$\endgroup$
  • $\begingroup$ Have you tried using the residues properties? 1889 = 2019 (mod 3), this is a big hint, since you can only deduce here if the residues are still identical (both numbers divisible by 3). An indirect proof should do the job, no need for algorithmic brute force $\endgroup$ – Panzerkroete Jun 5 at 21:50
  • $\begingroup$ @Panzerkroete, if modulo 3 works for you, can you write an answer? $\endgroup$ – Apass.Jack Jun 6 at 8:11
3
$\begingroup$

If you have implemented breadth first search correctly, you should have found that 1889 can be reached.

$\quad 2019+7\to 2026$
$\quad 2026+7\to 2033$
$\quad\quad\cdots\quad$ (add 7 repeatedly)
$\quad 4238+7\to 4245$
$\quad 4245 \div 3 \to 1415$
$\quad 1415 * 2 \to 2830$
$\quad 2830 * 2 \to 5660$
$\quad 5660 + 7 \to 5667$
$\quad 5667 \div 3 \to 1889$

It is possible that you had been asked to show that 1883 can't be derived from 2019.

A number can be derived from 2019 iff it is a positive integer not divisible by 7

Proof:
"$\Longrightarrow$": If $n$ is not divisible by 7, neither is any of $n+7$, $n*2$ and $n/3$ (when $n$ is divisible by 3). If we start with a number that is not divisible by 7, it will remain not divisible by 7 regardless of how many operations we have applied on it. Since 2019 is not divisible by 7, we cannot derive any number that is divisible by 7.

"$\Longleftarrow$":

In fact, we can derive all positive numbers not divisible by 7 without the operation $n\to n * 2$. For all $k\ge0$,

  • $\dfrac{2019 + 7 * (((7k+1)*3^{6k+7}-2019)/7)}{3^{6k+7}}=7k+1$
  • $\dfrac{2019 + 7 * (((7k+2)*3^{6k+11}-2019)/7)}{3^{6k+11}}=7k+2$
  • $\dfrac{2019 + 7 * (((7k+3)*3^{6k+6}-2019)/7)}{3^{6k+6}}=7k+3$
  • $\dfrac{2019 + 7 * (((7k+4)*3^{6k+9}-2019)/7)}{3^{6k+9}}=7k+4$
  • $\dfrac{2019 + 7 * (((7k+5)*3^{6k+8}-2019)/7)}{3^{6k+8}}=7k+5$
  • $\dfrac{2019 + 7 * (((7k+6)*3^{6k+10}-2019)/7)}{3^{6k+10}}=7k+6$

Exercises

Exercise 1. Assume the same three operations. Let $n$ be a positive number not divisible by 7. Then a number can be derived from $n$ iff it is a positive integer not divisible by 7.

Exercise 2. Assume the same three operations. Let $n$ be a positive number divisible by 7. Then a number can be derived from $n$ iff it is divisible by 7.

Exercise 3. If positive integer $m$ can be derived from positive integer $n$ using the three operations, then $m$ can be derived from $n$ using the first and last operations, namely, $n\to n+7$ and $n\to n/3$ (if divisible).

$\endgroup$
  • $\begingroup$ I think you meant "remainder" instead of reminder. Did you may also mean remainders of numbers divided by 3 instead of 7? $\endgroup$ – Panzerkroete Jun 5 at 22:15
  • $\begingroup$ I mean 7. Does 3 work for you? $\endgroup$ – Apass.Jack Jun 6 at 4:07
  • $\begingroup$ Probably I need to clarify the question. All this operations should be done on number derived from initial number. 2019 - 1 level. 2019+7=2026, 2019*2=4038, 2019/3=673 - 2 level. Then we break 2026 from 2 level again 2026+7=2033, 2026*2=4052, 2026/3=with remainder (we don't need it anymore). And so for every integer that we meet executing this 3 operations.Next will be 4038 ... $\endgroup$ – cs_student Jun 6 at 6:52
  • $\begingroup$ $2019+7=2026$. Then $2026+7=2033$. Then $2033+7=2040$. Then $2040+7=2047$. Then $2047+7=2054$. Then $\cdots$ (many steps of adding 7). Then $4238+7=4245$. $\endgroup$ – Apass.Jack Jun 6 at 8:07
  • $\begingroup$ @cs_student You mean, that we have a additional rule? Here, we have to (1.): add 7; then (2.) multiply with 2 and last (3.) divide by 3 if possible, otherwise start from step 1 again? Then this problem is way more easier. I asked my algorithmics professor and he immediately conjected that this problem would be $NP-complete$ or even $EXPTIME$-hard if we can arbitrarely shuffle the composition of functions since they dont form a composition ring. . $\endgroup$ – Panzerkroete Jun 7 at 9:41
0
$\begingroup$

Define $f(x) = x/3, g(x) = 2x, h(x) = x+7$ and $D = \mathbb{N}$ for the functions $f,g,h$. I presume that the question is the following:
Given $x,y \in \mathbb{N}$ is there a transformation sequence $s_{(n)}:= (f \circ g \circ h) ^{n}$ such that $(f \circ g \circ h) ^{n}(x) = y)$ with the restriction that always $3 | (g\circ h)(f \circ g \circ h) ^{n-1}(x)$ ?

Now write $s_{(n)}$ as a direct expression depending only on $x,n$. Lets call this $c(x,n)$. Here $c(x,n) = \frac{2^nx+14(2^n-1)}{3^n}$ For simplicity we write also $c(x,n):=\frac{num(x,n)}{3^n}$

Given $x,y$, then $y$ can be derived from $x$ iff $c(x,n)=y$ has a has at least one natural solution for $n$ and $3^i | num(x,i)$ for all $i \leq n, i \in \mathbb{N}$.

Applied this result to the conrete numbers, we see that the positive $n \approx 0.166$ and hence 1889 can not be derived from 2019.

If there are no restrictions on the composition of the function, this problem is (according to my professor) at least $NP$-complete. A formal proof would be nice, until now I didnt find a suitable Problem for a sharp reduction.

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