数论小题

大佬最帅

题 14：有三个盒子，里面分别有 2、3、4 颗棋子，我们记为 (2，3，4)
现在规定一种操作：从某个盒子里拿出一些棋子放到另一个盒子，使这
个盒子里的棋子数翻倍。比如，从第二盒（3 颗棋子）里面拿出 2 颗，
放到第一个盒子里，这个盒子里原来有 2 颗棋子，现在又放入 2 颗，就
是 4 颗了，翻倍了。这次操作就是合法的。这时盒子里棋子的情况从 (2，
3，4) 变成了 (4，1，4)。现在，我们可以把第一盒的 4 颗棋子全部
放到第 3 盒，使第 3 盒里面的棋子数翻倍。这时，(4，1，4) 变成了
(0，1，8)，我们清空了一个盒子。
问题：是不是无论三个盒子里有多少颗棋子，都可以通过几次操作，清
空其中一个盒子吗？

realnumber

想不出,发个答案?

abababa

能不能这样证明，设初始时为$(x,y,z)$，不妨设$x\le y\le z$。只要$y\ge 2x$，就总能从$y$中拿出一个$x$给$x$，直到$y$第一次小于$2x$，即$x\le y<2x$，把这个状态仍记作$(x,y,z)$。这时有$x\le y<2x,y\le z$，这时能从$y$中最后拿出一个$x$给$x$，而此时$y-x<x$，于是三个数中最小的那个数变为$y-x$，比最初最小的那个数$x$减少了。这说明经过有限次操作后，总能使三个数中最小的那个数减少，因此最后就减少到零。

realnumber

回复 3# abababa


    你的思路没有把z考虑进去,应该不够的,不改变z的话,比如
x=6,y=8,z=23变为12,2,23→10,4,23→6,8,23有周期现象了.
而z参与的话,当然可以.
6,8,23→12,2,23→12,4,21→8,8,21→0,16,21

abababa

回复 4# realnumber
是的，我也发现了，这个不行。

kuing

已用 QQ 截图识别文字将 1# 的图片去除。

kuing

设初始时为 `(x,y,z)`，如果有两数相等就不用说了，现不妨设 `x<y<z`。

首先证明：如果 `x=1`，能清空 `y`。

操作方法：
将数字写成 `2` 进制，由最右边起，如果 `y` 右边第一位是 `1`，则由 `y` 给 `x`，否则就由 `z` 给 `x`。
然后第二位也是这样，如此下去即可清空 `y`。

举个栗子：初始 `(1,21,25)`，写成二进制：
$\begin{alignedat}{2}
x={}&&    1\\
y={}&&10101\\
z={}&&z&\text{（无需写出，够给就行，它最大，一定够，下同）}
\end{alignedat}$
由 `y` 给 `x` 变成：
$\begin{alignedat}{2}
x={}&&   10\\
y={}&&10100\\
z={}&&z
\end{alignedat}$
由 `z` 给 `x` 变成：
$\begin{alignedat}{2}
x={}&&  100\\
y={}&&10100\\
z={}&&z'
\end{alignedat}$
由 `y` 给 `x` 变成：
$\begin{alignedat}{2}
x={}&& 1000\\
y={}&&10000\\
z={}&&z'
\end{alignedat}$
由 `z` 给 `x` 变成：
$\begin{alignedat}{2}
x={}&&10000\\
y={}&&10000\\
z={}&&z''
\end{alignedat}$
由 `y` 给 `x` 即清空成功。

一般情况，当 `x>1` 时，对 `y`, `z` 盒子里的棋子进行捆绑，每 `x` 个一捆，余下的散装棋不用管。
对已捆绑的棋子按上述的操作方法，就能清空 `y` 里所有已捆绑的棋子，而剩下的散装棋个数小于 `x`。
也就是说，我们能将最小的数变得更小。

综上，搞定。