Cho số nguyên dương $r$ và một bảng hình chữ nhật chia thành $20$x$12$ ô vuông. Ta chỉ được di chuyển từ một ô vuông đến ô vuông khác khi khoảng cách giữa hai tâm của hai ô đó bằng $\sqrt{r}$.
Xét bài toán tìm một dãy các nước đi để chuyển từ ô này sang ô khác mà 2 ô đó nằm ở 2 góc kề nhau của bảng, 2 góc đó nằm trên cùng 1 chiều dài hình chữ nhật.
a) CMR bài toán không giải được nếu $r$ chia hết cho $2$ hoặc $3$.
b)CMR bài toán giải được không khi $r=73$? Khi $r=79$?
Đề bài của buiminhhieu
Nếu từ ô này di chuyển sang ô khác tức là từ tâm ô này di chuyển sang tâm ô khác
a,Ta chọn 4 ô ở 4 góc, thứ tự gọi là A,B,C,D
Nối các tâm AB,BC,CD,DA ta được 1 hình chữ nhật 19x11 ta giả sử AB=19,AD=11,AB là cạnh bên dưới
Ta cần đi từ A sang B
Với điểm M bất kì là tâm 1 hình vuông ban đầu, kẻ MH,MK vuông góc với AB,AD
Gọi $AH=x_{M},AK=y_{M}$ suy ra $x_{M}$,$y_{M}$ số tự nhiên
Sau 1 lần di chuyẻn A đi đến E
Suy ra $x_{E}^{2}+y_{E}^{2}=r$ (Pitago)
Nếu r chia hết cho 2 suy ra $x_{E}$,$y_{E}$ cùng tính chẵn lẻ
Như vậy nếu từ E đi đến F thì $x_{F}$,$y_{F}$ cùng tính chẵn lẻ
Mà $x_{B}$=19,$y_{B}$=0 không cùng tính chẵn lẻ nên không thể từ A đi về B
=> r không chia hết cho 2
Nếu r chia hết cho 3 thì do số chính phương chỉ có thể chia 3 dư 0 hoặc 1 nên $x_{E}$, $y_{E}$ chia hết cho 3
Từ E đi đến F thì $x_{F}$,$y_{F}$ cũng chia hết cho 3
Mà $x_{B}$=19 không chia hết cho 3 nên từ A không thể đi đến B
=> r không chia hết cho 3
b, r=73 thì không thể do 73=$3^{2}+8^{2}$
Mà do (8;3)=1 và $x_{M}$ <12,$y_{M}$ <20
nên đoạn thẳng AB chỉ có thể chứa 3 điểm trong dãy các điểm đi
Đó là 3 điểm A(0;0), P(6;0) và Q(16;0) không thể có điểm B
Vì vậy với r=73 thì từ A không thể sang B
r=79 thì $x_{E}^{2}+y_{E}^{2}=79$ với $x_{E}$, $y_{E}$ là số tự nhiên
Mà 79 không thể phân tích thành bất kì tổng 2 số chính phương nào
nên khoảng cách giữa 2 tâm 2 ô bất kì không thể bằng $\sqrt{r}=\sqrt{79}$
vậy không giải được với r=79