Friday, August 30, 2013

Con kiến mà leo cành đa...

Ascending and Descending
M.C. Escher 1960
Con kiến mà leo cành đa,
Leo phải cành cụt leo ra leo vào,
Con kiến mà leo cành đào,
Leo phải cành cụt leo vào leo ra...

Hôm qua không biết lang thang thế nào mà lại chui vào nhà của bác Nguyễn Trọng Tạo, người đã viết tặng cô thôn nữ hái sen của XDTV câu:  "Mây ghé làng anh mây mặc yếm nâu... ".
Thấy có cái hình vẽ Mobius strip nổi tiếng của Escher[*] tò mò đọc thì mới biết cái hình đó chỉ là để câu khách. Ờ mà cũng hợp lý, vì quyển GEB cũng xuất bản theo khổ để bàn, coffee table, to uỵch. Vì thế quyển này thường được dùng để bày ngoài phòng khách, nơi uống trà, cà-phê trong nhà các trọc phú về tri thức,  tạm gọi là "trưởng giả trí tuệ" - có thể họ cũng đồng thời là triệu phú về tiền bạc tài sản - để phô trương tầm văn hóa của mình[**].

Tất nhiên, vì không có ý định mượn gió bẻ măng, bàn chuyện chính trị chính em, nên mình hoàn toàn lờ đi một sự thật là cái Mobius strip tạo thành hình chữ S, trông cũng na ná như hình một nước nào đó ở cái xứ Đông nam Á xa xôi mà rất đỗi gần gũi với mình.

Bài toán mà GS. Vũ Hà Văn nêu lên là thế này:
Có 10 con kiến trên một que 1 mét. Từng con kiến bắt đầu bò sang trái hoặc phải tùy hỉ, dọc theo que, với tốc độ 1 mét/giờ. Khi hai con kiến đụng đầu nhau chúng sẽ đổi hướng. Khi một con bò đến đầu que thì nó rới xuống đất. 
Hỏi: khi nào thì tất cả kiến rơi xuống đất? 

GS Ngô Bảo Châu đưa ra một lời giải cho GS Vũ Hà Văn như sau:
Bác Văn cấp cho mỗi con kiến một cái mũ đánh số từ 1 đến mười. Khi hai con kiến đụng độ nhau, thay vì đổi hướng, hai con kiến sẽ đổi mũ cho nhau. Trong bài toán mới này, hiển nhiên sau một giờ, cả mười con Kiến đều rơi vào mồm bác Văn đã há sẵn. Nếu có đo đạc trước, bác Văn còn có thể há mồm đúng lúc chúng rụng, khỏi bị bệnh há miệng mắc quai. Bài toán này dễ hơn bài cũ vì kiến chỉ đổi mũ, không đổi hướng.
...
Bác Văn thì không quan tâm lắm đến hoán vị, miễn là cả đàn kiến chui vào mồm là được.  

Ai quan tâm có thể đọc kỹ hơn ở đây

Lời giải đưa ra một cách giải thích rất hay là để cho các con kiến đổi mũ cho nhau mỗi khi cụng đầu, thay vì việc quay đầu đi ngược lại.

Kết luận của GS NBC về việc GS VHV có thể há miệng chờ xơi gọn tất cả các con kiến thì không hoàn toàn đúng nếu cái que nằm ngang, và sẽ chỉ đúng nếu một trong hai điều sau đây là đúng:
1./ Cái mồm của GS VHV có thể chuyển động với tốc độ ánh sáng, nhanh gấp tỷ lần tốc độ rơi tự do của các vật thể, dưới ảnh hưởng của từ trường trái đất, mà cụ thể ở đây là các chú kiến. Nếu vậy, có thể giả sử rằng khoảng cách 1m giữa hai đầu của cái que không có nghĩa lý gì!
2./ Cái mồm của GS VHV có đường kính ít nhất là 1m.
Vì tôi đã có dịp diện kiến GS Văn*** cho nên tôi biết mặc dù tài giỏi lẫy lừng nhưng anh cũng chỉ là người trần tục như chúng ta mà thôi. Không biết phép cân đẩu vân của Tôn Ngộ Không và mồm miệng thì cũng to vừa phải. Cho nên thế nào cũng có một vài chú kiến thoát, không bị GS Văn xơi tái.

Để tính số lần đụng đầu nhau tối đa của các chú kiến GS NBC bổ sung thêm:
...ta chỉ cần xác định hoán vị đổi mũ... là n(n-1)/2 trong trường hợp có n con kiến. Nhưng trong bài toán này, vì có một số kiến đi sang phải, một số đi sang trái, trong mỗi nhóm không chuyển vị với nhau, nên số lần đụng độ tối đa sẽ là n^2/4 nếu số kiến n là chẵn, và (n^2-1)/4 nếu n lẻ.


Tất nhiên,  một lần nữa tôi lại làm ngơ, mũ ni che tai, lờ đi không bình luận gì về cái ngụ ý, hàm ý hết sức tinh tế tàng ẩn trong cái ý "cụng đầu thì đổi mũ" hay "đi sang phải, đi sang trái" của GS NBC ;)

Như thường lệ, để thay lời kết luận, sau đây xin mời bà con, nhất là những ai đang chăm cháu nội, cháu ngoại, hoặc chăm con, nghe một bài hát thiếu nhi rất đỗi quen thuộc, bài "Con kiến leo cành đa".

Còn những ai chưa có cháu nội, cháu ngoại để chăm, hoặc vẫn còn bận bịu chăm lo cho chính bản thân mình thì xin mời nghe "Aria sur la ligne G" của Johann Sebastian Bach (tranh minh hoạ của Vincent Van Gogh).


2013.08.27

Chú thích:

[*] Lại nhớ nhà mình trên giá sách hồi trước bày quyến "Goedel, Escher, Bach" (GEB) của Hofstadter mà bây giờ đi  tìm thì  không biết nó ở đâu nữa!
[**] Trêu chọc, đâm bị thóc, chọc bị gạo một chút thôi. Kiểu khoe ngầm một cách kín đáo như thế còn tế nhị hơn chuyện khoe một cách lộ liễu trắng trợn là nhà mình cũng có GEB bày trên giá sách!
[***] Cũng đã từng học lớp i Chu Văn An!

10 comments:

  1. Loại toán kiến bò que này chỉ dùng simulation là có đáp số ngay
    Dùng randomize function
    1: rand(10,1) ... Tạo ra10 random positions for 10 ants
    If any two ant have same pos, doit again
    2: tao ra 10 distance variable
    Xi = pi + v*t .... Pi initial position
    3: startclock t voi dieu kien v = random -, + 1
    4: if xi < 0, or Xi > 1 stop xi, stop timer clock
    If N > 10 stop the master clock

    Run this loop100 time, find mean, std ... Đó là đáp só khá chính xác

    ReplyDelete
    Replies
    1. Đúng là kỹ sư có khác!

      Các nhà toán học thuần túy thì đúng là họ chỉ quan tâm đến lời giải cho bài toán đặt ra ở mức độ trừu tượng, tìm được ra cận trên, cận dưới là coi như giải xong. Triển khai ra thực tế đương nhiên là một bài tập về nhà cho độc giả...

      TN định giải xem chính xác thì lúc nào cả 10 con kiến rơi khỏi que à? Ôi nếu thế thì phải thêm biến ngẫu nhiên về chiều dài của mỗi con kiến, khả năng bám trụ của mỗi chú kiến khi chỉ còn 1,2,3,4,5 chân bám vào que, v.v... ;)

      Delete
  2. Phản đối Ngô Bảo Châu cướp mất "sinh quyền"!

    Bài toán vui kiến bò que đúng là do các nhà toán học nghĩ ra, chẳng có chút thực tế nào.
    Quan sát loài kiến mới thấy chúng chuyển động không theo qui tắc nào khi có một mình, còn khi đi theo đàn thì lại rất có trật tự. Chính vì vậy người ta mới hay dùng hình ảnh đoàn kiến để giáo dục tinh thần kỷ luật cho con người.
    Một đặc điểm nữa là chúng thích chạm đầu nhau và qua bộ râu để trao đổi thông tin. Vì vậy điểm hay nhất, sát thực tế nhất của bài toán là "đổi hướng khi chạm đầu nhau" lại bị Ngô Bảo Châu tước đoạt bằng cách "chụp mũ" cho kiến và bắt chúng đổi mũ cho nhau (mặc dù về mặt toán học thì hành động đó hoàn toàn tương đương với giả thuyết đầu bài).

    Tất nhiên các nhà toán học có thể tưởng tượng ra nhiều điều không có thực và đó là "toán quyền", nhưng cướp đi "sinh quyền" của con kiến, bắt cụng đầu đổi mũ mà không đổi hướng, là rất đáng bị lên án! Nói riêng bài toán này gặp phải con kiến "điên" cứ đi 5 bước đổi hướng một lần, thì Vũ Hà Văn có "há miệng" đến thế kỷ sau cũng không đớp được.

    Kiến mà biết "đội mũ và không đổi hướng" thì đã tiến lên Chủ nghĩa XH từ lâu và thống trị thế giới, chứ không phải loài người hay ngồi nghĩ vẩn vơ đâu.

    ReplyDelete
  3. Hề hề hề,
    Đúng là con kiến leo cành .....que thiệt.
    Các viện sĩ rách việc quá nhể, nghiên cứu cả con kiến nữa thì ..... thật là điên.
    Mang cái danh "chuyên tán" mà quả thật mõ tui chả biết tán cái này ra sao cả.....

    ReplyDelete
  4. Vấn đề mô phỏng (modelling) không hề (hề hề) "rách việc" anh Bình nhé : ví dụ:
    Mô phỏng chuyển động của bày ong, mô phỏng chuyển động quạt cánh của ruồi đã dẫn đến những kết quả "khủng khiếp" ấn tượng: loài ruồi sử dụng ít neuron thần kinh nhất gần như tối thiểu nhưng điều khiển được chuyển động cánh hết sức vi diệu.
    Dùng data recorded from traffic có thể mô phỏng hệ thống giao thông hữu hiệu tiết kiệm thời gian, nhiên liệu và ... Sinh mạng, (có một nhà khoa học mỹ sang ta để nghiên cứu cái đó và đã ... Mất mạng vì TAi nạn GT) và nghiên cứu đã bị bỏ qua nên ... Sinh mạng cứ mất ... Do giao thông ... Tăng dần đều ... :-(
    Các nhà toán học lý thuyết như NBC, VHV etc etc đặt ra các bài toán sinh động để kích thích trí tưởng tượng của sinh viên tìm ra lời giải ngắn gọn thú vị nhất, kể cả dùng lối tiếp cận thực nghiệm simulation miễn sao giải quyết tốt bài toán.
    Có rất nhiều nghiên cứu tưởng như vô bổ nhưng ... :)

    http://www.ted.com/talks/michael_dickinson_how_a_fly_flies.html
    http://www.ted.com/talks/a_robot_that_flies_like_a_bird.html

    ReplyDelete
    Replies
    1. Hế hề hề,
      Cái việc mô phỏng này nọ thì mõ tui đôi khi cũng phải dùng, nhưng mô phỏng con kiến nó leo cành .... que thì chưa biết.
      Cứ theo logic này thì có nhẽ sẽ có người nghiên cứu mô phỏng cả con cò mà đi ăn đêm nữa đây....
      Rắc rối quá, thôi cứ để cho các nhà .... viện sỹ nghiên cứu vậy. Còn mõ tui xin thú thực là chả nghiện mấy thứ đó và cũng không đủ khả năng để hiểu cho dù có bày nó ra trước mắt.
      Giá mà có ai bỏ công nghiên cứu hai cái hạt cơ bản là hạt lúa và hạt ngô thì mõ tui xin vỗ tay theo hầu .....
      Hề hề hề,....

      Delete
    2. Mô phỏng đàn cừu .. Hì hì ... Đã có bài toán thả cùu trên núi của người Thuỵ Sỹ đấy Anh Bình ạ ...
      Còn bầy sói thì khỏi cần mô phỏng .... Chúng nhìu qué :)

      Delete
    3. Nước mình văn minh ... Lúa nước nên mô phỏng .... Hạt lúa là đúng rồi .... Tuy nhiên bay giờ đất trồng lúa đã bị "nhóm đầy tớ" mô phỏng thành ... Địa ốc ... Và và và .... Túm lại là ở nước mình cứ "mô phỏng theo nhóm lợi ích " là "ích lợi nhóm " ngay thôi :)

      Delete
    4. Tiếp tục dòng tranh luận tại đây :
      http://blog.ichuvanan.org/2013/09/mo-phong-va-cach-tiep-can-cua-ky-su.html

      Delete