Đến nội dung

Hình ảnh

Topic các bài toán về phép toán, thuật toán biến đổi và các trò chơi

- - - - - hay vip kích thích sáng tạo thử thách

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

#1
bachhammer

bachhammer

    Thiếu úy

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

Xin chào tất cả các thành viên trên diễn đàn, mình là bachhammer. Mình lập topic này để cùng các bạn thảo luận về các bài toán xung quanh các phép toán, thuật toán và các trò chơi, vốn là một trong các dạng toán gần với thực tế, thường xuất hiện trong các đề thi khu vực , quốc gia (VMO), thậm chí là quốc tế (IMO). Các dạng toán này thường là những thuật toán, phép toán biến đổi, hay là những trò chơi mang tính logic cao. Hy vọng rằng với topic này sẽ đáp ứng được nhu cầu trao đổi của những bạn đã biết, sẽ biết và chưa biết. Thường ko có một phương pháp chung nhất định cho dạng này. Vì thế đỏi hỏi sự tư duy năng nỗ của người làm toán để đi đến đích. Xin đưa ra một ví dụ nhỏ thôi:

"Cho 2013 đồ vật được đánh số thứ tự từ 1 đến 2013, và các đồ vật ấy được bố trí thành vòng tròn theo thứ tự 1-2-3-...-2013-1 (tức là một chu trình khép kín), theo chiều quay của kim đồng hồ. Xét phép biến đổi sau: bắt đầu từ một vật nào đó mang số k, ta sẽ hoán đổi với vật mang số k+1 (nếu k = 2013 thì k+1 trùng với 1). Gỉa sử bắt đầu từ đồ vật mang số a, một người ngồi tại vị trí đồ vật mang số b, muốn lấy. Liệu dựa trên phép biển đổi này, người đó có thể lấy được đồ vật mang số a hay ko? Và cần tối thiểu bao nhiu bước để lấy được? (người này cũng hơi rãnh, ko tự lấy món đồ :biggrin:  :biggrin:  :biggrin: ...)".

Lời giải:

Không mất tính tổng quát ta giả sử a = 1 và b = 1 + k ($0\leq k\leq 2012$, quy ước 1 - 1 = 2013, 2013+1=1). Nếu như k = 0 thì người này ko cần đợi (vì nó nằm ở trước mặt).

Xét k khác 0 thì ta sẽ thấy như sau: Gọi tương ứng vị trí đồ vật thứ k là số k. Sau một lần biến đổi thì vị trí k sẽ có đồ vật mang số k + 1 (được tăng lên 1 đơn vị). Như vậy sau một lần biến đổi, đồ vật số m sẽ nằm ở vị trí m - 1. Như vậy sau một số bước biến đổi nó sẽ đến đúng vị trí mong muốn. Còn chuyện bao nhiu bước thì các bạn có thể tự tính... :lol: .

Qua ví dụ trên có thể thấy được cái hay của các bài toán dạng này. Mong được trao đổi cùng các bạn (nhớ ủng hộ nhé...)

Các bạn cũng có thể chia sẻ các bài toán dạng này trên topic này cũng được. Nguyên tắc là đảm bảo đề bài phải ghi số thứ tự (các bài tốt nhất là đừng trùng nhau, dễ nhầm). Và đề bài ko có sự lặp lại... Nhiu đó thôi.

Dĩ nhiên mình có hai bài trước:

Bài 1: Xét một số nguyên dương bất kì n và đặt $a_{1} = n$. Ta xem hai thuật toán sau:

a) $\left\{\begin{matrix} a_{n}=\frac{a_{n-1}+1}{2}(1)\\a_{n}=\frac{a_{n-1}}{2}(2) \end{matrix}\right.$

b) $\left\{\begin{matrix} a_{n}=\frac{a_{n-1}-1}{2}(1)\\a_{n}=\frac{a_{n-1}}{2}(2) \end{matrix}\right.$.

Trong đó (1) xảy ra khi $a_{n-1}$ lẻ, (2) xảy ra khi $a_{n-1}$ chẵn.

Hỏi số nào trong dãy $(a_{n})$ xuất hiện nhiều nhất nếu áp dụng liên tiếp thuật toán (1)? Cũng hỏi tương tự đối với thuật toán hai?

Bài 2: Cho một hình vuông 4 x 4 và 15 miếng ghép hình vuông nhỏ kích thước 1 x 1 có đánh số thứ tự từ 1 đến 15. Gắn các hình vuông theo thứ tự 1, 2, 3, 4, 5,...,15, từ trái qua và từ trên xuống. Xét phép biến đổi đẩy qua, đẩy lại, đẩy lên, đẩy xuống mà ko tháo các miếng hình vuông ra. Hỏi các biển đổi sau có tồn tại hay ko?

basdbahshdfghsgdf.png

 

 

 


:ukliam2: TOPIC SỐ HỌC - Bachhammer :ukliam2: 

Topic số học, các bài toán về số học

:namtay  :namtay  :namtay  :lol:  :lol:  :lol:  :lol:  :excl:  :excl:  :excl:  :lol:  :lol:  :lol: :icon6:  :namtay  :namtay  :namtay  


#2
Beethoven97

Beethoven97

    Lính mới

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

Bài 2: Cho một hình vuông 4 x 4 và 15 miếng ghép hình vuông nhỏ kích thước 1 x 1 có đánh số thứ tự từ 1 đến 15. Gắn các hình vuông theo thứ tự 1, 2, 3, 4, 5,...,15, từ trái qua và từ trên xuống. Xét phép biến đổi đẩy qua, đẩy lại, đẩy lên, đẩy xuống mà ko tháo các miếng hình vuông ra. Hỏi các biển đổi sau có tồn tại hay ko?

attachicon.gifbasdbahshdfghsgdf.png

Mình giải bài 2:

Ta định nghĩa về thông số sai trật tự D, đối với mỗi cách sắp xếp là số cặp miếng lát có thứ tự sai, chẳng hạn như trật tự đúng trong hình bên trái có D = 0, vì ko có cặp số nào sai thứ tự.

Lặp luận như sau: Xuất phát từ một cách sắp xếp có trật tự đúng, sau đó đẩy các miếng lát di chuyển vòng quanh, ta có được hình như bên dưới:

àdsffdsdfsdsfasfsadfsdf.png

Hình 1 ta có D =0

Hình 2 ta có D = 6

Hình 3 ta có D = 12.

Ta thấy nếu di chuyển các miếng hình vuông sao cho ô góc phải dưới luôn để trống thì D luôn chẵn.

Nhưng nếu 15 -> 14 và 14 -> 15 thì D = 1 (ko thể làm được). Vậy nên ta thấy ko thể tồn tại một phép biến đổi trên.(các đại lượng bất biến)...


Bài viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 21-07-2013 - 13:05


#3
bachhammer

bachhammer

    Thiếu úy

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

Thấy topic ko có người nên muốn làm nóng (thu hút ghé thăm):

Bài 3: Cho bàn cờ hình vuông được chia thành 2013 x 2013 hình vuông nhỏ kích thước cạnh 1 đơn vị. Ghép tọa độ vào như hình vẽ:

sadasdsdfsdfsd.png .

Xét một quân cờ vua bất kì năm trong ô có tọa độ (quy ước (tọa độ ngang; tọa độ dọc) là tọa độ của quân cờ) (a; b). Xét quan hệ đồng dư $a\equiv c(mod2);b\equiv d(mod2)$; $0\leq c\leq d\leq 1$. Nếu:

* $(c,d)=(0,0)$ thì quân cờ di chuyển lên ô có tọa độ (a; b - 1).

* $(c,d)=(0,1)$ thì quân cờ di chuyển qua ô có tọa độ (a + 1; b).

* $(c,d)=(1,0)$ thì quân cờ di chuyển qua ô có tọa độ (a - 1; b).

* $(c,d)=(1,1)$ thì quân cờ di chuyển xuống ô có tọa độ (a; b+1).

Hỏi cần đặt quân cờ ở ô nào để sau một số lần di chuyển thì nó đến đúng ô tâm của hình vuông (có tọa độ (1007; 1007))? Có bao nhiu vị trí thỏa mãn?

 

 

 

 

 


:ukliam2: TOPIC SỐ HỌC - Bachhammer :ukliam2: 

Topic số học, các bài toán về số học

:namtay  :namtay  :namtay  :lol:  :lol:  :lol:  :lol:  :excl:  :excl:  :excl:  :lol:  :lol:  :lol: :icon6:  :namtay  :namtay  :namtay  


#4
bachhammer

bachhammer

    Thiếu úy

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

Mình nghĩ cần nên có những bài dạng này để mọi người có thể cảm thấy sự thú vị của toán học đến ngỡ ngàng. Ở câu 2 thì nếu các bạn cho đại một con số tự nhiên bất kì (càng lớn càng tốt). Với thuật toán 1 sau một số hữu hạn bước sẽ thành toàn các số 1. Với thuật toán 2 ta ra các số 0 (các bạn thử chứng minh nhé...). Còn với bài 3 chỉ với một để ý sau: Ta hãy thay tất cả tọa độ bằng các con số 0, 1 tương ứng với tính chẵn lẻ của số trong tọa độ (là số đồng dư theo modulo 2). Xét 4 hình vuông tạo thành 1 hình vuông lớn như hình vẽ:

File gửi kèm  áhsgdyjhgs.bmp   1.97MB   239 Số lần tải

Ta kí hịu các mũi tên là hướng di chuyển của quân cờ thì ta thấy rõ nếu đặt một quân cờ trong nhóm 4 ô đó thì nó có khả năng đi vòng quanh... Xét tất cả các ô thuộc tọa độ dọc là 1. Khi đó theo kí hịu trên thì các quân cờ hoặc tiến xuống dưới và tiến ra khỏi bàn cờ hoặc sẽ tiến thẳng ra khỏi bàn cờ (loại TH này). Xét tất cả các ô có tọa độ ngang là 2013. Khi đó tương tự như trên ta cũng loại. Xét trong 2012 x 2012 ô còn lại. Theo nhận xét trên thì nếu ta chia 2012 x 2012 ô vuông thành các hình vuông 4 x 4 thì ta sẽ thấy nếu muốn tới ô cần tìm thì ta sẽ xét hình vuông dạng trên có chứa ô đó. Khi đó ta tìm được 3 ô xung quanh thỏa (tạm gọi là ô lân cận). Tóm lại có 4 ô thoả mãn yêu cầu bài toán (chắc là tự tìm được).

Thật sự đây chỉ là một TH nhỏ lẻ (số hơi lớn thôi), chứ thực chất ta hoàn toàn có thể tổng quát bài toán lên đến

n x n. Thử xem. Hy vọng có nhìu bạn tham gia ủng hộ mình topic này nhé.

Bài 4: Có 6 viên sỏi không sắp thứ tự lớn nhỏ. Trò chơi như sau: Ta chia 6 viên thành k đống (dĩ nhiên k phải < 7). Sau đó lấy trong mỗi đống một viên và lập thành 1 đống mới. Hỏi với mỗi cách chia bất kì, liệu sau một số hữu hạn bước ta có thể thu được các đống sau cho số các phần tử của mỗi đống nguyên tố cùng nhau? (Cho đề mang số 6 thể hiện sự hoàn hảo của số 6, ý bảo bài này hoàn hảo, ko mắt lỗi đìu kiện nào?)...


:ukliam2: TOPIC SỐ HỌC - Bachhammer :ukliam2: 

Topic số học, các bài toán về số học

:namtay  :namtay  :namtay  :lol:  :lol:  :lol:  :lol:  :excl:  :excl:  :excl:  :lol:  :lol:  :lol: :icon6:  :namtay  :namtay  :namtay  


#5
PolarBear154

PolarBear154

    Sĩ quan

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

Mình giải bài 2:

Ta định nghĩa về thông số sai trật tự D, đối với mỗi cách sắp xếp là số cặp miếng lát có thứ tự sai, chẳng hạn như trật tự đúng trong hình bên trái có D = 0, vì ko có cặp số nào sai thứ tự.

Lặp luận như sau: Xuất phát từ một cách sắp xếp có trật tự đúng, sau đó đẩy các miếng lát di chuyển vòng quanh, ta có được hình như bên dưới:

attachicon.gifàdsffdsdfsdsfasfsadfsdf.png

Hình 1 ta có D =0

Hình 2 ta có D = 6

Hình 3 ta có D = 12.

Ta thấy nếu di chuyển các miếng hình vuông sao cho ô góc phải dưới luôn để trống thì D luôn chẵn.

Nhưng nếu 15 -> 14 và 14 -> 15 thì D = 1 (ko thể làm được). Vậy nên ta thấy ko thể tồn tại một phép biến đổi trên.(các đại lượng bất biến)...

Ta thấy nếu di chuyển các miếng hình vuông sao cho ô góc phải dưới luôn để trống thì D luôn chẵn.

Anh giải thích rõ chỗ này giúp em đc k ạ?


Trong bất cứ hoàn cảnh công việc nào, không cúi đầu trước cái ác, không lùi trước hiểm nạn. Nhìn thẳng và đi trên con đường mình đã chọn: con đường mà sự nhẫn nại bao dung là những bước đi tới, hành trang là những ước mơ vô cùng bé nhỏ- chỉ xin làm một cành dương tưới trên cuộc đời đầy rẫy khô khát và bất trắc... 


#6
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Topic vắng quá nhỉ :))

Mình xin đóng góp một bài trò chơi sau :)

Bài 5: Annie và Bach chơi trò chơi. Họ bắt đầu với một tập hợp $S$ rỗng. Ban đầu, Annie đặt một số nguyên dương $m$ vào $S$. Sau đó, Bach phải đặt một số nguyên dương không là bội của $m$ vào $S$. Sau mỗi lượt chơi, một số $k$ nguyên dương có thể đặt vào trong $S$ khi và chỉ khi nó không thể biểu diễn được dưới dạng tổng của một số phần tử thuộc $S$ (tổng này có thể lặp lại các số hạng). Người thua cuộc là người phải đặt số $1$ vào tập $S$. Tìm người có chiến thuật thắng cuộc.


Bài viết đã được chỉnh sửa nội dung bởi LNH: 30-01-2014 - 12:01


#7
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Topic vắng quá nhỉ :))

Mình xin đóng góp một bài trò chơi sau :)

Bài 5: Annie và Bach chơi trò chơi. Họ bắt đầu với một tập hợp $S$ rỗng. Ban đầu, Annie đặt một số nguyên dương $m$ vào $S$. Sau đó, Bach phải đặt một số nguyên dương không là bội của $m$ vào $S$. Sau mỗi lượt chơi, một số $k$ nguyên dương có thể đặt vào trong $S$ khi và chỉ khi nó không thể biểu diễn được dưới dạng tổng của một số phần tử thuộc $S$ (tổng này có thể lặp lại các số hạng). Người thua cuộc là người phải đặt số $1$ vào tập $S$. Tìm người có chiến thuật thắng cuộc.

$m$ phải không nhỏ hơn 2 mới được chứ, không thì bài toán quá đơn giản.

P/S: Nhầm, vì nếu đặt 1 vào thì thua mất luôn.


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 02-02-2014 - 22:16


#8
nguyen0811105

nguyen0811105

    Lính mới

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

Topic vắng quá nhỉ :))

Mình xin đóng góp một bài trò chơi sau :)

Bài 5: Annie và Bach chơi trò chơi. Họ bắt đầu với một tập hợp $S$ rỗng. Ban đầu, Annie đặt một số nguyên dương $m$ vào $S$. Sau đó, Bach phải đặt một số nguyên dương không là bội của $m$ vào $S$. Sau mỗi lượt chơi, một số $k$ nguyên dương có thể đặt vào trong $S$ khi và chỉ khi nó không thể biểu diễn được dưới dạng tổng của một số phần tử thuộc $S$ (tổng này có thể lặp lại các số hạng). Người thua cuộc là người phải đặt số $1$ vào tập $S$. Tìm người có chiến thuật thắng cuộc.

nếu đặt các số nguyên tố vào thì có phải là không bao giờ có người thua cuộc không? 







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: hay, vip, kích thích sáng tạo, thử thách

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

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