UyHiP-2013-Apr

也算得上是与时俱进更新了一回，上个月的 UyHiP 居然被我想出来了真是让人开心～

Problem

对于一个函数 \(f\) ，我们说 \(f\) 是 \(k\) 性质的，当且仅当存在一对正整数 \((a, d)\) 满足 \(f(a) < f(a + d) < f(a + 2d) < \cdots < f(a + kd)\) 。

现在请找出所有的正整数 \(k\) ，使得所有的 \(N^+ \to N^+\) 的双射函数 \(f\) 均是 \(k\) 性质的。

Solution

\(k\) 只能为 1 或 2 。

显然 \(k\) 具有单调性，我们只要证明 \(k = 2\) 时可行，且 \(k = 3\) 时不可行即可。

对于任意一个 \(N^+ \to N^+\) 的函数 \(f\) ，我们总可以找到一个 \(x\) 使得 \(f(x) = 1\) 。考虑序列 \(f(x + 1), f(x + 2), \dots, f(x + 2^t), \dots\) 。由于值是有限的，所以这个序列不能无限递减下去，所以必定存在一个 \(r\) 使得 \(f(x + 2^r) < f(x+2^{r+1})\) 。由于 \(f(x)\) 是 \(f\) 的最小值，所以我们有 \(f(x) < f(x + 2^r) < f(x + 2 \times 2^r)\) 。也就是 \(k = 2\) 总是可行的。

考虑一个序列 \(3, 2, 1, 9, 8, \dots, 4, 27, \dots 10, 81, \dots 28, \dots\) 。我们将证明对于这个函数不存在 \(k = 3\) 时的 \((a, d)\) 。对于任意一个 \(f(a) < f(a + d) < f(a + 2d)\) ，我们总可以找到一个 \(t\) ，使得 \(a + d \leq 3^t < a + 2d\) （否则就不会有 \(f(a + d) < f(a + 2d)\) ）。易知 \(3^t < a + 2d < a + 3d = 3(a + d) - 2d \leq 3^{t + 1} - 2d < 3^{t + 1}\) ，于是必有 \(f(a + 2d) > f(a + 3d)\) 。

nonsense

上次手贱鼓捣 Jekyll 时没有备份，导致丢失了一堆的 markdown 源文件 →_→

幸亏还留着 html 备份。

看 html 很好的一点就是公式全部给我备份了的，在 img 的 alt 属性里面。

于是怒写一个 Elisp 代码批量替换，少部分就自己手玩微调。

(defun to-md ()
  (interactive)
  (replace-regexp "' class='maruku-png' src='/images/latex/.*?.png' style='' />

" "") (beginning-of-buffer) (replace-regexp "

" "## ") (beginning-of-buffer) (replace-regexp "

" "# ") (beginning-of-buffer) (replace-regexp "

" "") (beginning-of-buffer) (replace-regexp "

" "") (beginning-of-buffer) (replace-regexp "

" "") (beginning-of-buffer) (replace-regexp "

" "") (beginning-of-buffer) (replace-regexp " <img alt='" "") (beginning-of-buffer) (replace-regexp "&" "&") (beginning-of-buffer) (replace-string "" "") (beginning-of-buffer) (replace-string "<" "<") (beginning-of-buffer) (replace-string ">" ">") (beginning-of-buffer) (replace-regexp "'" "'") (beginning-of-buffer))

不能再手贱了 →_→