0%

TOAD-puzzle-5

新生活。

看到一个很好玩的题,来源于 TOAD 。

problem

给定一个正整数三元组 \((a, b, c)\) ,每次可以选择任意两个数,不妨假设选择 \(a, b\) ,且满足 \(a \leq b\) ,则可以把这个三元组变换到 \((2a, b - a, c)\)

求证:任意一个三元组经过若干次变换后,总可以使一个数为 0 。

solution

三个数的奇偶性只有 4 种情况,分类讨论。

  1. 奇奇奇。任意变换一次后转为奇偶偶。
  2. 奇奇偶。选两个奇数变换后转为偶偶偶。
  3. 偶偶偶。可知任意变换均不会改变奇偶性,全部除二。
  4. 奇偶偶。解决这种情况即可。

我们先考虑一个奇数与一个偶数组成的二元组。可以知道,任意一个二元组的变换方式是唯一的。对于二元组 \((a, b)\) (保证 \(a\) 为偶数 \(b\) 为奇数),若另一个二元组 \((a', b')\) 变换到 \((a, b)\) ,则可以知道 \((a', b')\) 是唯一的,为 \((a + \frac{b}{2}, \frac{b}{2})\) 。即,每个二元组都可以由一个二元组变换过来,且一定可以变换到一个二元组去。这表示从一个二元组开始变换,最后一定可以回到这个二元组。显然,经过有限次变换后 \((a, b)\) 一定可以变成它的前驱,也就是 \((a + \frac{b}{2}, \frac{b}{2})\) 。在这个过程中,奇数会增加,偶数会除以二。

考虑三个数 \((a, b, c)\) ,奇偶性分别是奇偶偶。如果 \(b\)\(c\) 模 4 同时为 2 ,变换 \(b\)\(c\) 一次后两个数模 4 一定为 0 。如果不同时为 2 ,则必定有一个模 4 为 0 ,利用刚才讲到的方法可以让这个数除以二。有限次后, \(b\)\(c\) 一定都会变成 1 ,然后再做一次变换就会有个数变成 0 了。