近在咫尺

aimisiyou

有两个自然数a,b,两数都可进行如下循环操作a=2*a+xi，b=2*b+yi,每次操作xi,yi可任意取{-1,0,1}其中之一。
问题：1、经过有限次操作，两数能相邻的充要条件是什么？
         2、若a=11,b=17,能否经过有限次操作使得最终两数相邻？
         

aimisiyou

例如 a=3, b=10
则有a=2*3+0=6，a=2*6-1=11  即 a 操作2次，b操作0次，达到两数相邻。

lsr314

假设$a<b$,必要条件是存在整数$t$，满足$(b-1)/(a+1)<2^t<(b+1)/(a-1)$,由于$a=11,b=17$不满足这个条件，所以不可能。

aimisiyou

lsr314 发表于 2020-9-4 20:05
假设$a

这个结论是如何得出来的呢？

hujunhua

最开始，A={a}, B={b}
集合迭代扩张，S=Flatten@{2S-1, 2S, 2S+1}
从 S={s} 开始，看看扩张 n 次的结果
第1次扩张得到：S={2s-1, 2s, 2s+1}
第2次扩张得到：S={4s-3, 4s-2, 4s-1, 4s, 4s+1, 4s+2, 4s+3}
第3次扩张得到：S={8s-7, 8s-6, …，8s, …, 8s+6, 8s+7}
……
第k次扩张得到：`S=\{2^k s-2^k+1, …, 2^k s, …，2^k s+2^k-1\}`
要使a, b经过迭代能够相邻，
即要    First@B-1≤Last@A   且First@A-1≤Last@B
假定这样A, B分别扩张了m, n次, 上述不等式即\[\begin{cases}
2^nb-2^n&≤2^ma+2^m-1\\
2^ma-2^m&≤2^nb+2^n-1
\end{cases}\]不妨假定 a≤b，则必有  m≥n， 设 t=m-n。 解得\[
\frac{b-1}{a+1}≤2^t-\frac1{2^n(a+1)}≤2^t+\frac1{2^n(a-1)}≤\frac{b+1}{a-1}
\]这是充要条件，但不够简明，可以简化得到3#的那个必要条件。