Đến nội dung


Chú ý

Do trục trặc kĩ thuật nên diễn đàn đã không truy cập được trong ít ngày vừa qua, mong các bạn thông cảm.

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 5 - toán rời rạc

mss 2014

  • Please log in to reply
Chủ đề này có 32 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 14-03-2014 - 18:41

Vào hồi 20h, Thứ Sáu, ngày 14/3/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 6, sẽ có 05 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 14-03-2014 - 19:39

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.


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 anhtukhon1

anhtukhon1

    Sĩ quan

  • Thành viên
  • 480 Bài viết
  • Giới tính:Nam
  • Đến từ:DOTA VIỆT NAM
  • Sở thích:TRÙM DOTA VIỆT NAM :O

Đã gửi 14-03-2014 - 20:35

Đề này hình như em nộp thì phải

Thôi kệ cứ làm vậy

ta tô màu các ô đen và ô trắng xen kẽ nhau ( ô đầu tiên là ô đen)

Khi đó ta có nhận xét: Các ô đen có dạng $2^{2k}=4^{k}\equiv 1(mod3)$

Các ô trắng có dạng $2^{2k+1}=4^{k}.2\equiv 2(mod3)$

Mà mỗi lần con mã nhảy sẽ nhảy qua 2 ô khác màu nhau mà con mã muốn quay về ô đầu tiên(không ăn ở ô đầu tiên lúc đầu) thì nó sẽ phải ăn ở số ô đen bằng số ô trắng

Khi con mã nhảy vào 1 ô đen và một ô trắng thì tổng 2 ô nó ăn sẽ đồng dư với (1+2)=0(mod3). Mà nó ăn số ô đen bằng số ô trắng vậy số ngô mà con mã ăn chia hết cho 3



#4 Rias Gremory

Rias Gremory

    Del Name

  • Thành viên
  • 1384 Bài viết
  • Giới tính:Nam
  • Đến từ:Quảng Bình
  • Sở thích:Mathematics

Đã gửi 14-03-2014 - 22:08

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

Bài làm MSS42

 

 

1924993_1431333857111274_1069286933_n.jp

 

Coi số hạt ngô trên các ô từ thứ một đến thứ sáu tư của bàn cờ là một dãy số $(u_{n}) : 1,2,4,8,16,32...$ với $n\leq 64$

Ta thấy rằng từ số hạng thứ hai trở đi thì mỗi số hạng đều bằng tích của số hạng đứng ngay trước nó với số $2$

Ta có : $u_{1}=1$

            $u_{2}=1.2$

            $u_{3}=1.2.2=1.2^{2}$

            ................

            $u_{64}=1.2^{63}$

Xét tổng : $S=2^{0}+2^{1}+2^{2}+2^{3}+...+2^{63}$

$\Rightarrow 2S=2^{1}+2^{2}+2^{3}+2^{4}+...+2^{64}$

$\Rightarrow S=2^{64}-1$

Vì lượt đi đầu ( đi hết 64 ô) , con mã không ăn hạt ở ô đầu tiên nên trong lượt đi này con mã ăn được $2^{64}-1-1$ hạt ngô

Lượt đi về con mã không ăn hạt ngô ở ô 64 , vậy số hạt ngô con mã ăn ở lượt đi về là $2^{64}-1-2^{63}$

Vậy tổng số hạt ngô con mã ăn được là $2^{65}-2^{63}-3$

Ta có $2^{2}\equiv 1$ (mod $3$ )

$\Rightarrow 2^{64}\equiv 1$ (mod $3$)

Nên $2^{65}\equiv 2$ (mod $3$) và $2^{63}\equiv 2$ (mod $3$)

Vậy $2^{65}-2^{63}-3\equiv 0$ (mod $3$)

 

Kết luận : số ngô mà con mã ăn chia hết cho 3.



#5 Rias Gremory

Rias Gremory

    Del Name

  • Thành viên
  • 1384 Bài viết
  • Giới tính:Nam
  • Đến từ:Quảng Bình
  • Sở thích:Mathematics

Đã gửi 14-03-2014 - 22:29

Bài toán trên chỉ là mở rộng của bài toán tính tổng $S=2^{0}+2^{1}+2^{2}+2^{3}+....+2^{n}$, với $n$ nguyên và $n\geq 1$

Mở rộng : Bàn cờ có kích thước là $\sqrt{n}\times \sqrt{n}$ với $n$ là số chính phương thõa mãn $n\geq 1$.

Trong ô cờ thứ nhất đặt $a.r^{0}$ hạt ngô.

Trong ô cờ thứ hai đặt $a.r^{1}$ hạt ngô

Trong ô cờ thứ ba đặt $a.r^{2}$ hạt ngô

..............
Trong ô cờ thứ $n$ đặt $a.r^{n-1}$ hạt ngô.

Với $a$ nguyên và $a\geq 1$

____________________________________________________________________________________________________________________

 

Tổng tất cả hạt ngô ở trên bàn cờ là $S=\sum_{k=0}^{n-1}ar^{k}=ar^{0}+ar^{1}+ar^{2}+...+ar^{n-1}$

Nhân cả $2$ vế với $r$ ta có : $r.S-S=ar^{n}-a\Rightarrow S=\frac{a(r^{n}-1)}{r-1}$

Lượt đi đầu tiên , quân mã không ăn số hạt ngô ở ô đầu tiên nên ở lượt này số hạt ngô quân mã ăn được là $\frac{a(r^{n}-1)}{r-1}-a$

Lượt đi tiếp theo , quân mã không ăn số hạt ngô ở ô $n$ nên ở lượt đi này số hạt ngô quân mã ăn được là $\frac{a(r^{n}-1)}{r-1}-ar^{n-1}$

Vậy số hạt ngô quân mã ăn được là $\frac{a(r^{n}-1)}{r-1}-a+\frac{a(r^{n}-1)}{r-1}-ar^{n-1}=a[\frac{2(r^{n}-1)}{r-1}-(r^{n-1}+1)]$



#6 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 14-03-2014 - 22:57

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

Ta tô màu trắng đen cho bàn cờ giống như trong cờ vua, giả sử ô thứ nhất màu đen thì ta luôn có ô máu đen có số hạt dạng $2^{2k}$$\equiv 1(mod 3)$ với $k\in \mathbb{N}$, ô màu trắng có số hạt dạng $2^{2k+1}$$\equiv 2(mod 3)$ ($k\in \mathbb{N}$)

Ta dễ thấy khi đi 1 nước, con mã đi tới 1 ô khác màu ô nó đang đứng 

Vậy nên để đi từ ô thứ nhất để đi lòng vòng về ô thứ nhất ta cần có 2n nước đi ($n\in \mathbb{N}$) trong đó có n nước đi vào ô trắng , n nước đi vào ô đen 

Gọi $S_{1}$ là số hạt con mã ăn được ở trong những ô trắng thì $S_{1}\equiv 2n(mod 3)$

     $S_{2}$ là số hạt con mã ăn ở trong những ô đen, do ô thứ nhất chỉ tính là ăn 1 lần nên $S_{2}\equiv n(mod 3)$

Suy ra tổng số hạt con mã ăn được là $S=S_{1}+S_{2}\equiv 2n+n\equiv 3n(mod 3) hay S\vdots 3$ (ĐPCM) 



#7 lovemathforever99

lovemathforever99

    Thượng sĩ

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

Đã gửi 14-03-2014 - 23:48

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

 

Bài làm của MSS 52:  bài toán rất khó diễn tả lời giải, mong btc thông cảm vs lời giải của e.

 

Ta tô màu trắng,đen cho 64 ô của bàn cờ và đánh số từ 1 đến 64. Và giả sử ô đầu tiên là ô trắng.Như vậy ô trắng được đánh số lẻ, ô đen đánh số chẵn. 

 

Bổ đề: Sau hữu hạn bước, con mã muốn trở về ô ban đầu thì nó phải di chuyển 1 số chẵn ô. 

 

Chứng minh: 

    Con mã di chuyển hình chữ L - 3 ô theo luật cờ vua nên nó luôn đi đến ô trái dấu so với ô ban đầu. 

    Theo điều giả sử, con mã đang đứng ở ô trắng, nên ô tiếp theo nó đi tới sẽ là ô đen, tiếp theo nữa là ô trắng,.. cứ liên tục như vậy sau hữu hạn bước sẽ trở về ô ban đầu là ô trắng : trắng 1, đen 1; trắng 2, đen 2;...; trắng n, đen n; trắng 1.

 

Vậy con mã đã đi qua 1 số chẵn ô ( không kể ô cuối cùng vì trùng với ô đầu tiên).

 

 Từ cách chứng minh của bổ đề trên, ta còn suy ra con mã đã di chuyển 1 số lượng ô trắng bằng với số lượng ô đen.

 

Trở lại bài toán :

 

1966924_258833100958139_755523558_n.jpg

Ta có: $2\equiv -1(mod 3)$

 Nên :  $2^{2k}\equiv 1(mod 3)$

           $2^{2k+1}\equiv -1(mod 3)$

( xem $2k$ là chẵn, $2k+1$ là lẻ)

 

Theo đề bài ô thứ n đặt $2^{n-1}$ hạt ngô.

 

Như vậy ô trắng có số ngô là lũy thừa của 2 với số mũ chẵn.

Ngược lại ô đen có số ngô là lũy thừa của 2 với số mũ lẻ.

 

Theo hình, dấu cộng biểu diễn số ngô ở ô đó $\equiv 1(mod 3)$

                  dấu trừ     biểu diễn số ngô ở ô đó $\equiv -1(mod 3)$

 

Theo bổ đề, con mã di chuyển 1 số ô trắng = số ô đen nên số dấu cộng = số dấu trừ, nghĩa là tổng số ngô $\equiv 1-1+1-1+...+1-1=0(mod 3)$

Vậy số ngô con mã đã ăn chia hết cho 3.


                                                 ''Chúa không chơi trò xúc xắc.''

Albert Einstein


#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 15-03-2014 - 00:11

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

 

MSS 54: 

 

Ta tô ô bàn cờ $8 \times 8$ sao cho các ô chứa số hạt ngô có số lũy thừa của 2 là lẻ thì màu đen, ngược lại, các ô chứa số hạt ngô có số lũy thừa của 2 là chẵn thì màu trắng, như vậy con mã sẽ xuất phát tại ô đầu tiên của bàn cờ (a8 - màu trắng ), hình vẽ cụ thể như sau:

 

1897801_1480367662184977_740563675_n.jpg

 

Ta thấy các ô đen - trắng so le nhau, không có ô nào cùng màu thẳng hàng.

 

Khi quân mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua thì mỗi lần di chuyển, quân mã sẽ đi đến một ô màu khác với ô hiện tại.

 

Do quân mã này không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên, nên:

Ô đầu tiên nó đi đến là ô màu đen;

Ô thứ hai nó đi đến là ô màu trắng;

Ô thứ ba nó đi đến là ô màu đen; ...

Quá trình cứ tiếp tục như vậy thì ta thấy nếu kết thúc bước đi của quân mã là ô màu đen thì số ô màu đen nó đã đi hơn số ô màu trắng là 1; còn nếu kết thúc bước đi của quân mã là ô màu trắng thì số ô màu đen và trắng nó đã đi là bằng nhau.

 

Mà theo bài thì sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó nên ô cuối cùng nó đi đến là ô màu trắng.

 

Vậy ta có số ô màu đen và trắng nó đã đi là bằng nhau, giả sử là n ô; tức số ô chứa số hạt ngô có số lũy thừa của 2 là lẻ và số ô chứa số hạt ngô có số lũy thừa của 2 là chẵn mà quân mã đã đi qua là như nhau (đều là n). (*)

 

Ta nhận xét số ngô ở mỗi ô đen và trắng có dạng là $2^{2k+1}$ và $2^{2k}$ với $k \in N$

 

Ta có $2^2 \equiv 1$ (mod 3) nên $2^{2k} \equiv (2^2)^k \equiv 1^k = 1$ (mod 3)

 

Suy ra $2^{2k+1}=2^{2k}.2 \equiv 1.2=2$ (mod 3)

 

Như vậy số ngô quân mã đã ăn ở mỗi ô đen đều chia 3 dư 2 và số ngô con mã đã ăn ở mỗi ô trắng đều chia 3 dư 1.

 

Kết hợp (*) thì ta có tổng số ngô mà con mã đã ăn sẽ chia cho 3 dư là 0, tức chia hết cho 3.

 

đpcm.

 

 

 

  



#9 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 15-03-2014 - 01:38

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

Bài dự thi trận $5$ của $\textrm{MSS}27$:

 

Chứng minh bổ đề phụ: Với $n\in \mathbb{N}$

 

$\triangleright $: $2^{n}\equiv 1(\bmod3)\Leftrightarrow 2\mid n$

 

Thật vậy, với $2\mid n$:

 

$\Rightarrow n=2k(k\in \mathbb{N})\Rightarrow 2^{n}=2^{2k}=4^{k}\equiv 1^{k}=1(\bmod 3)$

$\blacksquare$

 

$\triangleright$: $2^{n}\equiv -1(\bmod3)\Leftrightarrow 2\not{\mid}n$

 

Thật vậy, với $2\not{\mid} n$:

 

$n=2q+1\Rightarrow 2^{n}=2^{2q+1}=4^{q}.2\equiv 1^{q}.(-1)=-1(\bmod3)$

$\blacksquare$

 

Quay lại bài toán:
 
Vì bàn cờ vua $8 \times 8$ nên sẽ có $32$ ô đen và $32$ ô trắng xen kẻ nhau. Không mất tính tổng quát, giả sử quân mã bắt đầu ở ô trắng là $A8$. Theo giả thiết nên số hạt ngô sẽ được sắp xếp:
File gửi kèm  6.jpg   20.74K   0 Số lần tải
$A8=2^{0}$
$B8=2^{1}$
$C8=2^{2}$
...
$A7=2^{8}$
...
$H1=2^{64}$
 
Ta thấy ở những cột có số thứ tự chẵn ( tức $8,6,4,2$) ô trắng luôn là lũy thừa bậc chẵn của $2$
Và  ở những cột có số thứ tự lẻ ( tức $7,5,3,1$) ô đen luôn là lũy thừa bậc chẵn của $2$.
Lại thấy nếu quân mã xuất phát từ ô trắng $A1$ thì phải sau một số nước chẵn mới có thể trở về ô trắng lúc đầu ( thỏa đề)
 
Vậy nếu quân mã nhảy từ cột này sang cột khác, hàng nhích $\frac{+}{ }1$, ví dụ từ $M_{A8}\rightarrow M_{B6}\rightarrow M_{C4}...$ và luôn theo quy luật như vậy thì ta có đpcm.
 
Thật vậy, khi quân mã di chuyển thì màu của ô nó đứng lúc đầu sẽ thay đổi ( từ trắng sang đen và ngược lại). Tức $n$ trong bổ đề sẽ thay đổi theo ( từ chẵn sang lẻ và ngược lại). Sau một số nước đi chẵn, tổng số hạt ngô mà quân mã thu được sẽ $\equiv 1-1+1-1+1-1...+1-1=0(\bmod3)$ ( áp dụng bổ đề trên). Đây là điều phải chứng minh$\blacksquare$
-----------------------------------
$\bigstar$ Nếu mỗi ô chỉ được đi một lần thì bài toán sẽ được chứng minh đơn giản hơn. Nhưng đề ở đây chưa thật rõ ràng. Vì ( theo em) nếu mỗi ô chỉ được đi một lần thì tại sao "sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó". ?
 
Bài toán sẽ sai trong ví dụ sau. Các nước đi của quân mã:
 
$A8\rightarrow C7\rightarrow E6\rightarrow C5\rightarrow E4\rightarrow G5\rightarrow E6\rightarrow C7\rightarrow A8$
 
Trong đó, theo như đề thì số ngô ở ô $A8$ đầu tiên sẽ không được tính, ở ô $A8$ cuối quân mã sẽ ăn nốt hạt ngô ở đó . Lúc đó ta có số ngô quân mã thu được sau các nước đi trên:
 
$S=2^{10}+2^{20}+2^{26}+2^{36}+2^{30}+2^{20}+2^{10}+2^{0}=69862426625\not{\vdots}3$
 
Vậy sau $8$ nước đi trên, số hạt ngô mà quân mã thu được không chia hết cho $3$. Vô lí
----------------------------------
Vậy: Em xin được chứng minh theo cách mỗi ô chỉ được đi một lần. 
 
Áp dụng điều vừa chứng minh ở trên, giả sử nước đầu tiên quân mã đi là $B6$ thì trước nước cuối cùng quân mã phải ở ô $C7$, tức số nước đang lẻ ở ô có lũy thừa bậc chẵn của $2$, mà mỗi ô chỉ được đi một lần. Vậy tổng số thóc mà quân mã đã thu được ở thời điểm đó có dạng $2^{p}$ với $p$ lẻ tức tổng số thóc đó $\equiv -1 (\bmod3)$ (theo bổ đề). Vậy nước cuối cùng quân mã thu được hạt thóc ở ô $A8$ là $2^{0}=1$$\equiv 1 (\bmod3)$. Vậy cuối cùng số thóc mà quân mã thu được $\equiv -1+1=0 (\bmod3)$. Ta có điều phải chứng minh.
$\blacksquare \blacksquare \blacksquare$
 
Mở rộng $1$: Cho bàn cờ trống kích thước $m \times n$ , trong đó $m\leq n$ và $m;n$ đều lẻ, chứng minh một quân mã đặt từ một ô bất kì trên bàn cờ này không thể di chuyển sao cho trở lại được vị trí bạn đầu. 
 
Chứng minh:

Trên bàn cờ vua, các ô đen và trắng xen kẽ nhau, một quân mã luôn đi từ một ô tới ô khác màu. Vì $m$ và $n$ đều là lẻ nên khi đó số các ô đen và trắng trên bàn cờ là khác nhau. Chẳng hạn bàn cờ $5 \times 5$ có $13$ ô đen và $12$ ô trắng. Muốn quân mã trở lại ô ban đầu thì phải có số ô đen và trắng bằng nhau, tổng số ô trên các nước đi là số chẵn. Do đó một hành trình đó không thể đi qua mỗi ô đúng một lần khi số các ô trên bàn cờ là số lẻ(theo đường đi Hamilton).

Từ  đường đi Hamilton ta cũng chứng minh được mở rộng $2$: ( bằng lý thuyết đồ thị )

Cho bàn cờ vua trông có kích thước $8 \times 8$. Một con mã cũng được đặt ngẫu nhiên trên bàn cờ này. Hỏi quân mã có thể đi một hành trình sao cho kết thúc tại nơi nó bắt đầu đi sao cho mỗi ô chỉ được đi qua một lần? Biết quân mã đi theo đúng luật chơi cờ vua tức đi chéo hình chữ nhật có kích thước $2 \times 3$ hay gọi tắt là hình chữ $L-3$ 

 

Mở rộng $3$: Cho bàn cờ vua trông có kích thước $a \times a$ trong đó, $a\in \mathbb{N}^{*}$ và $3\mid a$. Đặt ngẫu nhiên số hạt ngô vào các ô trên bàn cờ sao cho tổng số hạt ngô bằng $a^{a}$ ( không chừa trống ô nào). Một con mã cũng được đặt ngẫu nhiên trên bàn cờ này. Hai người cùng chơi trò chơi sau. Mỗi lượt từng người sẽ di chuyển quân mã đi một nước và ăn số hạt ngô đặt ở ô vừa đi,nhưng không ăn hạt ngô ở ô bắt đầu, chỉ cho phép quân mã ăn số hạt ngô trong ô theo lũy thừa của $2$ ( tức $2^{0};2^{1};2^{2};...$). Cứ như thế... cho đến hết hạt ngô trên bàn cờ. Vì sao người chơi sau luôn thắng nếu có một chiến thuật hợp lí? Biết quân mã ở đây có thể nhảy tự do ( :P) sang bất cứ ô nào trên bàn cờ sao cho ô đó có hạt ngô ( có thể nhảy qua lại một ô bao nhiêu lần tùy ý) và người chiến thắng là người di chuyển mã để ăn hết hạt ngô cuối cùng.

 

Đáp án:

Người chơi sau luôn thắng nếu có chiến thuật như sau: 

Luôn nhảy đến ô có số hạt ngô có luỹ thừa bậc khác tính chẵn lẻ với luỹ thừa bậc (chẵn hoặc lẻ ) của $2$ mà người chơi trước đã ăn.

Chứng minh: Áp dụng bổ đề đã chứng minh ở đầu bài. Sau một lượt chơi, số hạt ngô còn lại trên bàn sẽ giảm đi một lượng $\equiv -1+1=0 (\bmod3)$. Cứ như thế cho đến hết lượt cuối cùng. Nguời thứ hai sẽ luôn là người đi sau và tin chắc mình sẽ ăn hạt ngô cuối cùng bởi $3\mid a\Rightarrow 3\mid a^{a}$ nên cứ mỗi lượt số sỏi lại chia hết cho $3$.

$\blacksquare \blacksquare \blacksquare \blacksquare \blacksquare$


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


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


#10 lovemathforever99

lovemathforever99

    Thượng sĩ

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

Đã gửi 15-03-2014 - 02:16

MSS 52 :

 

Vì lời giải trên của bài toán không liên quan đến kích thước của bàn cờ nên có thể mở rộng như sau:

 

Mở rộng 1: 

 

Bài toán vẫn đúng nếu thay bàn cờ $8 \times 8$ ô vuông bằng bàn cờ $n \times n$ ô vuông. (n là số tự nhiên lớn hơn 2)

 

Chứng minh giống như chứng minh bài toán, không có gì thay đổi.

 

Mở rộng 2:

 

Bài toán vẫn đúng nếu thay bàn cờ $8 \times 8$ ô vuông bằng bàn cờ $a \times b$ ô vuông. (với $a,b$ là 2 số tự nhiên bất kì lớn hơn hoặc bằng 2, nhưng a,b không thể đồng thời bằng 2)

 
Chứng minh giống như chứng minh bài toán, không có gì thay đổi.
 
Mở rộng 3:
 
Bài toán vẫn đúng nếu thay số hạt thóc đặt vào mỗi ô : $2^{k}$ được thay bằng $n^{k}$
 
Lúc này bài toán trở thành:

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt $n$ hạt ngô

Trong ô cờ thứ ba đặt  $n^{2}$hạt ngô

...

Trong ô cờ thứ 64 đặt $n^{n-1}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho $n+1$.

 
Chứng minh, lập luận cũng tương tự.Ta có: $n\equiv -1(mod  (n+1))$

 Nên :  $n^{2k}\equiv 1(mod  (n+1))$

           $n^{2k+1}\equiv -1(mod  (n+1))$

( xem $2k$ là chẵn, $2k+1$ là lẻ)

 

Theo đề bài ô thứ n đặt $n^{n-1}$ hạt ngô.

 

Như vậy ô trắng có số ngô là lũy thừa của n với số mũ chẵn.

Ngược lại ô đen có số ngô là lũy thừa của n với số mũ lẻ.

 

Theo hình, dấu cộng biểu diễn số ngô ở ô đó $\equiv 1(mod (n+1))$

                  dấu trừ    biểu diễn số ngô ở ô đó $\equiv -1(mod (n+1))$

 

Theo bổ đề, con mã di chuyển 1 số ô trắng = số ô đen nên số dấu cộng = số dấu trừ, nghĩa là tổng số ngô $\equiv 1-1+1-1+...+1-1=0(mod (n+1))$ 

Vậy số ngô con mã đã ăn chia hết cho n+1.

 


                                                 ''Chúa không chơi trò xúc xắc.''

Albert Einstein


#11 lovemathforever99

lovemathforever99

    Thượng sĩ

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

Đã gửi 15-03-2014 - 02:17

MSS 52 :

 

Vì lời giải trên của bài toán không liên quan đến kích thước của bàn cờ nên có thể mở rộng như sau:

 

Mở rộng 1: 

 

Bài toán vẫn đúng nếu thay bàn cờ $8 \times 8$ ô vuông bằng bàn cờ $n \times n$ ô vuông. (n là số tự nhiên lớn hơn 2)

 

Chứng minh giống như chứng minh bài toán, không có gì thay đổi.

 

Mở rộng 2:

 

Bài toán vẫn đúng nếu thay bàn cờ $8 \times 8$ ô vuông bằng bàn cờ $a \times b$ ô vuông. (với $a,b$ là 2 số tự nhiên bất kì lớn hơn hoặc bằng 2, nhưng a,b không thể đồng thời bằng 2)

 
Chứng minh giống như chứng minh bài toán, không có gì thay đổi.
 
Mở rộng 3:
 
Bài toán vẫn đúng nếu thay số hạt thóc đặt vào mỗi ô : $2^{k}$ được thay bằng $n^{k}$
 
Lúc này bài toán trở thành:

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt $n$ hạt ngô

Trong ô cờ thứ ba đặt  $n^{2}$hạt ngô

...

Trong ô cờ thứ 64 đặt $n^{n-1}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho $n+1$.

 

 
Chứng minh, lập luận cũng tương tự.
 
Ta có: $n\equiv -1(mod  (n+1))$

 Nên :  $n^{2k}\equiv 1(mod  (n+1))$

           $n^{2k+1}\equiv -1(mod  (n+1))$

( xem $2k$ là chẵn, $2k+1$ là lẻ)

 

Theo đề bài ô thứ n đặt $n^{n-1}$ hạt ngô.

 

Như vậy ô trắng có số ngô là lũy thừa của n với số mũ chẵn.

Ngược lại ô đen có số ngô là lũy thừa của n với số mũ lẻ.

 

Theo hình, dấu cộng biểu diễn số ngô ở ô đó $\equiv 1(mod (n+1))$

                  dấu trừ    biểu diễn số ngô ở ô đó $\equiv -1(mod (n+1))$

 

Theo bổ đề, con mã di chuyển 1 số ô trắng = số ô đen nên số dấu cộng = số dấu trừ, nghĩa là tổng số ngô $\equiv 1-1+1-1+...+1-1=0(mod (n+1))$ 

Vậy số ngô con mã đã ăn chia hết cho n+1.

 


                                                 ''Chúa không chơi trò xúc xắc.''

Albert Einstein


#12 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 15-03-2014 - 06:06

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

SBD: MSS 48

Bài giải:

Tô màu bàn cờ: ô thứ lẻ tô màu trắng, ô thứ chẵn tô màu đỏ:

1054721182_1269255632_574_574.jpg

Với $n$ là số lẻ bất kỳ thì : $2^n\equiv (-1)^n\equiv -1(mod3)$

      $n$ là số chẵn thì :$2^n\equiv (-1)^n\equiv 1(mod3)$

Suy ra $2^1\equiv 2^3\equiv ...\equiv 2^{63}\equiv -1(mod3)$

           $2^0\equiv 2^2\equiv ...\equiv 2^{62}\equiv 1(mod3)$

Do đó số ngô ở ô đỏ chia 3 dư 2, số ngô ở ô trắng chia 3 dư 1 $(1)$

Ban đầu, con mã đứng ở ô trắng

Sau bước $1$, con mã đứng ở ô đỏ (do cách đi của nó)

Sau bước $2$, con mã đứng ở ô trắng

Sau bước $3$, con mã đứng ở ô đỏ 

$...$

Sau bước $a$, con mã trở lại ô đầu tiên, đứng ở ô trắng

Như vậy số lần đi $a\vdots 2$ và số lần con mã ăn ở ô đỏ bằng số lần ở ô trắng và bằng $\frac{a}{2}(2)$

Từ $(1),(2)$ suy ra số ngô con mã ăn chia 3 cùng dư với: $\frac{a}{2}.2+\frac{a}{2}.1=\frac{3a}{2}\equiv 0(mod3)$

Vậy số ngô con mã ăn chia hết cho 3

 



#13 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 15-03-2014 - 16:11

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

MSS30 canhhoang30011999

Đầu tiên ta tô màu các ô có có số hạt ngô là số mũ chẵn là trắng có số mũ lẻ là đen thì theo cách đặt các hạt ngô ta được 1 bàn cờ vua có màu giống như 1 bàn cờ vua bình thường (đen trắng xen kẽ)

Ta lại dễ dàng thấy được con mã trong cờ vua khi di chuyển thì nó sẽ nhảy từ ô màu này sang ô màu khác 

Con mã của ta xuất phát ơ ô màu trắng nên dễ thấy để nó đi vào 1 ô màu trắng thì phải qua chăn nước đi (vì cứ sau 1 nước đi thì ô của nó lại đổi màu)

Từ đó ta thấy con mã cần chẵn nước đi để trở lại ô ban đầu 

Mà con mã lại đổi màu mỗi khi nó nhảy nên số ô màu trắng bằng số ô màu đen nó đi qua hay số ô có số hạt ngô có số mũ chẵn bằng số ô có số hạt ngô có số mũ lẻ (1)

Lại có $2^{2k}\equiv 1$ (mod 3)(2)

$2^{2q+1}\equiv -1$(mod 3)(3)

Từ (1) (2) (3) $\Rightarrow$ số ngô con mã ăn được chia hết cho 3



#14 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 15-03-2014 - 23:51

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

 

MSS 54: 

 

Mở rộng: Với những điều kiện về số ngô trong mỗi ô bàn cờ đã cho ở bài toán và lúc này, ở mọi vị trí xuất phát trên bàn cờ của quân mã (không nhất thiết là ô đầu tiên) thì nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô ban đầu và không nhảy trở lại ô ban đầu. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô ban đầu và ăn nốt hạt ngô ở ô đó.

 

Lúc này thì số ngô mà quân mã ăn cũng luôn chia hết cho 3.

 

Thật vậy: Ta cũng tô ô bàn cờ $8 \times 8$ sao cho các ô chứa số hạt ngô có số lũy thừa của 2 là lẻ thì màu đen, ngược lại, các ô chứa số hạt ngô có số lũy thừa của 2 là chẵn thì màu trắng, hình vẽ cụ thể như sau: 

1231555_1480952228793187_2009249559_n.jp

 

Xét quân mã xuất phát ở vị trí một ô màu trắng bất kì thì khi quân mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua thì mỗi lần di chuyển, quân mã sẽ đi đến một ô màu khác với ô hiện tại.

 
Do quân mã này không ăn ở ô ban đầu và không nhảy trở lại ô ban đầu, nên:
Ô đầu tiên nó đi đến là ô màu đen;
Ô thứ hai nó đi đến là ô màu trắng;
Ô thứ ba nó đi đến là ô màu đen; ...
Quá trình cứ tiếp tục như vậy thì ta thấy nếu kết thúc bước đi của quân mã là ô màu đen thì số ô màu đen nó đã đi hơn số ô màu trắng là 1; còn nếu kết thúc bước đi của quân mã là ô màu trắng thì số ô màu đen và trắng nó đã đi là bằng nhau.
 
Mà theo bài thì sau khi con mã đi xong nó quay trở về ô ban đầu và ăn nốt hạt ngô ở ô đó nên ô cuối cùng nó đi đến là ô màu trắng.
 
Vậy ta có số ô màu đen và trắng nó đã đi là bằng nhau; tức số ô chứa số hạt ngô có số lũy thừa của 2 là lẻ và số ô chứa số hạt ngô có số lũy thừa của 2 là chẵn mà quân mã đã đi qua là như nhau. (*)
 
Ta nhận xét số ngô ở mỗi ô đen và trắng có dạng là $2^{2k+1}$ và $2^{2k}$ với $k \in N$
 
Ta có $2^2 \equiv 1$ (mod 3) nên $2^{2k} \equiv (2^2)^k \equiv 1^k = 1$ (mod 3) Suy ra $2^{2k+1}=2^{2k}.2 \equiv 1.2=2$ (mod 3)
 
Như vậy số ngô quân mã đã ăn ở mỗi ô đen đều chia 3 dư 2 và số ngô con mã đã ăn ở mỗi ô trắng đều chia 3 dư 1.
 
Kết hợp (*) thì ta có tổng số ngô mà con mã đã ăn sẽ chia cho 3 dư là 0, tức chia hết cho 3.
 
Xét quân mã xuất phát ở vị trí một ô màu đen bất kì thì lập luận tương tự trên ta cũng có tổng số ngô mà con mã đã ăn sẽ chia cho 3 dư là 0, tức chia hết cho 3.
 
Vậy bài toán được c/m.


#15 Zaraki

Zaraki

    PQT

  • Phó Quản trị
  • 4259 Bài viết
  • Giới tính:Nam
  • Đến từ:Đảo mộng mơ.
  • Sở thích:Mathematics, Manga

Đã gửi 16-03-2014 - 08:40

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:
Trong ô cờ thứ nhất đặt 1 hạt ngô
Trong ô cờ thứ hai đặt 2 hạt ngô
Trong ô cờ thứ ba đặt 4 hạt ngô
...
Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.
 
Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.
 
Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

SBD:15
Lời giải.

File gửi kèm  Untitled.png   42.32K   2 Số lần tải

Ta đánh số thứ tự vào các ô trong bàn cờ vua như hình vẽ. Ô thứ $n$ có nghĩa là ô đó có $2^n$ hạt ngô trong ô.
Ta sẽ chứng minh rằng con mã đứng ở ô thứ $k$ bất kì, sau khi đi lòng vòng và trở lại ăn hat ngô ở ô thứ $k$ (ban đầu nó không ăn ở ô đó) thì số ngô con mã ăn luôn chia hết cho $3$.
 
Ở đây, ta định nghĩa ô chẵn là ô có số thứ tự chẵn, ô lẻ là ô có số thứ tự lẻ. Ta có hai nhận xét sau:
 
Nhận xét 1. Số ngô ở mỗi ô: Ô chẵn thì có số ngô trong ô luôn chia $3$ dư $1$, ô lẻ có số ngô trong ô chia $3$ dư $2$ (vì $2^{2k} \equiv 1 \pmod{3}$ và $2^{2k+1} \equiv 2 \pmod{3}$ với mọi $k \in \mathbb{N}$).
 
Nhận xét 2. Nước đi của con mã: Nếu ban đầu nó đứng ở ô chẵn thì sau bước di chuyển tiếp theo, nó đứng ở ô lẻ. Và ngược lại, nếu ban đầu nó đứng ở ô lẻ thì ở bước di chuyển tiếp theo, nó sẽ đứng ở ô chẵn. (Điều này có thể nhận thấy khi nhìn vào bàn cờ).
 
Đầu tiên, ta hãy xét trường hợp con mã bắt đầu tại ô chẵn. Sau lượt di chuyển đầu tiên, con mã bước vào ô lẻ. Và vì con mã không ăn tại ô đầu tiên nó đứng nên số ngô con mã ăn lúc đó chia $3$ dư $2$. Sau lượt di chuyển thứ hai, con mã bước vào ô chẵn, số ngô con mã ăn lúc đó sẽ chia $3$ dư $2+1=3$ hay chia hết cho $3$. 
 
Hành trình của con mã cứ tiếp tục như vậy. Và tính từ sau lượt di chuyển thứ nhất của con mã (lúc đó con mã ở ô lẻ), thì cứ hai lượt di chuyển từ ô lẻ đến ô chẵn, số ngô mà con mà con mã ăn sẽ được cộng thêm với một số chia hết cho $3$. 
 
Theo như đề bài, con mã sau khi đi lòng vòng sẽ quay lại ô đầu tiên nó bắt đầu, tức là ô chẵn. Điều đó đồng nghĩa với việc hai lượt di chuyển ô lẻ đến ô chẵn của con mã cứ tiếp diễn cho đến khi nó kết thúc di chuyển. Hay nói, cách khác, số ngô của con mã luôn được cộng với một số chia hết cho $3$. Mặt khác, ban đầu, con mã đã không ăn ô nó khởi đầu nên số ngô ban đầu của nó là $0$ (chia hết cho $3$) . Và cứ sau hai bước di chuyển đó, kết cục, số ngô con mã luôn là số chia hết cho $3$.
 
Trong trường hợp nó khởi đầu bởi ô lẻ, chứng minh hoàn toàn tương tự. 
Vậy số ngô mà con mã ăn luôn chia hết cho $3$. $\blacksquare$
 
Mở rộng 1. Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:
Trong ô cờ thứ nhất đặt 1 hạt ngô
Trong ô cờ thứ hai đặt $n$ hạt ngô
Trong ô cờ thứ ba đặt $n^2$ hạt ngô
...
Trong ô cờ thứ 64 đặt $n^{63}$ hạt ngô.
 
Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.
 
Hãy CM rằng số ngô mà con mã ăn chia hết cho $k$ với điều kiện $n^{2m} \equiv 1 \pmod{k}, n^{2m+1} \equiv -1 \pmod{k}, (k \in \mathbb{N})$.

 

Chứng minh hoàn toàn tương tự trên.


“A man's dream will never end!” - Marshall D. Teach.

#16 tranducmanh2308

tranducmanh2308

    Hạ sĩ

  • Thành viên
  • 79 Bài viết
  • Giới tính:Nam
  • Đến từ:A2k43 THPT chuyên Phan Bội Châu
  • Sở thích:xem phim,chơi bóng rổ, làm toán và lên FACE

Đã gửi 16-03-2014 - 10:56

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

MSS 34

Ta thấy được bàn cờ vua được tô màu bởi các ô đen và trắng xen kẽ nhau.

Không mất tính tông quát, ta giả sử ô cờ đầu tiên thứ nhất đặt 1 hạt ngô($2^{0}$ hạt ngô) màu trắng thì các ô trắng tiếp theo sẽ đặt $2^{2}$,$2^{4}$,...,$2^{62}$ hạt ngô, còn các ô màu đen sẽ đặt $2^{1}$,$2^{3}$,...,$2^{63}$ hạt ngô.

Con mã sẽ đứng ở ô màu trắng đầu tiên. Do con mã luôn đi từ ô trắng sang ô đen hoặc từ ô đen sang ô trắng nên từ ô đầu tiên nó sẽ đi sang ô màu đen, rồi từ ô đen đó đến ô trắng khác... cứ như vậy cho đến khi nó quay về ô trắng đầu tiên thì sô ô trắng mà nó đi nhiều hơn ô đen 1 ô (do khi đi nó bắt đầu từ ô màu trắng, khi quay về nó cũng về ô màu trắng và nó đi xen kẽ từ trắng sang đen và ngược lại)

Mà theo giả thiết nó không ăn hạt ngô ở ô đầu mà khi trở về ô đầu nó mới ăn và khi nó ăn ngô ở ô nào thì người ta lại đặt số ngô bằng số ngô ban đầu ở ô đó (khi nó quay lại 1 ô nào đó trên bàn cờ khác ô đầu tiên thì nó vẫn có thể ăn số ngô bằng số ngô trước đó) nên số ô đen mà nó ăn ngô cũng bằng số ô trắng mà nó ăn ngô. 

Lại có: các ô trắng được đặt  $2^{2}$,$2^{4}$,...,$2^{62}$ hạt ngô (số mũ chẵn ) nên ta đặt số ngô trong mỗi ô trắng là $2^{2k}$($k\in \mathbb{N}$,$k\leq 31$)

Tương tự ta đặt số ngô trong mỗi ô đen là $2^{2q+1}$ ($q\in \mathbb{N}$,$q\leq 31$)

do số ô đen mà nó ăn ngô cũng bằng số ô trắng mà nó ăn ngô nên ta gọi số ô đen(trắng) mà nó đi đến và đồng thời ăn ngô là $n$ ($n\in \mathbb{N}$,$n\geq 1$)

Từ đó ta có số ngô mà nó ăn là:

 $n.2^{2k}+n.2^{2q+1}=n(4^{k}+4^{q}.2)$

$4\equiv 1(mod 3)$$\Leftrightarrow 4^{k}\equiv 1(mod 3)$ và $4^{q}.2\equiv 2(mod 3)$

nên $4^{q}.2+4^{k}\equiv 3\equiv 0(mod 3)$$\Leftrightarrow n(4^{q}.2+4^{k})\equiv 0(mod 3)$

Suy ra số ngô mà nó ăn chia hết cho 3 (đpcm)


:wub: >:) :wub: :ukliam2: :ukliam2: :ukliam2:ĐÚNG THÌ LIKE :botay :like :botay SAI THÌ SỬA (SAI VẪN LIKE) :ph34r: @};- :ninja: :)) :blink: :P@@@


#17 nguyentrungphuc26041999

nguyentrungphuc26041999

    Sĩ quan

  • Thành viên
  • 406 Bài viết
  • Giới tính:Nam
  • Đến từ:A1K43 THPT Phan Bội Châu
  • Sở thích:bóng đá, làm toán, chơi game,đủ trò

Đã gửi 16-03-2014 - 20:38

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

Một con mã ô đầu tiên của bàn cờ, nó đi lòng vòng và ăn các hạt ngô trong ô nó nhảy đến( con mã di chuyển theo hình chữ L - 3 ô như đối với môn cờ vua) nhưng nó không ăn ở ô đầu tiên và không nhảy trở lại ô đầu tiên. Sau mỗi lần nó ăn người ta lại đặt số ngô bằng số ngô ban đầu vào trong ô đó. Sau khi con mã đi xong nó quay trở về ô đầu tiên và ăn nốt hạt ngô ở ô đó.

 

Hãy CM rằng số ngô mà con mã ăn chia hết cho 3.

 

Ta có 

$2^{2a}=4^{k}\equiv 1^{a}\left ( mod 3 \right )$

suy ra $2^{a}$ chia $3$ dư $1$

$2^{2b+1}=2.4^{k}\equiv 2.1^{b}\left ( mod3 \right )$

$2^{2b+1}$ chia $3$ dư $2$

Quay trở lại bài toán,đánh thứ tự cột từ trái sang phải là $a,b,c,d,e,f,g,h$,đánh thứ tự cột là $1,2,3,4,5,6,7,8$

gọi ô có số hạt ngô khi chia cho $3$ dư $1$ là ô trắng,gọi ô có số hạt ngô khi chia cho $3$ dư $2$ là ô đen

dễ thấy ô $a1$ là ô trắng,trong mỗi hàng, ô đen và ô trắng xen kẽ nhau theo nên ô cuối của hàng 1 (ô $a8$) là ô đen do mỗi hàng có 8 ô.

vì thế ô cuối cùng của hàng $2$ là ô trắng vì thế ô đầu tiên của hàng 2 là ô đen do mỗi hàng có 8 ô.

Lập luận như thế ta cũng có ở cột $a$ ô trắng và ô đen xen kẽ nhau.Nhưng do ô đen và ô trắng mỗi hàng xen kẽ nhau nên ô đen và ô trắng ở mỗi hàng cũng xen kẽ nhau.

Vậy ô trắng và ô đen đều xen kẽ nhau ở mỗi hàng và mỗi cột ( theo bàn cờ vua )

Dễ thấy sau mỗi lượt đi,con mã nhảy từ trắng sang ô đen và ô đen sang ô trắng.

Vì thế,sau mỗi 2 lần đi,con mã sẽ nhảy quá lanf ô trắng và 1 lần ô đen,số hạt ngô con ngựa ăn được sẽ chia hết cho 3(cho dù chúng có nhảy qua ô chúng đã đi qua hay không vì sau mỗi lần nó ăn,người ta lại đặt lại số ngô nó ăn)do $2^{2a}+2^{2b+1}\equiv 1+2\left ( mod 3 \right )$ hay chia hết cho $3$ 

Ta có, con ngựa xuất phát ở ô trắng và kết thúc ở ô trắng nên số nước đi của chúng là lẻ nhưng do ở ô đầu tiên nó không ăn hạt ngô đó,vì vậy số nước đi của nó là chẵn,nên số hạt ngô nó ăn chia hết cho 3 (đpcm)



#18 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 18-03-2014 - 07:22

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à.


#19 lovemathforever99

lovemathforever99

    Thượng sĩ

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

Đã gửi 18-03-2014 - 11:42

1484739_259745494200233_1356535561_n.jpg

 

em xin nộp lại hình (không hiểu tại sao máy tính của em vẫn không thể up ảnh lên được)


                                                 ''Chúa không chơi trò xúc xắc.''

Albert Einstein


#20 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 18-03-2014 - 12:22

SBD:15

attachicon.gifUntitled.png

 

 

Mình nghĩ là số ngô trong mỗi ô trong bài của bạn đã sai, vì thứ tự là:

 

Cho bàn cờ vua $8 \times 8$. Theo thứ tự từ trái qua phải, từ trên xuống dưới, ta làm việc sau:

Trong ô cờ thứ nhất đặt 1 hạt ngô

Trong ô cờ thứ hai đặt 2 hạt ngô

Trong ô cờ thứ ba đặt 4 hạt ngô

...

Trong ô cờ thứ 64 đặt $2^{63}$ hạt ngô.

 

 

Mình nghĩ là nó phải thế này:

 

File gửi kèm  untitled20.bmp   2.85MB   23 Số lần tải







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

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