Từ 1 điểm $\left ( 1,1 \right )$ di chuyển một hòn sỏi trên mặt phẳng thỏa mãn các điều kiện sau
a) Từ điểm $\left ( a,b \right )$ có thể di chuyển đến điểm $\left ( 2a,b \right )$ hoặc $\left ( a,2b \right )$.
b) Từ điểm $\left ( a,b \right )$ có thể di chuyển đến $\left ( a-b,b \right )$ nếu $a>b$ hoặc $\left ( a,b-a \right )$ nếu $b>a$
Hỏi với $x,y$ nguyên dương như thế nào thì hòn sỏi có thể đến $\left ( x,y \right )$
(Bài này mình ra $x,y$ thoả mãn $\left ( x,y \right )=2^s$ )
Sửa lại tiêu đề em nhé, vi phạm nội quy diễn đàn rồi đấy !
Xét các trường hợp xảy ra với ô $(x;y)$ :
$\bullet$ Nếu $gcd(x;y)\vdots p$ với $p$ là 1 số nguyên tố lẻ bất kì. Muốn hòn sỏi di chuyển đến $(x;y)$ thì trc đó nó phải ở vị trí $(x+y;y)$ hoặc $(x;x+y),\left(\frac{x}{2};y\right);\left(x;\frac{y}{2}\right)$.
Lúc đó do $gcd(x;y)=gcd(x+y;y)=gcd(x;x+y)\vdots p\,\, , \,\, gcd\left(\frac{x}{2};y\right);gcd\left(x;\frac{y}{2}\right)\vdots p$ (do $p$ lẻ) nên trước khi đến ô $(x;y)$, hòn sỏi phải ở ô $(x_1;y_1)$ mà $gcd(x_1;y_1)\vdots p$. Tiếp tục làm như thế ta cũng có ô xuất phát của hòn sỏi có 2 chỉ số chia hết ch0 $p$ (Ô $(1;1)$), 1 điều vô lý !
$\bullet$ Nếu $gcd(x;y)=2^{k}$ với $k\in \mathbb{N}^{*}$, ta có thể dùng tính chất a) để dễ dàng suy ra trước khi đến ô này, hòn sỏi đã từng ở ô $(a;b)$ mà $gcd(a;b)=1$, $a,b$ đều lẻ. Ta đưa bài toán về TH 3 :
$\bullet$ Nếu $gcd(x;y)=1\,\,, \,\,x;y$ cùng lẻ, $x>y$. Lúc này $x+y\vdots 2$, đặt $v_2(a)$ là số mũ lớn nhất của 2 tr0ng khai triển số nguyên tố của $a$. Vậy thì từ ô $\left(\frac{x+y}{v_2(x+y)};y\right)$ hòn sỏi có thể di chuyển đến ô $(x+y;y)$ sau 1 số bước rồi di chuyển đến $(x;y)$.
Nhưng mặt khác $gcd\left(\frac{x+y}{v_2(x+y)};y\right)=1$ và $\frac{x+y}{v_2(x+y)}+y< x+y$ (Do $v_2(x+y)\geq 1,x<y$)
Tiếp tục quá trình này với để ý tổng 2 chỉ số của ô cần đi qua của hòn sỏi luôn giảm, cuối cùng ta nhận thấy hòn sỏi chỉ cần đi qua ô $(1;1)$.
Vậy tóm lại ô $(x;y)$ nguyên thỏa $gcd(x;y)=2^{k}$ với $k$ là 1 số tự nhiên bất kì là ô thỏa mãn đầu bài !
Bài viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 27-07-2013 - 21:32
