TOAD 25 - Rational Creatures

Posted on 2013-04-25 In CS/Math , TOAD Disqus: Word count in article: 476 Reading time ≈ 2 mins.

好久没更了。

Problem

给定一个 0/1 序列 $S$ ，执行 $S \leftarrow S + inv(S)$ 无数次后，证明小数 $0.S$ 一定是无理数。 $inv(S)$ 表示将 $S$ 中的每个 0 变 1 1 变 0 ，例如 $inv(0111) = 1000$ 。

Solution

证明一个数是无理数就是要证明这个数不能表示出 $\frac{q}{p}$ 的形式，或者证明一个无限小数不含有循环节。这里我们证明这个小数不存在循环节。

假设一开始的字符串为 $S^0$ ，$r$ 次操作后的字符串为 $S^r$ 。设 $S^{\infty} = u v v v \dots$ 。令 $\vert v\vert = 2^a b$ ，其中 $b$ 为奇数。我们要证明 $a > 0$ 。注意到对于任意一个字符串 $x$ ， $x^r \quad (r > 0)$ 中 0 和 1 的个数总是相等的。如果 $a = 0$ ，则表示 $v$ 的长度为奇数，1 的个数一定和 0 的个数不相等。易知一定存在一个足够大 $t$ 使得 $x^t$ 中 $v$ 出现的次数足够多，使得 0 和 1 的个数不同，与前述矛盾。所以 $a > 0$ 。

如果 $u$ 为奇数，则我们可以令 $S \leftarrow S^1$ ，总是可以找到一个长度为偶数的 $u$ 。既然 $u$ 和 $v$ 都是偶数，我们不妨把 $S^\infty$ 的所有偶数项全部去掉，则可以得到一个新的序列，这个序列仍然存在循环节，且循环节的长度是 $\frac{\vert v\vert }{2}$ 。注意到循环节的长度只有原来的一半。我们只要照这样不停的做下去，如果 $v$ 存在，则一定有一个时刻 $v$ 为奇数，此时与前面证明的冲突。Q.E.D.

nonsense

稍后放出 TX 的旅游记录。