Hailstone-2.9

$$f(x)=\left\{\begin{array}{lr}x+1,& \text{if }x\equiv 1(mod2)\\ \frac{x}{2},& \text{if }x\equiv 0(mod2)\end{array}\right\}$$

명제 $p$ : 모든 자연수에 대해 함수를 $m$번 반복해서 $1$에 도달하게 할 수 있다.

증명을 해보자.

 

$sol.1$

모든 자연수가 자기 자신보다 작아질 수 있다는 것을 증명하자.

2가 자기 자신보다 작아지면 1이 되면서 부합하고, 3이 자기 자신보다 작아지면 2를 경유하여 1에 도달하게 된다.

$x>\frac{x+1}{2}\iff x>1$

$x>\frac{x}{2}$

따라서 x=1인 경우만 해보면 된다.

$sol.2$

$x=1$일 때만 해봐도 되는 것을 보이자.

Hailstone-3의 글에 있는 Theorem 3를 참고하면 된다.