Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Trận 10 - Toán rời rạc

mss 2014

  • Please log in to reply
Chủ đề này có 19 trả lời

#1 E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản trị
  • 3787 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Nội
  • Sở thích:Toán và thơ

Đã gửi 23-05-2014 - 19:52

Vào hồi 20h, Thứ Sáu, ngày 23/05/2014, Tổ trọng tài sẽ ra đề vào topic này, sau khi có đề, các toán thủ bắt đầu thi đấu.
 

I - Bạn cần biết:

1) Điều lệ giải đấu

2) Lịch thi đấu và tổng hợp kết qủa

 

II - Lưu ý

1) Các toán thủ khi thi đấu, cứ yên tâm rằng, sau khi trả lời là bài làm đã được lưu, BTC đã nhận được bài làm của bạn, có điều bạn không nhìn thấy được mà thôi. Bạn nên mừng vì điều này, như thế các toán thủ khác không thể copy bài của bạn được.


Bạn cũng nên sử dụng chức năng xem trước của diễn đàn để sửa các lỗi LATEX trước khi gửi bài, vì gửi rồi sẽ không xem và sửa lại được nữa.

 

 
Để sử dụng chức năng xem trước, bạn click vào Sử dụng bộ soạn thảo đầy đủ và chọn Xem trước.

 

2) Các toán thủ chớ quên rằng mỗi một mở rộng đúng sẽ được 10 điểm, các bạn nên mở rộng bài toán để thu được nhiều điểm hơn

 

3) Thành viên diễn đàn không đăng kí thi đấu vẫn có thể giải bài, nhưng phải ghi rõ là: Mình không phải là toán thủ thi đấu

 

4) Sau trận 10, sẽ có 09 toán thủ ít điểm nhất bị loại. 


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#2 E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản trị
  • 3787 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Nội
  • Sở thích:Toán và thơ

Đã gửi 23-05-2014 - 20:02

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


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#3 Tran Nguyen Lan 1107

Tran Nguyen Lan 1107

    Trung sĩ

  • Thành viên
  • 123 Bài viết
  • Giới tính:Nam
  • Đến từ:10A1 THPT Phan Bội Châu TP Vinh Nghệ An

Đã gửi 23-05-2014 - 21:20

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



#4 canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết
  • Giới tính:Nam
  • Đến từ:A1K43 THPT chuyên Phan Bội Châu
  • Sở thích:toán

Đã gửi 23-05-2014 - 21:55

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

MSS 30 canhhoang 30011999

ta quy ước tọa độ điểm ở giữa  ô vuông ầu là (1;1)  

ta tô màu các ô vuông như hình vẽ

Gọi ($a_{1};b_{1}$) là tọa độ điểm trước khi di chuyển và $(a_{2};b_{2})$ là tọa độ điểm sau khi di chuyển thì

$(a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= r^{2}$

nếu r chia hết cho 2 thì

$(a_{1}-a_{2})^{2},(b_{1}-b_{2})^{2}$ cùng tính chẵn lẻ

$\Rightarrow a_{2}-a_{1},b_{2}-b_{1}$ cùng tính chẵn lẻ

$\Rightarrow$ sau một lần di chuyển thì vẫn dữ nguyên màu

 mà 2 ô ở 2 góc ở 2 kề nhau của bảng trên cùng chiều dài hình chữ nhật khác màu

$\Rightarrow$ không thực hiện được

nếu r chia hết cho 3 

mà $(a_{2}-a_{1})^{2}\equiv 0,1$(mod 3)

$(b_{2}-b_{1})^{2}\equiv 0,1$(mod 3)

$\Rightarrow a_{2}-a_{1}\vdots 3$

$\Rightarrow$ sau một lần di chuyển thì số dư của hoành độ khi chia cho 3 được dữ nguyên

mà 20 chia 3 dư 2,1 chia 3 dư 1

$\Rightarrow$ điều phải chứng minh

b Nếu $r= 79$\

$\Rightarrow (a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= 79$

mà 79 chia 4 dư 3

mà 1 số chính phương chia 4 dư 1 hoặc 0

$\Rightarrow$ không thể thực hiện được

với r=73 thì $(a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= 73= 8^{2}+3^{2}$

$\Rightarrow$ nếu bắt đầu từ ô đầu tiên ta chỉ có thể đến các ô có chấm đỏ

$\Rightarrow$ không thể thực hiện được

File gửi kèm



#5 Super Fields

Super Fields

    Thiếu úy

  • Thành viên
  • 526 Bài viết
  • Giới tính:Không khai báo

Đã gửi 24-05-2014 - 00:02

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

 

Bài dự thi trận $10$ của $MSS 27$:

 

$a>$

 

$\star$ Xét trường hợp cụ thể: $r=10$

 

Ta thấy $10=3^2+1^2$. Gọi hình chữ nhật đó nằm trên trục tọa độ $xAy$ với $A$ là gốc.

 

Điểm ở trên $A$ là $B$, điểm ở bên phải $A$ là $D$, điểm còn lại là $C$

 

Vì khoảng cách giữa hai tâm có và chỉ có thể là $\sqrt{10}$ nên có thể đi từ $A(0;0)$ đến $M(3;1)$

 

$\triangleright$ Gọi $a;b;c;d$ lần lượt là những lần mình đi theo kiểu $(3;1);(3;-1);(-3;1);(-3;-1)$

 

$\triangleright$ Gọi $a';b';c';d'$ lần lượt là những lần mình đi theo kiểu $(1;3);(1;-3);(-1;3);(-1;-3)$

 

Hiển nhiên có số lần đi là tự nhiên nên $a;b;c;d;a';b';c';d' \in N^*$

 

Đến đây, ta có hệ phương trình:

 

$\left\{\begin{matrix} 3a + 3b - 3c - 3d + a' + b' - c' - d' = 11\\ a + b - c - d + 3a' + 3b' - 3c' - 3d' = 0 \end{matrix}\right.\Leftrightarrow 8a'+8b'-8c'-8d'=11$

 

$\Rightarrow a'+b'-c'-d'=\frac{11}{8}$ Vô lí vì $a';b';c';d'$ tự nhiên.

 

Vậy hệ vô nghiệm hay không có cách đi nào với $r=10$ thỏa mãn bài toán được xét.

 

$\star$ Xét đến tổng quát:

 

$1.$ Nếu $r$ chẵn thì hoặc hai số tạo ra nó cùng chẵn hoặc cùng lẻ.

 

$1.1$ Nếu hai số tạo ra nó cùng chẵn thì ta làm giống hệt hướng giải với $r=10$ xin được không chứng minh lại

 

$1.2$ Nếu hai số tạo ra nó cùng lẻ thì ta lại xét trường hợp $B(11;0)$

 

Ta có:

 

Hoành độ có thể là $a+3;a-3;a+1;a-1$, tương tự cho tung độ, do đó ta có hệ

 

$\left\{\begin{matrix} 3a+b-3c-d=11\\ 3a'+b'-3c'-d'=0\\ |a|+|b|+|c|+|d|=|a'|+|b'|+|c'|+|d'|\\ \end{matrix}\right.$

 

Giải hệ và thấy hệ vô nghiệm với mọi $a;b;c;d;a';b';c';d' \in N^*$

 

Vậy không có cách đi nào với $r$ chẵn hay $r$ chia hết cho $2$ thỏa mãn bài toán được xét.

 

$2$ Nếu $r$ chia hết cho $3$ , ta đi xét cấu tạo số:

 

Bằng lập luận tương tự, ta cũng nhận một hệ phương trình vô nghiệm.

 

Vậy không có cách đi nào với $r$ chia hết cho $3$ thỏa mãn bài toán được xét.

 

Kết luận: Bài toán không giải được nếu $r$ chia hết cho $2$ và $3$.

 

$b>$ Áp dụng câu $a$ ta có ngay $r=73$ thỏa mãn bài toán

 

         Nhưng $r=79$ không thỏa mãn.

 

 

 

 

 

 



#6 Super Fields

Super Fields

    Thiếu úy

  • Thành viên
  • 526 Bài viết
  • Giới tính:Không khai báo

Đã gửi 24-05-2014 - 00:22

Em xin được bổ sung thêm:

 

$b>$ Vì $79$ không thể viết được dưới dạng $a^2+b^2$ nên không thỏa bài toán


$\dagger$God made the integers, and else is the work of man.$\dagger$


$\boxed{\textrm{My Blog}}$


#7 phuocdinh1999

phuocdinh1999

    Thượng sĩ

  • Thành viên
  • 265 Bài viết
  • Giới tính:Nam
  • Đến từ:Quảng Nam

Đã gửi 25-05-2014 - 08:40

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

$\boxed{SBD:MSS48}$

                                      3015969655_353962148_574_574.jpg

Thay vì di chuyển đường chéo từ ô này sang ô khác có khoảng cách giữa $2$ tâm là $\sqrt{r}$, ta có thể di chuyển ngang $a$ bước rồi dọc $b$ bước sao cho $a^2+b^2=r$ (như hình trên)

 

Kí hiệu bảng HCN: từ trái sang phải đánh số $1,2,...,20$; từ trên xuống dưới đánh số $1,2,...,12$ (ví dụ như hình trên)

Kí hiệu ô $(x,y)$ là ô ở hàng $y$ cột $x$ $(1\leq x\leq 20;1\leq y\leq 12)$

Giả sử ban đầu ta đứng ở ô $(1,1)$, cần tìm cách đi để đến ô $(20,1)$

 

a)+Xét TH $r\vdots 2$:

Khi đó $a^2+b^2=r\vdots 2\Rightarrow (a+b)^2=r+2ab\vdots 2\Rightarrow a+b\vdots 2$

Mỗi lần đi 1 nước tức là di chuyển từ ô $A(m,n)$ ---> $B(m\pm a;n\pm b)$

Do $a+b\vdots 2\Rightarrow a-b\vdots 2\Rightarrow x_B+y_B-(x_A+y_A)=\pm a\pm b\vdots 2$

 

Như vậy nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod2)$

 

Ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến ô $(20,1)$ vì $1+1\vdots 2$ và $20+1\equiv 1(mod2)$ (đpcm)

 

+Xét TH $r\vdots 3$

Ta có: $a^2+b^2=r\vdots 3$

Vì $a^2,b^2$ chia $3$ chỉ có thể dư $0,1$ nên suy ra $a\vdots 3;b\vdots 3\Rightarrow a+b\vdots 3$

Lập luận tương tự TH trên, ta được:

 

Nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod3)$

 

Mà ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến $(20,1)$ vì $1+1\not\equiv 20+1(mod3)$ (đocm)

 

b)+Xét TH $r=79$:

Ta có $a^2+b^2=79$

Do $a^2,b^2$ chia $4$ có thể dư $0,1$ nên $a^2+b^2$ chia $4$ chỉ có thể dư $0,1,2$

Mà $79$ chi $4$ dư $3$ nên không tồn tại $a,b$ nguyên thoả mãn điều kiện, bài toán không giải được



#8 angleofdarkness

angleofdarkness

    Thượng sĩ

  • Thành viên
  • 246 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:K48 chuyên toán - THPT chuyên ĐHSP Hà Nội.

Đã gửi 25-05-2014 - 12:27



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

 

MSS54: angleofdarkness
 
Giả sử bảng cho là hình chữ nhật ABCD. Xét sự di chuyển của hai ô vuông x ở ô A và y ở ô ngay dưới A.
 
Theo đề bài: 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}$. và kêt hợp định lí Pytagore thì ta di chuyển được hai ô x và y này khi và chỉ khi $r =x^2+y^2$
 
a/
 
Nếu $r \vdots 2$ thì $x^2+y^2 \vdots 2$ tức là $x^2 \equiv y^2 (mod 2)$. Điều đó có nghĩa là mỗi bước di chuyển là giữa hai ô vuông là hai số lẻ hoặc hai số chẵn. 
 
Giả sử bảng đã cho như một bàn cờ (tô màu trắng hoặc đen cho mỗi ô) Như vậy thì ta chỉ có thể di chuyển giữa hai ô cùng màu đen (hoặc trắng).
 
 
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 thì có màu khác nhau  nên không thể di chuyển hai ô này được.
 
Nếu $r \vdots 3$ thì $x^2+y^2 \vdots 3$ Tức là có cả 2 số x; y chia hết cho 3. Như vậy ta chỉ cho phép di chuyển giữa các ô là bội số của 3.
 
Coi bảng như một hệ trục tọa độ với A(0; 0) và cần xét di chuyển với điểm B(19; 0). Nhưng hai ô này có B(19; 0) có 19 không là bội của 3 nên không thể di chuyển A với B.
 
Suy ra  bài toán không thể giải được khi $r \vdots 2$ hoặc $r \vdots 3$.
 
b/
 
Nếu $r=73$ thì có $x^2+y^2=73=8^2+3^2$ nên $x=8;y=3$ hoặc ngược lại. Vậy ta có thể di chuyển từ một góc của một hình chữ nhật $9 \times 4$ vào góc đối diện của nó. 
 
Xét các bước đi có được như sau: $(0,0) \rightarrow  (8,3) \rightarrow (16,6) \rightarrow (8,9) \rightarrow (11,1) \rightarrow (19,4) \rightarrow (11,7) \rightarrow (19,10) \rightarrow (16,2) \rightarrow (8,5) \rightarrow (16,8) \rightarrow (19,0)$
 
Nếu $r=79$ là số nguyên tố, mà $r =x^2+y^2$ nên bài toán không giải được.


#9 angleofdarkness

angleofdarkness

    Thượng sĩ

  • Thành viên
  • 246 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:K48 chuyên toán - THPT chuyên ĐHSP Hà Nội.

Đã gửi 25-05-2014 - 19:52

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

 

Bài làm của MSS54:

 

Mở rộng:

 

Giả sử xét sự di chuyển hai ô x và y (x; y nguyên ) với điều kiện ta di chuyển được hai ô này khi $r=x^2+y^2$

 

Như vậy thì bài toán giải được khi r là tổng của hai số chính phương, kèm theo điều kiện r không chia hết cho 2 và 3 (đã c/m ở câu a)



#10 phuocdinh1999

phuocdinh1999

    Thượng sĩ

  • Thành viên
  • 265 Bài viết
  • Giới tính:Nam
  • Đến từ:Quảng Nam

Đã gửi 25-05-2014 - 20:08

$\boxed{SBD:MSS48}$

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

                                      3015969655_353962148_574_574.jpg

Thay vì di chuyển đường chéo từ ô này sang ô khác có khoảng cách giữa $2$ tâm là $\sqrt{r}$, ta có thể di chuyển ngang $a$ bước rồi dọc $b$ bước sao cho $a^2+b^2=r$ (như hình trên)

 

Kí hiệu bảng HCN: từ trái sang phải đánh số $1,2,...,20$; từ trên xuống dưới đánh số $1,2,...,12$ (ví dụ như hình trên)

Kí hiệu ô $(x,y)$ là ô ở hàng $y$ cột $x$ $(1\leq x\leq 20;1\leq y\leq 12)$

Giả sử ban đầu ta đứng ở ô $(1,1)$, cần tìm cách đi để đến ô $(20,1)$

 

a)+Xét TH $r\vdots 2$:

Khi đó $a^2+b^2=r\vdots 2\Rightarrow (a+b)^2=r+2ab\vdots 2\Rightarrow a+b\vdots 2$

Mỗi lần đi 1 nước tức là di chuyển từ ô $A(m,n)$ ---> $B(m\pm a;n\pm b)$

Do $a+b\vdots 2\Rightarrow a-b\vdots 2\Rightarrow x_B+y_B-(x_A+y_A)=\pm a\pm b\vdots 2$

 

Như vậy nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod2)$

 

Ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến ô $(20,1)$ vì $1+1\vdots 2$ và $20+1\equiv 1(mod2)$ (đpcm)

 

+Xét TH $r\vdots 3$

Ta có: $a^2+b^2=r\vdots 3$

Vì $a^2,b^2$ chia $3$ chỉ có thể dư $0,1$ nên suy ra $a\vdots 3;b\vdots 3$

Mỗi lần đi 1 nước tức là di chuyển từ ô $A(m,n)$ ---> $B(m\pm a;n\pm b)$
Ta có: $ x_B+y_B-(x_A+y_A)=\pm a\pm b\vdots 3$

 

Như vậy nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod3)$

 

Mà ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến $(20,1)$ vì $1+1\not\equiv 20+1(mod3)$ (đocm)

 

b)+Xét TH $r=79$:

Ta có $a^2+b^2=79$

Do $a^2,b^2$ chia $4$ có thể dư $0,1$ nên $a^2+b^2$ chia $4$ chỉ có thể dư $0,1,2$

Mà $79$ chi $4$ dư $3$ nên không tồn tại $a,b$ nguyên thoả mãn điều kiện, bài toán không giải được



#11 Nguyen Duc Thuan

Nguyen Duc Thuan

    Sĩ quan

  • Thành viên
  • 367 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT Chuyên Hùng Vương, Phú Thọ

Đã gửi 25-05-2014 - 21:38

 

Cho số nguyên dương r và một bảng hình chữ nhật chia thành 20x12 ô 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?

MSS01 - Nguyễn Đức Thuận

 

File gửi kèm  vmf.jpg   59.63K   0 Số lần tải

a) Ta tô màu các tâm ô vuông như hình vẽ. Không mất tính tổng quát, bài toán yêu cầu đi từ $A$ đến $T$.

Do $A$ và $T$ khác màu nên mỗi bước đi phải đi đến 1 ô màu khác.

Coi mỗi nước đi có dạng chữ $L$, khi đó gọi $a$ và $b$ là 2 cạnh chữ $L$

$\Rightarrow r=a^2+b^2$

+) Để đi tới một ô màu khác thì $a$ và $b$ phải khác tính chẵn lẻ.

Ví dụ: Đi từ $A$ tới $P$ thì $a=AQ=3$, $b=PQ=4$

$\Rightarrow r$ lẻ hay $r$ không chia hết cho 2 (đpcm)

Giả sử $r\vdots 3$ , do $a^2,b^2$ chia 3 dư 0 hoặc 1 mà $a^2+b^2=r \vdots 3$ nên $a, b$ đều chia hết cho 3

như vậy khoảng cách (tính theo chiều dài bảng) từ $A$ đến đích là số chia hết cho 3

ví dụ: Chữ $L$ có kích thước $3\times 6$ , ta đi từ $A$ tới $B$ rồi tới $C$ hoặc $D$ thì $AC=6$; $AD’=9$ đều chia hết cho 3

$\Rightarrow AT\vdots 3$ (vô lí vì $AT=19$)  suy ra $r$ không chia hết cho 3 (đpcm)

b) Bài toán giải được với $r$ là cạnh huyền của chữ $L$ có kích thước nguyên (tức là $r$ viết được dưới dạng tổng 2 bình phương) (Theo định lí Pythagore)

+) Xét $r=73=8^2+3^2$ => kích thước chữ $L$ là $3\times 8$ , bài toán có thể giải được.

+) Xét $r=79=a^2+b^2$ với $a$ chẵn, $b$ lẻ mà $a^2\vdots 4, b^2\equiv 1(mod4)\Rightarrow a^2+b^2\equiv 1(mod4))$

Mà 79 chia 4 dư 3 nên không tồn tại $a, b$ nguyên. Do đó bài toán không giải được.



#12 E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản trị
  • 3787 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Nội
  • Sở thích:Toán và thơ

Đã gửi 26-05-2014 - 10:11

Trận đấu đã kết thúc, mời các toán thủ nhận xét bài làm của nhau


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#13 buiminhhieu

buiminhhieu

    Thượng úy

  • Thành viên
  • 1150 Bài viết
  • Giới tính:Nam
  • Sở thích:Inequality

Đã gửi 26-05-2014 - 11:29

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

$r=73$ bài toán vẫn có thể giải được theo các bước của 

 

MSS54: angleofdarkness

Xét các bước đi có được như sau: $(0,0) \rightarrow  (8,3) \rightarrow (16,6) \rightarrow (8,9) \rightarrow (11,1) \rightarrow (19,4) \rightarrow (11,7) \rightarrow (19,10) \rightarrow (16,2) \rightarrow (8,5) \rightarrow (16,8) \rightarrow (19,0)$

 

 

MSS 30 canhhoang 30011999

ta quy ước tọa độ điểm ở giữa  ô vuông ầu là (1;1)  

ta tô màu các ô vuông như hình vẽ

Gọi ($a_{1};b_{1}$) là tọa độ điểm trước khi di chuyển và $(a_{2};b_{2})$ là tọa độ điểm sau khi di chuyển thì

$(a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= r^{2}$

nếu r chia hết cho 2 thì

$(a_{1}-a_{2})^{2},(b_{1}-b_{2})^{2}$ cùng tính chẵn lẻ

$\Rightarrow a_{2}-a_{1},b_{2}-b_{1}$ cùng tính chẵn lẻ

$\Rightarrow$ sau một lần di chuyển thì vẫn dữ nguyên màu

 mà 2 ô ở 2 góc ở 2 kề nhau của bảng trên cùng chiều dài hình chữ nhật khác màu

$\Rightarrow$ không thực hiện được

nếu r chia hết cho 3 

mà $(a_{2}-a_{1})^{2}\equiv 0,1$(mod 3)

$(b_{2}-b_{1})^{2}\equiv 0,1$(mod 3)

$\Rightarrow a_{2}-a_{1}\vdots 3$

$\Rightarrow$ sau một lần di chuyển thì số dư của hoành độ khi chia cho 3 được dữ nguyên

mà 20 chia 3 dư 2,1 chia 3 dư 1

$\Rightarrow$ điều phải chứng minh

b Nếu $r= 79$\

$\Rightarrow (a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= 79$

mà 79 chia 4 dư 3

mà 1 số chính phương chia 4 dư 1 hoặc 0

$\Rightarrow$ không thể thực hiện được

với r=73 thì $(a_{2}-a_{1})^{2}+(b_{2}-b_{1})^{2}= 73= 8^{2}+3^{2}$

$\Rightarrow$ nếu bắt đầu từ ô đầu tiên ta chỉ có thể đến các ô có chấm đỏ

$\Rightarrow$ không thể thực hiện được

$r=73 vẫn có thể thực hiện được

 

$\boxed{SBD:MSS48}$

                                      3015969655_353962148_574_574.jpg

Thay vì di chuyển đường chéo từ ô này sang ô khác có khoảng cách giữa $2$ tâm là $\sqrt{r}$, ta có thể di chuyển ngang $a$ bước rồi dọc $b$ bước sao cho $a^2+b^2=r$ (như hình trên)

 

Kí hiệu bảng HCN: từ trái sang phải đánh số $1,2,...,20$; từ trên xuống dưới đánh số $1,2,...,12$ (ví dụ như hình trên)

Kí hiệu ô $(x,y)$ là ô ở hàng $y$ cột $x$ $(1\leq x\leq 20;1\leq y\leq 12)$

Giả sử ban đầu ta đứng ở ô $(1,1)$, cần tìm cách đi để đến ô $(20,1)$

 

a)+Xét TH $r\vdots 2$:

Khi đó $a^2+b^2=r\vdots 2\Rightarrow (a+b)^2=r+2ab\vdots 2\Rightarrow a+b\vdots 2$

Mỗi lần đi 1 nước tức là di chuyển từ ô $A(m,n)$ ---> $B(m\pm a;n\pm b)$

Do $a+b\vdots 2\Rightarrow a-b\vdots 2\Rightarrow x_B+y_B-(x_A+y_A)=\pm a\pm b\vdots 2$

 

Như vậy nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod2)$

 

Ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến ô $(20,1)$ vì $1+1\vdots 2$ và $20+1\equiv 1(mod2)$ (đpcm)

 

+Xét TH $r\vdots 3$

Ta có: $a^2+b^2=r\vdots 3$

Vì $a^2,b^2$ chia $3$ chỉ có thể dư $0,1$ nên suy ra $a\vdots 3;b\vdots 3\Rightarrow a+b\vdots 3$

Lập luận tương tự TH trên, ta được:

 

Nếu ban đầu ta đứng ở ô $N(x_N;y_N)$ và sau một số nước đi, ta đứng ở ô $M(x_M;y_M)$

thì $(x_M+y_M)$$\equiv (x_N+y_N)(mod3)$

 

Mà ban đầu ta đứng ở ô $(1,1)$ nên không thể đi đến $(20,1)$ vì $1+1\not\equiv 20+1(mod3)$ (đocm)

 

b)+Xét TH $r=79$:

Ta có $a^2+b^2=79$

Do $a^2,b^2$ chia $4$ có thể dư $0,1$ nên $a^2+b^2$ chia $4$ chỉ có thể dư $0,1,2$

Mà $79$ chi $4$ dư $3$ nên không tồn tại $a,b$ nguyên thoả mãn điều kiện, bài toán không giải được

Thiếu $r=73$


%%- Chuyên Vĩnh Phúc

6cool_what.gif


#14 buiminhhieu

buiminhhieu

    Thượng úy

  • Thành viên
  • 1150 Bài viết
  • Giới tính:Nam
  • Sở thích:Inequality

Đã gửi 26-05-2014 - 11:38

 

Bài dự thi trận $10$ của $MSS 27$:

 

$a>$

 

$\star$ Xét trường hợp cụ thể: $r=10$

 

Ta thấy $10=3^2+1^2$. Gọi hình chữ nhật đó nằm trên trục tọa độ $xAy$ với $A$ là gốc.

 

Điểm ở trên $A$ là $B$, điểm ở bên phải $A$ là $D$, điểm còn lại là $C$

 

Vì khoảng cách giữa hai tâm có và chỉ có thể là $\sqrt{10}$ nên có thể đi từ $A(0;0)$ đến $M(3;1)$

 

$\triangleright$ Gọi $a;b;c;d$ lần lượt là những lần mình đi theo kiểu $(3;1);(3;-1);(-3;1);(-3;-1)$

 

$\triangleright$ Gọi $a';b';c';d'$ lần lượt là những lần mình đi theo kiểu $(1;3);(1;-3);(-1;3);(-1;-3)$

 

Hiển nhiên có số lần đi là tự nhiên nên $a;b;c;d;a';b';c';d' \in N^*$

 

Đến đây, ta có hệ phương trình:

 

$\left\{\begin{matrix} 3a + 3b - 3c - 3d + a' + b' - c' - d' = 11\\ a + b - c - d + 3a' + 3b' - 3c' - 3d' = 0 \end{matrix}\right.\Leftrightarrow 8a'+8b'-8c'-8d'=11$

 

$\Rightarrow a'+b'-c'-d'=\frac{11}{8}$ Vô lí vì $a';b';c';d'$ tự nhiên.

 

Vậy hệ vô nghiệm hay không có cách đi nào với $r=10$ thỏa mãn bài toán được xét.

 

$\star$ Xét đến tổng quát:

 

$1.$ Nếu $r$ chẵn thì hoặc hai số tạo ra nó cùng chẵn hoặc cùng lẻ.

 

$1.1$ Nếu hai số tạo ra nó cùng chẵn thì ta làm giống hệt hướng giải với $r=10$ xin được không chứng minh lại

 

$1.2$ Nếu hai số tạo ra nó cùng lẻ thì ta lại xét trường hợp $B(11;0)$

 

Ta có:

 

Hoành độ có thể là $a+3;a-3;a+1;a-1$, tương tự cho tung độ, do đó ta có hệ

 

$\left\{\begin{matrix} 3a+b-3c-d=11\\ 3a'+b'-3c'-d'=0\\ |a|+|b|+|c|+|d|=|a'|+|b'|+|c'|+|d'|\\ \end{matrix}\right.$

 

Giải hệ và thấy hệ vô nghiệm với mọi $a;b;c;d;a';b';c';d' \in N^*$

 

Vậy không có cách đi nào với $r$ chẵn hay $r$ chia hết cho $2$ thỏa mãn bài toán được xét.

 

$2$ Nếu $r$ chia hết cho $3$ , ta đi xét cấu tạo số:

 

Bằng lập luận tương tự, ta cũng nhận một hệ phương trình vô nghiệm.

 

Vậy không có cách đi nào với $r$ chia hết cho $3$ thỏa mãn bài toán được xét.

 

Kết luận: Bài toán không giải được nếu $r$ chia hết cho $2$ và $3$.

 

$b>$ Áp dụng câu $a$ ta có ngay $r=73$ thỏa mãn bài toán

 

         Nhưng $r=79$ không thỏa mãn.

 

Mình nghĩ $r$ chia hết cho $3$ nó chưa chắc lập luận tương tự

Còn $r=73$ cần có 1 VD chứng minh


%%- Chuyên Vĩnh Phúc

6cool_what.gif


#15 buiminhhieu

buiminhhieu

    Thượng úy

  • Thành viên
  • 1150 Bài viết
  • Giới tính:Nam
  • Sở thích:Inequality

Đã gửi 26-05-2014 - 11:41

 

MSS54: angleofdarkness
 
b/
 
Nếu $r=73$ thì có $x^2+y^2=73=8^2+3^2$ nên $x=8;y=3$ hoặc ngược lại. Vậy ta có thể di chuyển từ một góc của một hình chữ nhật $9 \times 4$ vào góc đối diện của nó. 
 
Xét các bước đi có được như sau: $(0,0) \rightarrow  (8,3) \rightarrow (16,6) \rightarrow (8,9) \rightarrow (11,1) \rightarrow (19,4) \rightarrow (11,7) \rightarrow (19,10) \rightarrow (16,2) \rightarrow (8,5) \rightarrow (16,8) \rightarrow (19,0)$
 
Nếu $r=79$ là số nguyên tố, mà $r =x^2+y^2$ nên bài toán không giải được.

 

HIX,$79$ là số nguyên tố sao bài toán không giải được và $r=73$ nó không phải là số nguyên tố mà nó vẫn giải được đấy thôi !


%%- Chuyên Vĩnh Phúc

6cool_what.gif


#16 Super Fields

Super Fields

    Thiếu úy

  • Thành viên
  • 526 Bài viết
  • Giới tính:Không khai báo

Đã gửi 26-05-2014 - 13:37

Mình nghĩ $r$ chia hết cho $3$ nó chưa chắc lập luận tương tự

Còn $r=73$ cần có 1 VD chứng minh

Mình đã bổ sung thêm $79$ không thể viết dưới dạng $a^2+b^2$ ( Dễ chứng minh bằng đồng dư với $4$)

 

Nên $73$ hoặc theo câu $a>$ hoặc theo cách $73=8^2+3^2$ thì thoả bài toán. Mình nghĩ không cần cho ví dụ cụ thể.


$\dagger$God made the integers, and else is the work of man.$\dagger$


$\boxed{\textrm{My Blog}}$


#17 angleofdarkness

angleofdarkness

    Thượng sĩ

  • Thành viên
  • 246 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:K48 chuyên toán - THPT chuyên ĐHSP Hà Nội.

Đã gửi 26-05-2014 - 17:40

HIX,$79$ là số nguyên tố sao bài toán không giải được và $r=73$ nó không phải là số nguyên tố mà nó vẫn giải được đấy thôi !

 

nhầm, thiếu toi cái quan trọng là 79 k phân tích thành tổng hai scp đc -_-



#18 canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết
  • Giới tính:Nam
  • Đến từ:A1K43 THPT chuyên Phan Bội Châu
  • Sở thích:toán

Đã gửi 26-05-2014 - 21:58

$r=73$ bài toán vẫn có thể giải được theo các bước của 

 

 

 

$r=73 vẫn có thể thực hiện được

 

Thiếu $r=73$

bạn hiếu chỉ ra 1 cách khi r=73 cho mình cái



#19 buiminhhieu

buiminhhieu

    Thượng úy

  • Thành viên
  • 1150 Bài viết
  • Giới tính:Nam
  • Sở thích:Inequality

Đã gửi 26-05-2014 - 22:00

bạn hiếu chỉ ra 1 cách khi r=73 cho mình cái

Đây

 

 
 
Xét các bước đi có được như sau: $(0,0) \rightarrow  (8,3) \rightarrow (16,6) \rightarrow (8,9) \rightarrow (11,1) \rightarrow (19,4) \rightarrow (11,7) \rightarrow (19,10) \rightarrow (16,2) \rightarrow (8,5) \rightarrow (16,8) \rightarrow (19,0)$
 
 

%%- Chuyên Vĩnh Phúc

6cool_what.gif


#20 buithuyduong

buithuyduong

    Lính mới

  • Thành viên
  • 2 Bài viết

Đã gửi 12-07-2014 - 11:52

toán rời rạc nhiều dạng khủng lắm 







0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh