新生活。

看到一个很好玩的题，来源于 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 了。