Category: Vui học

Bài toán con kiến chui lỗ (TST 2017)

Published / by admin

Bình luận cho toàn bộ TST 2017 sẽ được đăng trên Sputnik Newsletter số 4 (04/2017), mời các bạn đón đọc!

(Nguyễn Tiến Dũng)

Các thầy Trần Nam Dũng và Ngô Văn Minh có nhờ tôi bình luận về bài toán số 1 của cuộc thi chọn đội tuyển IMO2017 của Việt Nam. Đề bài như sau:

Bài 1. Cho 44 cái lỗ phân biệt trên một cái rãnh là đường thẳng và 2017 con kiến. Mỗi con kiến sẽ chui lên từ một cái lỗ và bò đến một cái lỗ khác với vận tốc không đổi rồi chui xuống đó. Gọi T là tập các thời điểm mà con kiến chui lên hoặc chui xuống các cái lỗ. Biết rằng vận tốc của các con kiến đôi một khác nhau và |T| ≤ 45. Chứng minh rằng tồn tại ít nhất hai con kiến nào đó không gặp nhau.

Gợi ý lời giải: Có gì liên quan giữa các số 44, 45 và 2017? Dễ thấy 44 \times 45 = 1980 < 2017, nên có thể đoán đây là mấu chốt bài toán?

Vậy tai sao lại dùng tích? Bởi vì có nhiều nhất là từng đó điểm (vị trí, thời gian chạm lỗ khi lên hoặc xuống lỗ) trên mặt phẳng toạ độ. Ta vẽ trên mặt phẳng toạ độ các đồ thị đường đi của các con kiến, mỗi đồ thị là 1 đoạn thẳng nối 2 trong số các điểm trên. Tất cả các đoạn thẳng đó đều có hướng khác nhau (vì vận tốc các con kiến khác nhau). Hướng ở đây hiểu là góc so với đường nằm ngang modulo pi.

Câu hỏi đặt ra bây giờ là nếu hai đoạn một đều có điểm chung (hai con kiến nào cũng có gặp nhau) thì có nhiều nhất là bao nhiêu đoạn thẳng?

Ta có thể sắp xếp thứ tự các đoạn thẳng theo thứ tự vòng tròn theo góc của chúng.

Cố định 1 đoạn đầu tiên, từ điểm A1 đến điểm A2. Đoạn thứ hai có hướng quay về “bên phải” so với đoạn thứ nhất, nên phải có thêm ít nhất 1 điểm mới A3 (tức là hoặc là A1A3 với A3 nằm bên phải A1A2, hoặc A3A2 với A3 nằm bên trái A1A2, hoặc A3A4 (hai điểm mới) nằm ở hai bên của A1A2). Thêm đoạn thứ 3 phải thêm ít nhất 1 điểm mới, trừ trường hợp tạo thành 3 đoạn A1A2, A1A3, A2A3. Cứ như thế: thêm 1 đoạn thì cần thêm ít nhất 1 điểm mới, trừ khi thêm đoạn cuối cùng thì dùng được 2 điểm cũ. Như vậy để có n đoạn đôi một có điểm chung thì cần ít nhất n điểm. Với n = 44 lần 45 thì có nhiều nhất là từng đó con kiến đôi một có gặp nhau. Vì 2017 lớn hơn 44 lần 45 nên có hai con kiến không gặp nhau.

Thay vì nói đến hướng modulo pi, có thể chứng minh bằng quy nạp kiểu khác cho dễ hình dung hơn: Ta sẽ chứng minh bằng quy nạp rằng nếu có n điểm trên mặt phẳng thì không tạo được quá n đoạn thẳng với các đỉnh là các điểm đó sao cho đôi một có điểm chung và không có hai đoạn nào song song hay đè lên nhau.

Với n = 2, 3: hiển nhiên

Từ n-1 đến n:

Nếu có 1 điểm với không quá 1 đoạn xuất phát từ điểm đó, thì xoá điểm đó (và đoạn đó) đi, đưa về trường hợp n-1 điểm.

Giả sử bây giờ đỉnh nào cũng có ít nhất 2 đoạn xuất phát. Nếu có đỉnh A có 3 đoạn xuất phát thì sẽ “có vấn đề”: chẳng hạn là AB, AC, AD. Nếu BCD chứa A bên trong thì đoạn thứ hai từ B không thể cùng cắt AC và AD. Nếu BCD không chứa A bên trong thì ta có chẳng hạn tia AC nằm giữa hai tia AB và AD. Khi đó đoạn thứ hai từ đỉnh C không thể cùng cắt AB và AD. Như vậy từ mỗi đỉnh chỉ có đúng 2 đoạn, suy ra số đoạn bằng đúng số đỉnh trong trường hợp này.

Please follow and like us:

Toán Sputnik Lớp 6: Sắp hoàn thành cả bộ!

Published / by admin

Tin vui dành cho các học sinh và thầy cô giáo lớp 5 – lớp 6:

Bản thảo của bộ sách Toán Sputnik Lớp 6, Tập 1 (học kỳ 1) và Tập 2 (học kỳ 2) sẽ hoàn thành trong tháng 02/2017, sẵn sàng phục vụ các em học sinh lớp 6 ngay trong học kỳ 2 này, và các em học sinh chuẩn bị vào lớp 6 trong năm học 2017-2018.

Về mặt nội dung kiến thức, sách được viết sát theo chương trình trình hiện hành của Bộ Giáo Dục và Đào Tạo. (Khi nào Bộ công bố chương trình mới thì sách sẽ được chỉnh lại nhanh chóng theo chương trình mới). Chúng tôi hy vọng rằng các học sinh học theo sách Sputnik sẽ hiệu quả hơn nhiều so với sách độc quyền hiện hành của Bộ GD&ĐT.

  • Thích hợp với chương trình. Nội dung của sách phủ toàn bộ kiến thức mà Bộ Giáo Dục và Đào Tạo yêu cầu trong chương trình khung, và ngoài ra còn có một số phần đọc thêm (không bắt buộc, dành cho các học sinh tò mò hay có năng khiếu)
  • Toán có nghĩa. Học sinh đọc về khái niệm nào trong sách sẽ hiểu được ý nghĩa của nó, chứ không phải học những thứ “vô nghĩa” không hiểu để làm gì.
  • Chính xác và đúng bản chất. Mọi khái niệm đều được trình bày đúng bản chất tự nhiên của nó, và chính xác về mặt kiến thức khoa học.
  • Không giáo điều. Đưa ra các kiến thức không theo lối áp đặt, “sấm truyền”, mà theo lối gợi mở, khai phóng.
  • Gần gũi cuộc sống, với rất nhiều ví dụ từ cuộc sống thực tế, nhiều bài đọc thêm về ứng dụng trong thực tế, chỉ dẫn về các hoạt động thực hành.
  • Rành mạch, dễ hiểu. Học sinh có thể tự học theo sách mà vẫn nắm được toàn bộ kiến thức theo chương trình yêu cầu.
  • Trình tự logic hợp lý. Cái gì cần biết trước thì đặt lên trước.
  • Có các câu hỏi và bài tập hợp với trình độ và nội dung lý thuyết,  để học sinh có thể tự kiểm tra  và ôn tập kiến thức và rèn luyện kỹ năng.
  • Cơ bản, không mẹo mực. Các bài tập và kiến thức lý thuyết đều cơ bản, không lạc đề. Không có những thứ quá khó hay kiểu mẹo mực gây hoang mang cho học sinh.
  • Hiện đại và hội nhập quốc tế. Qua sách, học sinh sẽ biết được những điều hay về thế giới, về xã hội và công nghệ hiện đại.
  • Dễ tra cứu và mở rộng. Có chỉ mục (index) và các công cụ hỗ trợ khác cho việc tra cứu, và giới thiệu đến các sách vở tài liệu hay khác để học sinh nào tò mò có thể mở mang thêm kiến thức.
  • Vui học. Có những yếu tố trong sách làm cho việc học được vui, bớt
    căng thẳng mà lại tăng hiệu quả học tập.

Dưới đây là một vài trang nháp của oán Sputnik Lớp 6 – Tập 1, phần giới thiệu về phép trừ và số âm.

61_p32

61_p33 61_p34 61_p35

Please follow and like us:

SCRATCH: Những bài học lập trình đầu tiên

Published / by admin

Sputnik Education xin giới thiệu loạt bài viết về học lập trình với ngôn ngữ SCRATCH của TS. Bùi Việt Hà, ngường sáng lập School@Net ở Việt Nam, và là tác giả của quyển sáchđiện tử miễn phí: Tự Học Scratch.

Scratch là ngôn ngữ lập trình rất trực giác, dễ sử dụng, được Viện Công nghệ Massachusets (MIT) thiết kế, để dạy cho trẻ em làm quen với lập trình máy tính từ nhỏ.

Xin mời tải các bài học và sách xuống từ đây:

Tổng quan Scratch

MỤC ĐÍCH – MISSION của nhóm thiết kế Scratch:

Chúng tôi hỗ trợ một công cụ lập trình mới giúp trẻ suy nghĩ hợp lý hơn, hệ thống hơn, sáng tạo hơn, làm việc nhóm và rèn luyện các kỹ năng cần thiết trong xã hội hôm nay.

Phần mềm, môi trường Scratch có thể chạy, thực hiện theo các cách sau:

1. Tải phần mềm Scratch Offline để chạy như một ứng dụng độc lập trên máy tính.

2. Vào địa chỉ https://scratch.mit.edu/ và nháy lên lệnh Create để vào cửa sổ lập trình của Scratch trực tuyến (Scratch online).

1. Scratch là gì ?

Scratch là một môi trường, ngôn ngữ lập trình “kéo thả” mới xuất hiện trên thế giới và cũng rất mới đối với Việt Nam. Môi trường lập trình này rất đặc biệt vì nó thích hợp cho mọi lứa tuổi, mọi ngành nghề và trình độ. Vì sao mọi người cần học môi trường lập trình này? Vì sao Scratch lại thích hợp cho lứa tuổi thiếu nhi, thiếu niên và phù hợp cho việc đưa các kiến thức lập trình cho các bậc học này?

Môi trường và ngôn ngữ lập trình Scratch do nhóm nghiên cứu Lifelong Kindegarden Group thuộc đại học MIT (Massachusetts Institute of Technology) thiết lập đầu năm 2008. Ý tưởng ban đầu của nhóm chỉ là thiết lập một ngôn ngữ lập trình mới, đơn giản, chỉ dùng kéo thả, dành cho trẻ con để thiết lập trò chơi, phim hoạt hình, ứng dụng đơn giản, kích thích sự sáng tạo trong môi trường làm việc nhóm của trẻ.

Tuy nhiên Scratch chỉ thực sự bùng nổ từ năm 2014 khi một số quốc gia như Anh, Mỹ đã đổi mới đột phá chương trình giảng dạy môn Tin học trong nhà trường, đưa nội dung kiến thức Khoa học máy tính vào nhà trường ngay từ cấp Tiểu học. Một trong những đề nghị quan trọng nhất của các chương trình này là cần đưa các ngôn ngữ lập trình đơn giản, dạng kéo thả như Scratch vào giảng dạy trong nhà trường ngay từ Tiểu học. Việc điều chỉnh chương trình môn Tin học này đã kéo theo sự gia tăng bùng nổ của Scratch trên phạm vi toàn thế giới. Số lượng học sinh đăng ký tham gia trang Scratch tăng đột biến cả về số lượng và chất lượng. Thực tế đã chứng minh tính hấp dẫn của các môi trường lập trình kéo thả như Scratch, sự đam mê lập trình của trẻ nhỏ. Scratch vô cùng thích hợp cho trẻ lứa tuổi từ 6 đến 14, tức là các cấp Tiểu học, THCS của Việt Nam. Chính vì vậy trong Chương trình đổi mới giáo dục của Việt Nam sau 2018, Bộ Giáo dục & Đào tạo cũng đã quyết định đưa nội dung kiến thức Khoa học máy tính trong môn Tin học vào ngay từ cấp Tiểu học, và những ngôn ngữ lập trình kéo thả như Scratch sẽ là một lựa chọn tốt cho các nhà trường và học sinh.

2. Vài thông tin về môi trường và dự án Scratch

– Scratch là 1 môi trường lập trình ứng dụng đặc biệt, trong đó việc “viết” lệnh sẽ được thực hiện bằng thao tác “kéo thả”.

– Đầu ra của Scratch hỗ trợ các công nghệ và ứng dụng mới nhất của CNTT-ICT, do vậy các ứng dụng của Scratch rất phong phú, hấp dẫn, nhất là trẻ nhỏ.

– Scratch có sự phát triển bùng nổ 2 năm trở lại đây. Đặc biệt là sau khi một số quốc gia có tiềm lực khoa học kỹ thuật mạnh trên thế giới đã quyết đinh đưa Scratch vào giảng dạy trong nhà trường cho học sinh từ cấp Tiểu học.

– Scratch hoàn toàn miễn phí và có thể chia sẻ rộng rãi trong cộng đồng. Hiện nay trên Website chính của Scratch (https://scratch.mit.edu/) đã có hơn 15 triệu sản phẩm của Scratch được chia sẻ bới hơn 12 triệu người sử dụng trên khắp thế giới.

– Scratch rất thích hợp để tạo ra các ứng dụng đồ họa, animation, bài học, bài giảng, mô phỏng kiến thức, trình diễn, sách điện tử, trò chơi, … rất phù hợp với nhà trường, giáo viên, học sinh.

– Scratch là môi trường tốt nhất để dạy học sinh làm quen với tư duy máy tính, khoa học máy tính ngay từ lứa tuổi tiểu học.

Please follow and like us:

SGK Toán 6

Published / by admin

Sputnik đang bắt đầu tiển khai hợp tác cùng các đơn vị khác để làm series sách giáo khoa về toán (khi chưa được Bộ chính thức công nhận thì là sách tham khảo có tác dụng tương đương SGK)

Khởi đầu là SGK Toán 6 Tập 2, phục vụ ngay cho học kỳ 2 này.

Đây là 60 trang đầu tiên của bản nháp. Xin mời mọi người tham khảo và cho nhận xét:

http://sputnikedu.com/books/SGK62_60p.pdf

Ghi chú:

  • Một số bài tập trong bản nháp là lấy từ SGK cũ. Sẽ sửa đổi cho khỏi bị trùng.
  • So với SGK cũ thì sách Sputnik có rất nhiều điểm mới về cách tiếp cận, trình bày, định nghĩa, diễn giải, bài đọc thêm, tính hài hước, sự chính xác, sự tự nhiên của các khái niệm, tính lô gic, v.v. Xin mời bạn đọc tự xem và phán xét.

 

 

 

 

Please follow and like us:

Bài toán “3 cái nhà 3 cái giếng” và định lý Jordan-Schoenflies

Published / by admin

Bài toán “3 cái nhà 3 cái giếng” là một câu đố kinh điển sau đây:

Có 3 cái nhà (hay nhà kho)  và 3 cái giếng  (hay nhà máy, trạm cung cấp gì đó). Người ta muốn xây 9 con đường nối từ các nhà đến các giếng, mỗi đường từ một nhà đến một giếng, sao cho không có hai con đường nào bị vắt lên nhau và không có con đường nào đi xuyên qua nhà khác hay giếng khác. Hỏi có thể làm được điều đó không?

3Utilities

Bài toán này có thể phát biểu dưới dạng lý thuyết đồ thị: Hình dung mỗi cái nhà và mỗi cái giếng là đỉnh của đồ thị, và mỗi con đường là cạnh của đồ thị, ta sẽ được đồ thi ký hiệu là K_{3,3} (gồm có 2 bộ đỉnh, mỗi bộ 3 đỉnh, và cứ một đỉnh của bộ này và một đính của bộ kia thì có đúng một cạnh nối chúng, ngoài ra không có thêm cạnh nào khác). Câu hỏi là: đồ thì này có phải là đồ thị phẳng (planar graph) không?

Đồ thị phẳng là độ thị có thể vẽ trên mặt phẳng sao cho các cạnh không cắt nhau. Nói một cách chính xác hơn, một đồ thị gọi là phẳng nếu có thể nhúng nó qua một ánh xạ liên tục đơn ánh vào mặt phẳng.

Câu trả lời cho bài toán trên là:

Mệnh đề 1: K_{3,3} không phải đồ thị phẳng

(Suy ra không thể xây được đường thỏa mãn các điều kiện của câu đố 3 cái nhà 3 cái giếng).

Để chứng minh điều này một cách chặt chẽ, ta cần dùng một kết quả sau:

Mệnh đề 2: Nếu một đồ thị là phẳng thì có thể nhúng nó (theo một đơn ánh liên tục) vào mặt phẳng sao cho các cạnh trở thành các đường gấp khúc.

(Phép nhúng như vậy gọi là phép nhúng đa giácpolygonal embedding). Nói cách khác, thay vì dùng các đường liên tục tùy ý, ta chỉ cần dùng đến các đường gãy khúc (gồm một số đoạn thẳng nối lại với nhau).

Sử dụng Mệnh đề 1, ta có thể xây dựng một cách chứng minh khá đơn giản cho định lý Jordan nổi tiếng sau:

Mệnh đề 3 (Định lý Jordan). Nếu S là ảnh của một đơn ánh liên tục từ đường tròn vào mặt phẳng V = \mathbb{R}^2, thì V\setminus S không liên thông mà là hợp của hai miền liên thông, một “miền ngoài” không bị chặn và một “miền trong” bị chặn.

Đường cong S trong định lý Jordan được gọi là đường cong Jordan: nó khép kín và không tự cắt.

Trong trường hợp mà đường cong Jordan có dạng đa giác (một đường gãy khúc), bất kể lồi hay lõm, thì định lý Jordan khá hiển nhiên, và có một thuật toán đơn giản để xác định một điểm cho trước là nằm  ở miền trong hay miền ngoài của đường Jordan: kẻ một tia từ điểm đó. Có thể chọn tia sao cho nó chỉ cắt đường Jordan một số hữu hạn điểm. Nếu số điểm cắt đó là số chẵn, thì điểm ban đầu nằm ở miền ngoài, còn nếu số điểm đó là số lẻ, thì điểm ban đầu nằm ở miền trong.

Jordan3

(Một đường cong Jordan: đâu là miền trong đâu là miền ngoài?)

Đối với các đường trơn (khả vi) theo khúc, định lý Jordan cũng khá dễ dàng chứng minh. Nhưng đối với các đường phức tạp hơn, không trơn theo khúc, thậm chí không khả vi tại điểm nào hết, có dạng fractal, xoắn lung tung nhì nhằng khắp khơi, v.v., thì việc xác định một điểm cho trước là điểm nằm ở miền trong hay miền ngoài nhiều khi không đơn giản tí nào, và tuy định lý Jordan về mặt trực giác thì có thể dễ cảm thấy là đúng, nhưng để chứng minh chặt chẽ thì khác phức tạp. Hơn nữa, mở rộng của định lý Jorrdan lên trường hợp 3 chiều không còn đúng, với phản ví dụ nổi tiêng mang tên ‘mặt cầu có sừng của Alexander‘ (Alexander’s horned sphere).

AlexanderSphere

(Hình cầu có sừng của Alexander, ở Centre de Mathématiques et d’Informatique de Chateau-Gombert, Marseille)

Ở dưới đây chúng ta sẽ cố gắng đưa ra một chứng minh tương đối đơn giản cho định lý Jordan.

Schoenflies cải thiện kết quả của Jordan thành định lý sau:

Mệnh đề 4 (Định lý Jordan-Schoenlies) Nếu S là một đường cong Jordan trên mặt phẳng V = \mathbb{R}^2, thì tồn tại một đồng phôi (homeomorphism) từ V vào chính nó biến S thành một đường tròn.

(Hệ quả: Miền trong của một đường cong Jordan thì đồng phôi với hình tròn, còn miền ngoài đồng phôi với hình cái vành).

Chứng minh Mệnh đề 2:

Giả sử ta nhúng được một đồ thị K vào mặt phẳng. Ta sẽ chứng minh rằng có thể thay đổi cách nhúng sao cho các cạnh của K đều trở thành những đường gấp khúc không cắt nhau.

Cố đinh ảnh các đỉnh của K trên mặt phẳng (không cần thay đổi chúng). Có thể giả sử các đỉnh cách nhau một khoảng lớn hơn 2 đơn vị. Với mỗi cạnh c đi từ đỉnh P đến đỉnh Q, gọi A là điểm “đi ra khỏi P” với khoảng cách 1, tức là khoảng cách từ P đến A bằng 1, và các điểm nằm trên c từ A đến Q đều cách P một khoảng lớn hơn 1. Gọi Z là điểm “đi vào tới Q” với khoảng cách 1, tức là khoảng cách từ Z đến Q bằng 1, và các điểm nằm trên c từ P đến Z đều cách Q một khoảng lớn hơn 1. (Theo tính chất liên tục, thì các điểm này tồn tại và duy nhất). Bây giờ ta chỉ việc thay khúc đường đi từ P đến A trên c bằng đoạn thẳng PA,  thay khúc đường đi từ Z đến Q trên c bằng đoạn thẳng ZQ, và thay khúc đường đi từ A đến Z bằng một đường gấp khúc không tự cắt xấp xỉ nó với độ lệch đủ nhỏ. Theo cách đó, mọị cạnh đều trở thành đường gấp khúc, và chúng vẫn không cắt nhau như trước. Ta đã chứng minh xong Mệnh đề 2.

Dùng Mệnh đề 2 thì việc chứng minh Mệnh đề 1 trở nên dễ dàng. Sau đó dùng mệnh đề 1 thì việc chứng minh Mệnh đề 3 bằng phản chứng trở nên dễ dàng. Cuối cùng, có thể chứng minh Mệnh đề 4 bằng cách xấp xỉ dần dần.

Chứng minh mệnh đề 1 (dựa vào Mệnh đề 2):

Giả sử K_{3,3} là đồ thị phẳng. Theo Mệnh đề 1 có thể vẽ nó trên mặt phẳng, với các cạnh là các đường gấp khúc không cắt nhau. Gọi hai bộ đỉnh của đồ thị là A,B,C và X,Y,Z. Xét các “tứ giác”
AXBY (tạo bởi 4 cạnh gấp khúc) và BXCY. Chúng chia mặt phẳng thành 3 miền (hai miền “trong” và một miền “ngoài”), và ta có thể giả sử hai miền trong được bao bởi AXBY và BXCY. Đỉnh Z phải nằm ở một trong 3 miền đó. Nếu chẳng hạn Z nằm trong miền AXBY thì cạnh CZ sẽ phải cắt ít nhất một cạnh của tứ giác AXBY, vô lý. Các trường hợp khác cũng dẫn đến mâu thuẫn tương tự. Vậy K_{3,3} không phải đồ thị phẳng

Chứng minh mệnh đề 2 (dựa vào Mệnh đề 1):

Ý tưởng (lấy từ sách của Katok) là chứng minh rằng nếu mà đường Jordan nào đó không chia mặt phẳng thành 2 phần thì xây dựng được một đồ thị phẳng đẳng cấu với K_{3,3}, mâu thuẫn:

Kẻ hai đường song song a và b tạo thành một dải kẹp đường cong Jordan S vào bên trong, với một điểm A của S trên a và một điểm B của S trên b. Gọi x là một đường vuông góc với a và b và không cắt S. Gọi X là giao điểm của b và x. Kẻ một đường c song song với a và b và nằm giữa hai đường đó. Đường c cắt S tại ít nhất 2 điểm, trong đó có điểm Y là điểm “cao nhất” mà nằm ở “nửa đường dưới” S  của đi từ A đến B, còn Z là  điểm “thấp nhất” mà nằm ở “nửa đường trên” S  của đi từ A đến B. Gọi C là một điểm nằm trên đoạn thẳng YZ. Khi đó, nếu như có một đường nối từ C đến X mà không cắt S, thì những hình vừa xây dựng cho ta một đồ thị K_{3,3} trong mặt phẳng, tức là K_{3,3} là đồ thị phẳng, vô lý. Suy ra C và X phải nằm ở hai miền khác nhau của phần bù của S trong mặt phẳng, tức là mặt phẳng trừ đi S gồm có ít nhất 2 miền.

Tại sao lại chỉ có 2 mà không có nhiều hơn 2 miền? Để chứng minh điều này thì cần dùng đến bổ đề sau:

Mệnh đề 5 (Bổ đề). Nếu \gamma là một arc trên mặt phẳng (tức là ảnh của một đơn ánh liên tục f: [0,1] \to \mathbb{R}^2), thì hai điểm Y, Z bất kỳ không nằm trên \gamma có thể nối được với nhau bởi một đường gấp khúc không cắt \gamma. Nói cách khác, phần bù của \gamma là một miền liên thông (theo đường gấp khúc).

Jordan4

Please follow and like us:

Chồng phó mát và tháp Hà Nội

Published / by admin

Đây là một vấn đề thuật toán hết sức thú vị, và trường hợp riêng của nó đã được đem làm câu đố cho Spunik Newsletter Số 2. Chúng tôi xin trình bày lại nó thành riêng một bài dưới đây:

a) Bạn có thể đã nghe nói về bài toán Tháp Hà Nội: Có 3 cái cột, và có 8 miếng gỗ tròn có đục lỗ ở giữa được xếp vào cột thứ nhất tạo thành hình một cái tháp, sao cho miếng ở trên nhỏ hơn miếng ở dưới (tựa như các tầng tháp ở các ngôi chùa càng lên cao càng nhỏ dần).  Bây giờ cần dịch chuyển các miếng tròn giữa các cột với nhau, với nguyên tắc miếng to hơn thì không được xếp lên trên miếng thấp hơn, sao cho cuối cùng di chuyển được toàn bộ cái tháp từ cột thứ nhất sang cột thứ ba. Hỏi phải làm thế nào, và di chuyển mất (ít nhất) bao nhiêu nước? (Mỗi nước là di chuyển một tầng tháp từ cột này sang cột khác). Nếu thay số 8 bằng một số n bất kỳ thì sao?}

OLYMPUS DIGITAL CAMERA

b) Bây giờ chúng ta thay các các cột bằng các cái ghế, và các tầng tháp hình tròn bằng các miếng phó mát tròn kích cỡ tăng dần từ nhỏ đến to, thì bài toán vẫn như vậy. Nhưng bây giờ, thay vì có 3 cái ghế, ta có những 4 cái ghế, và được di chuyển các miếng phó mát giữa các ghế đó (với điều kiện như cũ: phó mát ở mỗi ghế phái xếp thành chồng, và không được để miếng to lên trên miếng nhỏ), thì cần ít nhất là bao nhiêu bước di chuyển để chuyển toàn bộ chồng phó mát gồm 8 miếng từ ghế thứ nhất sang ghế thứ tư?

c) Nếu thay vì 8 miếng phó mát và 4 ghế, ta có một chồng 11 miếng phó mát và 4 ghế thì sao? Cần bao nhiêu bước?

Câu đố này là cải biên từ câu đố đầu tiên trong quyển sách rất thú vị nhan đề  Những câu đố tư duy và lô-gic xứ Canterbury (Tủ sách Sputnik số 026) của tác giả Dudeney. Có thể mở rộng nó lên trường hợp n miếng phó mát và k ghế, tìm số bước B(n,k) di chuyển ít nhất.

01Reve

a) Trong trường hợp chỉ có 3 ghế (trò chơi Tháp Hà Nội), thuật toán khá là hiển nhiên: Cần chuyển chồng n-1 phó mát sang ghế thứ 2 rồi mới nhấc được miếng phó mát to nhất dưới cùng sang ghế thứ 3, rồi mới chuyển được chồng (n-1) miếng phó mát sang ghế thứ 3. Giả sử là ta không làm các động tác nào thừa (như kiểu làm một số bước dịch chuyển, mà sau đó trạng thái các chồng phó mát vẫn hệt như cũ) thì chỉ có mỗi cách làm như trên thôi, và ta có công thưc quy nạp:

B(n,3) = B(n-1,3) + 1 + B(n-1,3) = 2 B(n-1,3) + 1

(bởi vì để chuyển n-1 miếng phó mát từ cột đầu tiên sang cột thứ hai thì mất B(n-1,2)  bước, v.v.).

Từ công thức quy nạp này ta suy ra B(n,3) = 2^n - 1.

b) Trường hợp có n miếng phó mát (ở đây n=8)  và 4 ghế hoặc nhiều hơn, thuật toán tối ưu cũng phải là thuật toán “không có những bước thừa”. Lý luận để loại đi những hành động thừa, ta có thể thấy rằng thuật toán tối ưu phải gồm những công đoạn như sau:

– Công đoạn 1: Chuyển m miếng phó mát trên cùng (0 \leq n-1) từ ghế thứ nhất sang ghế thứ hai, mất B(m,4) bước.

– Công đoạn 2: Chuyển n-1-m miếng phó mát tiếp theo từ ghế thứ nhất sang ghế thứ 3, mất B(n-1-m,3) bước. (Chú ý rằng trong công đoạn 2 này thì không dùng được ghế thứ hai vì có những miến phó mát nhỏ hơn đặt ở đó, nên bài toán trở thành di chuyển với 3 ghế)

– Công đoạn 3: Chuyển miến phó mát to nhất sang ghế thứ tư, mất 1 bước.

– Công đoạn 4: Chuyển chồng phó mát từ ghế thứ ba sang ghế thứ tư, mất B(n-1-m,3) bước,

– Cộng đoạn 5: Chuyển nốt chồng phó mát từ ghế thứ hai sang ghế thứ tư, mất B(m,4) bước

(Ba công đoạn 2-3-4 có thể gộp thành một).

Tổng cộng, ta mất 1 + 2B(m,4) + 2B(n-1-m,3) = 2B(m,4) + B(n-m,3) bước di chuyển,
và ta được công thức quy nạp:

B(n,4) = \min_{0 \leq m \leq n-1 } (1 + 2B(m,4) + 2B(n-1-m,3))

Chú ý rằng, với mỗi n, ta phải chọn m tương ứng sao cho tổng B(m,4) + B(n-1-m,3) là nhỏ nhất.

Vì nói chung khi có nhiều ghế thì sẽ mất ít bước di chuyển hơn là khi chỉ có ít ghế, tức là ta luôn có B(m,4) \leq B(m,3) với mọi m, nên dễ thấy là m tối ưu phải thỏa mãn điều kiện m \geq n-1-m. Trong trường hợp n=8 thì m chỉ có thể nhận một trong 4 khả năng là 4,5,6 hoặc 7. Để so sánh các khả năng đó, ta phải lần lại theo quy nạp, tính ra B(4,4) = 7B(5,4) = 1 + 2 (B(2,4) + B(2,3)) = 1 + 2\times (3+3) = 13, B(7,4) > B(6,4) = 1 + 2(B(3,4) + B(2,3)) = 1 + 2 \times (5+3) = 17. Từ đây ta suy ra đối với n=8 thì m tối ưu là 5, và ta có

B(8,4) = 1 + 2 (B(5,4) + B (2,3)) = 1 + 2 \times (13 + 3) = 33

Đáp số: Trong trường hợp 8 miếng phó mát và 4 ghế  thì thuật toán tối ưu dùng 33 bước.

Câu c) với11 miếng phó mát phân tích tương tự, bạn đọc thử tự tính toán.

Trong sách  Những câu đố tư duy và lô-gic xứ Canterbury, Dudeney đưa ra một bảng để tính số bước tối ưu trong các trường hợp mà số ghế là k=3,4,5, và số phó mát là những số thích hợp nào đó.

Lập  một bảng như sau: Hàng đầu tiên bao gồm các số tự nhiên liên tiếp. Hàng thứ hai nhận được bằng cách cộng tổng các số tính từ số đầu tiên của  hàng thứ nhất, ví dụ 1+2+3 = 6 là số thứ ba của hàng thứ hai  (các số này có dạng n_i = i(i+1)/2, gọi là các số tam giác). Hàng thứ ba nhận được bằng cách cộng tổng các số tính từ số đầu tiên của hàng thứ hai, ví dụ $1+3+6 = 10$ là số thứ ba của hàng thứ ba.  Hàng thứ tư là dãy các số có dạng 2^i-1.

Hàng tiếp theo nhận được bằng cách nhân đôi số phía trước rồi cộng thêm với số phía trên, ví dụ 49 = 17 \times 2 + 15 là số thứ tư của hàng này. Hàng cuối cùng cũng nhận được theo cùng công thức quy nạp
như hàng thứ năm.

HanoiTowerCheese

Bảng này cho ta kết quả trực tiếp cho trường hợp 3 ghế và số miếng phó mát bất kỳ,  trường hợp 4 ghế với số miếng phó mát dạng tam giác (tức là các số n_i = i(i+1)/2), và trường hợp 5 ghế với số miếng phó mát dạng hình chóp. Trong những trường hợp này, có thể chỉ ra phương pháp tối ưu như sau:

Trong trường hợp nhiều hơn 3 ghế: thuật toán dựa trên quy nạp và  phương pháp tách chồng theo như các công đoạn ghi phía trên. Chẳng hạn nếu có 4 ghế và 10 miếng phó mát thì ta làm như sau: Ta di chuyển 6 miếng phó mát ghế thứ nhất sang ghế thứ hai mất B(6,4) bước, rồi di chuyển 4 miếng phó mát còn lại  từ ghế thứ nhất sang ghế thứ tư mất B(4,3) = 1 + 2 B(3,3) bước, rồi di chuyển 6 miếng phó mát từ ghế thứ hai sang ghế thứ tư, mất thêm B(6,4) bước nữa, tổng cộng là B(10,4) = 2 B(6,4) + B(4,3) = 2 \times 17 + 15 = 49 bước.

Theo bảng của Dudeney, chúng ta nhận thấy, chẳng hạn khi có 4 ghế và số phó mát là một số dạng n = i(i+1)/2 thì phải chọn số  m tương ứng bằng m = i(i-1)/2. Nhưng vì sao số m này lại là số tối ưu thì Dudeney không giải thích. Bạn có thể giải thích vì sao được không?

Please follow and like us:

Bài toán tô màu và định lý điểm bất động

Published / by admin

Nguyễn Tiến Dũng

Bởi toán học là một thể thống nhất, nên không những chỉ “hình học chẳng qua là đại số được vẽ ra, đại số chẳng qua là hình học được viết ra” như theo lời của Sophie Germain, mà những thứ khác của toán học tưởng chừng “xa cách ngàn trùng” cũng nối kết khăng khít với nhau.

Một ví dụ rất hay về chuyện gắn kết này là bài toán tô màu (một vấn đề tổ hợp) và định lý điểm bất động (trong giải tích, tô-pô)

Trước hết, ta xét bài toán tô màu, là một bài toán tổ hợp sơ cấp sau đây:

Sperner1Cho một tam giác ABC. Chia nó ra thành nhiều tam giác con một cách tùy ý. Tô màu các đỉnh của các tam giác con bằng 3 màu xanh, vàng, đỏ, sao cho: A tô màu xanh, B tô màu vàng, C tô màu đỏ, các đỉnh trên cạnh AB thì phải có màu là xanh hoặc vàng (giống như màu A hoặc B), các đỉnh trên cạnh BC thì phải có màu là vàng hoặc đỏ (giống màu của B hoặc C), và các đỉnh trên cạnh CA thì phải có màu là đỏ hoặc xanh (giống như màu của C hoặc A). Xem hình vẽ minh họa. Chứng minh rằng: Khi đó luôn tồn tại ít nhất 1 tam giác con có 3 đỉnh được tô bằng đủ 3 màu xanh, vàng, đỏ.

Bài toán trên được biết đến với tên gọi Bổ đề Sperner (Sperner’s lemma), do nhà toán học người Đức Emanuel Sperner (1905-1980) nghĩ ra trong một bài báo từ năm 1928.

Có cách chứng minh rất đơn giản sau đây cho bài toán trên:

Vẽ một đồ thị, trong đó có một đỉnh ứng với miền bên ngoài của tam giác ABC và mỗi đỉnh còn lại ứng với một tam giác con bên trong tam giác ABC. Mỗi cạnh của đồ thị ứng với hai miền (tam giác con hoặc miền bên ngoài) có chung nhau một cạnh có một đầu được tô màu xanh và một đầu được tô màu vàng. Số cạnh xuất phát từ đỉnh “ngoài” (tức là đỉnh ứng với miền nằm bên ngoài tam giác ABC) là một số lẻ (Vì sao vậy?). Suy ra có ít nhất một đỉnh “trong” có số cạnh cũng là số lẻ (vì tổng tất cả các số cạnh của tất cả các đỉnh là số chẵn, bằng 2 lần tổng số cạnh của đồ thị). Nhưng mỗi đỉnh trong ứng với một tam giác con, và số cạnh của nó chỉ có thể là 0, 1 hoặc 2 tùy theo các màu trên các đỉnh của tam giác con đó, và số đó là 1 khi và chỉ khi ba đỉnh có ba màu khác nhau xanh-vàng-đỏ. Vậy có ít nhất một tam giác con có ba đỉnh xanh-vàng-đỏ. Hơn thế nữa, số tam giác con như vậy phải là một số lẻ!

Bồ đề Sperner không những chỉ đúng trong trường hợp tam giác 2 chiều, mà còn đúng trong trường hợp n chiều trong đó n là một số tự nhiên bất kỳ. Khi n=1 thì nó phát biểu như sau:

Đánh dấu một số hữu hạn điểm trên một đoạn thẳng AB, chia nó thành một số đoạn thẳng con. Tô màu các điểm đó và A, B bằng hai màu xanh, đỏ sao cho a có màu xanh, B có màu đỏ. Khi đó có ít nhất một đoạn thẳng con có hai đầu có màu khác nhau xanh và đỏ. (Hơn thế nữa, số đoạn thẳng thẳng con như vậy là số lẻ).

Sperner2
Trường hợp 1 chiều phía trên của bổ đề Sperner khá là hiển nhiên và có thể chứng minh dễ dàng bằng quy nạp theo số điểm: cứ mỗi lần thêm 1 điểm thì số đoạn thẳng con có hai đầu có màu khác nhau hoặc là giữ nguyên hoặc là thêm 2, nên số lượng của chúng luôn là số lẻ. Trong lúc chứng minh bổ đề Sperner cho trường hợp 2 chiều, chúng ta đã dùng đến bổ đề 1 chiều này khi nói rằng số cạnh của đỉnh “ngoài” trong đồ thị mà ta xây dựng là một số lẻ.

Trong trường hợp 3 chiều, ta phải thay hình tam giác bằng một hình tứ diện ABCD, chia nó thành các hình tứ diện con, và tô các đỉnh bằng 4 màu (sao cho các đỉnh nằm trên mỗi mặt của ABCD phải có màu trùng với màu của một trong 3 đỉnh của mặt tam giác đó). Khẳng định vẫn là: số tứ diện con mà 4 đỉnh được tô bằng 4 màu khác nhau là số lẻ. Chứng minh vẫn hệt như cũ: xây dựng đồ thị với một đỉnh “ngoài” (ứng với miền nằm ngoài tứ diện) và các đỉnh “trong” (mỗi đỉnh ứng với một tứ diện con). Một cạnh nối hai đỉnh sẽ ứng với một mặt tam giác chung của hai miền mà có 3 đỉnh được tô bởi đủ 3 màu cho trước nào đó. Khi đó số cạnh của đỉnh “ngoài” là số lẻ (theo bổ đề Sperner hai chiều), suy ra có một số lẻ các đỉnh trong có số cạnh là số lẻ. Những đỉnh đó sẽ là những đỉnh có đúng 1 cạnh, và ứng với tứ diện con có 4 đỉnh được tô 4 màu khác nhau.

Cứ tiếp tục như vậy, bằng cách quy nạp theo số chiều, ta chứng minh được bổ đề Sperner trong trường hợp tổng quát với số chiều tùy ý.

Bây giờ, ta chuyển sang định lý Brouwer về điểm bất động, do nhà toán học Luitzen Brouwer (1881-1966) người Hà Lan chứng minh vào quãng năm 1910. (Jacques Hadamard cũng chứng minh kết quả này vào năm 1910 một cách độc lập, tuy nhiên không hiểu sao người ta gọi nó là định lý Brouwer mà không gọi là định lý Brouwer-Hadamard). Nó có thể phát biểu như sau:

Mọi ánh xạ liên tục f: \Delta \to \Delta từ một hình lồi đóng và bị chặn n chiều bất kỳ \Delta vào chính nó có ít nhất một điểm bất động, tức là một điểm x nằm trong \Delta sao cho f(x) = x.

Định lý Brouwer có rất nhiều ứng dụng trong toán học. Ví dụ như John Nash (nhà toán học đoạt giải Nobel về kinh tế) đã dùng định lý này để chứng minh sự tồn tại của các điểm ổn định Nash trong các trò chơi chiến lược.

Các cách chứng minh “thuần túy giải tích” của định lý Brouwer khá là rắm rối. Nhưng có một cách chứng minh rất trực giác và dễ hình dung và tương đối sơ cấp, dựa trên bổ đề Sperner! Chính vì vậy, người ta còn gọi bổ đề Sperner là “định lý Brouwer tổ hợp“. Cách chứng minh đó như sau:

Ta sẽ chứng minh trong trường hợp 2 chiều (trường hợp tổng quát hoàn toàn tương tự), và có thể giả sứ \Delta = \Delta ABC là tam giác ABC. (Nếu nó không phải tam giác thì có thể kéo nó co dãn thành hình tam giác, nói theo ngôn ngữ chính xác thì là nó “đẳng phôi với tam giác”, nên kết quả không thay đổi).

Xét ánh xạ liên tục f: \Delta \to \Delta, và cố định một điểm O nằm bên trong \Delta ABC. Ta sẽ tô màu tất cả các điểm của \Delta, theo nguyên tắc sau: Nếu hướng của vector \vec{Pf(P)} nằm kẹp giữa hai vector \vec{OB}, \vec{OC} thì tô màu xanh, nếu nó nằm kẹp giữa \vec{OC}, \vec{OA} thì tô màu vàng, nếu nó nằm kẹp giữa \vec{OA}, \vec{OB} thì tô màu đỏ. Nếu chẳng hạn nó trùng hướng với \vec{OA} thì chọn một trong hai màu vàng và đỏ. Ta có thể tô như vậy, sao cho A,B, C có màu tương ứng là xanh, vàng, đỏ, không có điểm nào trên đoạn AB  có màu đỏ, không có điểm nào trên đoạn BC  có màu xanh, không có điểm nào trên đoạn CA  có màu vàng, như là trong bổ đề Sperner.

Chia \Delta thành các tam giác nhỏ dần và nhỏ dần, rồi áp dụng định lý Sperner, ta được một dãy các tam giác con A_n B_n C_n của \Delta có đường kính nhỏ dần đến 0, sao cho các đỉnh của mỗi tam giác đều được tô bằng đủ 3 màu. Đặt tên lại các đỉnh nếu cần thiết, ta có thể giả sử các điểm A_n đều có màu xanh, các điểm B_n đều có màu vàng, các điểm C_n đều có màu đỏ.

Sử dụng tính chất đóng và bị chặn (tức là tính chất compact) của \Delta, ta tìm được một dãy con của dãy điểm  A_n hội tụ. Có thể giả sử luôn đó chính là dãy A_n, và gọi giới hạn của nó là điểm P = \lim A_n. Vì kích thước của dãy tam giá tiến dần đến 0 nên ta có P = \lim A_n = \lim B_n = \lim C_n.

Sử dụng tính chất liên tục của ánh xạ $\latex f$, từ việc tất cả các vector  \vec{A_nf(A_n)} đều nằm kẹp giữa \vec{OB}, \vec{OC}, ta suy ra nếu \vec{Pf(P)} \neq 0 thì hướng của nó phải nằm kẹp giữa \vec{OB}, \vec{OC}. Tương tự như vậy, hướng của nó phải nằm kẹp giữa \vec{OC}, \vec{OA}, và cũng phải nằm kẹp giữa \vec{OA}, \vec{OB}. Không thể như vậy, trừ khi \vec{Pf(P)} = 0, có nghĩa là điểm P chính là một điểm cố định của ánh xạ f.

Ta đã chứng minh xong định lý Brouwer.

Quay lại bổ đề Sperner. Có một trò chơi tam tác sau liên quan đến nó:

TriangleGameChia  tam giác ABC thành 36 tam giác con như trong hình vẽ. Ba đỉnh A, B, C của nó tô các màu anh, vàng, đỏ tương ứng. Hai người chơi lần lượt tô các đỉnh còn lại của các tam giác con, mỗi người chọn một đỉnh nào đó và tô khi đến lượt mình, sao cho các đỉnh trên cạnh AB phải là màu xanh hoặc vàng, trên cạnh BC phải là vàng hoặc đỏ, và trên cạnh CA phải là đỏ hoặc xanh. Số điểm của người thứ nhất là số tam giác con có các đỉnh được tô màu xnh-vàng-đỏ theo chiều ngược kim đồng hồ (cùng chiều với các màu tại ABC), còn số điểm của người thứ hai là số tam giác con có các đỉnh được tô màu xanh-vàng-đỏ theo chiều thuận kim đồng hồ. Ai được nhiều điểm hơn thì thắng. Theo bạn thì ai sẽ thắng, vì sao?

Chú ý rằng, theo bổ đề Sperner, tổng số điểm của hai người chơi là số lẻ, nên sẽ có người thắng và người thua chứ không hòa. Nhưng chi tiết hơn nữa, sự chênh lệch điểm giữa hai người có thể là bao nhiêu? Đây là bài tập dành cho bạn đọc :) Hay là đầu tiên cứ thử chơi vài ván xem?

Please follow and like us:

Đố vui kỳ này

Published / by admin

Đây là các câu đố trong Sputnik Newsletter Số 2
Xin mời bạn đọc gửi lời giải về: newsletter@sputnikedu.com
Thời hạn gửi lời giải: Đến hết tháng 02/2017. (Có thể chỉ giải một bài cũng được).
Chú ý ghi rõ họ tên, địa chỉ và số điện thoại liên lạc, lớp học (nếu có).
Những ai có lời giải hay sẽ được tuyên dương trên Newsletter và được tặng thưởng sách Sputnik.

Chú ý: Bạn đọc có thể gửi đến lời giải của những câu đố kỳ trước mà chưa công bố lời giải.

Câu đố 2-1 (Điểm nguyên). Cho một hình ngũ giác lồi ABCDE bất kỳ trên mặt phẳng với một hệ tọa độ cho trước, với các đỉnh đều là điểm nguyên. (Điểm nguyên là điểm có các tọa độ đều là số nguyên). Các đường chéo của hình ngũ giác này cắt nhau tạo thành một hình ngũ giác nhỏ A_1B_1C_1D_1E_1 bên trong. Chứng minh rằng hình ngũ giác A_1B_1C_1D_1E_1 chứa ít nhất một điểm nguyên ở bên trong hoặc trên biên của nó.

Câu đố 2-2 (Che vết bẩn). Trên một mặt bàn phẳng có một vết ố có đường kính 5 cm. (Đường kính của một hình là khoảng cách lớn nhất giữa hai điểm của hình đó). Chứng minh rằng có thể phủ kín vết ố đó bằng một tấm lót tròn có bán kính 3 cm.

Câu đố 2-3 (Bài toán xếp kẹo). Có một hộp kẹo hình lục giác đều mỗi cạnh dài 3 cm, để xếp các viên kẹo hình thoi mỗi cạnh dài 1cm và góc nhọn bằng \pi/3. (Hình thoi này là hợp của hai hình tam giác đều). Dễ thấy có thể xếp vừa khít 27 viên kẹo vào hộp. Bây giờ giả sử các viên kẹo có một trong 3 màu: trắng, xanh, đỏ. Đặt hộp sao cho một cạnh của nó nằm ngang phía dưới. Các viên kẹo màu trắng phải được xếp sao cho đường chéo dài của nó có hướng thẳng đứng từ dưới lên trên, các viên kẹo xanh phải xếp sao cho đường chéo dài của nó có hướng chếch từ trên xuống dưới khi nhìn từ trái sang phải, còn các viên kẹo đỏ phải xếp sao cho đường chéo dài của nó có hướng chếch từ dưới lên trên khi nhìn từ trái sang phải (xem hình vẽ). Dễ thấy có thể xếp như vậy với đúng 9 viên kẹo trắng, 9 viên kẹo xanh và 9 viên kẹo đỏ.

a) Nếu số kẹo trắng khác 9 (và tổng số kẹo vẫn là 27) thì có thể xếp kín hộp sao cho điều kiện phía trên được thỏa mãn không? (Đưa ra ví dụ hoặc giải thích thỏa đáng).

b) Có tổng cộng bao nhiêu cách xếp kẹo khác nhau (với các viên kẹo trắng, xanh, đỏ) thỏa mãn điều kiện trên?

Hexagon

Please follow and like us:

Một chút về lịch sử vec-tơ

Published / by admin

Chương trình Hình học lớp 10 THPT chủ yếu xoay quanh các vec-tơ và phương pháp tọa độ. Trong SGK Hình học 10 hiện tại (2017) có đoạn nói về lịch sử của khái niệm vec-tơ, nhưng đoạn đó có vẻ vừa kỳ bí khó hiểu vừa chưa chính xác về mặt thông tin. Bởi vậy Sputnik viết lại đây về lịch sử các vec-tơ cho các bạn học sinh lớp 10 và tất cả những ai quan tâm.

Từ vec-tơ là từ nhập từ tiếng Pháp vào Việt Nam. Tiếng Pháp viết là vecteur, đọc là véc-tơ, tiếng Anh viết là vector và đọc cũng thành véc-tơ. Phần lớn các thứ tiếng phương Tây khác cũng viết và đọc từ này tương tự như vậy.  Nó có gốc La-tinh, xuất phát từ động từ vehere (mang đi, đưa đi, cưỡi đi). Nghĩa gốc của từ vector chính là “vật/người chở đi, mang đi, cưỡi đi”. Động từ vehere còn sinh ra một từ quen thuộc khác, là từ vehicle (hay vehicule tiếng Pháp), chính là cỗ xe để chở đi.

Với gốc như vậy,  từ vector trong mỗi lĩnh vực khác nhau  có thể có một nghĩa khác nhau. Chẳng hạn trong sinh vật học, nó được dùng với nghĩa “vật truyền cái gì đó”. Ví dụ như các con muỗi được gọi là vector của bệnh sốt rét (malaria).

Trong hình học ngày nay, vec-tơ được hiểu là một đại lượng vừa có hướng vừa có độ lớn. Những đại lượng mà chỉ có độ lớn thôi chứ không có hướng, ví dụ như độ dài, thể tích, khối lượng, v.v., thì được gọi là những đại lượng vô hướng, scalars.  Những đại lượng mà có cả hướng lẫn độ lớn, như là vận tốc, gia tốc, lực, từ trường, v.v. thì được biểu diễn bằng các vec-tơ.

Để vẽ một vec-tơ, người ta có thể vẽ một đoạn thẳng nối từ một điểm A nào đó đến một điểm B nào đó trên mặt phẳng hay trong không gian. Hướng đi từ A đến B chính là hướng của vec-tơ , và độ lớn (đô dài) của đoạn  thẳng AB chính là độ lớn của vec-tơ. Khái niệm đoạn thẳng có hướng (tức là vec-tơ) như vậy được một nhà bác học người Italia tên là Giusto Bellavitis (1803-1880) đề xuất vào giữa thế kỷ 19 (khoảng năm 1846) dưới tên gọi “bipoint”, cùng với  nguyên tắc cộng  vec-tơ AB + BC = AC và nguyên tắc hai vec-tơ bằng nhau nếu 4 điểm tạo thành hình bình hành mà chúng ta biết đến ngày nay.

Cách làm của Bellavitis cho phép nghiên cứu các vec-tơ mà không cần dùng đến hệ tọa độ. Trước đó, nhà toán học Bernard Bolzano (1781-1848)  đã đề xuất từ năm 1804, rồi nhà toán học August Ferdinand Mobius (1790-1868) phát triển vào năm 1827,  một số phép toán là tiền thân của phép tính vec-tơ, với các điểm và các hình mà không cần dùng đến hệ tọa độ.

Tuy nhiên, trong nhiều vấn đề, khi có hệ tọa độ (hay như nói theo ngôn ngữ ngày nay, có cơ sở của không gian vec-tơ) thì vẫn tiện hơn. Có thể biểu diễn và tính toán các vec-tơ (và các thứ khác trong hình học)  thông qua các tọa độ của chúng. Phương pháp tọa độ, và môn hình học giải tích  gắn liền với nó, được Descartes và Fermat đưa ra và nghiên cứu từ nửa đầu thế kỷ 17, và được Newton sử dụng trong công trình của mình. cả ba người này tất nhiên đều đã làm việc với các vec-tơ, chỉ có điều họ chưa gọi chúng là vec-tơ, vì từ vec-tơ trong toán học về sau mới xuất hiện.

Trong số những nhà toán học đầu tiên dùng từ vector/vecteur, có thể kể đến William Hamilton (1731-1803) và Pierre-Simon de Laplace (1749-1827), cho những trường hợp riêng. Hamilton  nghiên cứu các số quaternion, tức là các mở rộng của số phức gồm những 4 thành phần, dạng A + iB +jC +kD với A, B, C, D  là các số thực (trong khi số phức chỉ có 2 thành phần A + iB), và ông ta gọi  iB +jC +kD là thành phần vec-tơ của số quaternion. Còn Laplace thì gọi đường thẳng tưởng tượng nối từ tâm mặt trời tới tâm trái đất là “vec-tơ tia nối” (rayon vecteur, vector radius), gọi tắt là vec-tơ, và dùng nó để mô tả định luật Kepler (vec-tơ này quét những miền có diện tích bằng nhau trong những khoảng thời gian bằng nhau).

Rất nhiều nhà toán học khác của thế kỷ 19, như là Grassmann, Gibbs,  Laguerre, Mourey, v.v. đã đóng góp vào việc phát trển khái niệm vec-tơ trong toán học. Giuseppe Peano (1858-1932) là người đã đưa ra hệ tiên đề cho không gian vec-tơ như chúng ta biết đến ngày nay vào năm 1888. Còn Arthur Cayley  (1821-1895) là người đã đưa ra khái niệm ma trận, vừa là mở rộng của khái niệm vec-tơ, vừa là công cụ để tính toán với các vec-tơ.

Khi ta cố định một hệ tọa độ trong không gian vec-tơ, thì một vec-tơ được hoàn toàn xác định bởi dãy số có sắp thứ tự các tọa độ của nó. Một dãy có xếp thứ tự các số, ví dụ như (1,5,2,0,9), có thể  gọi là một vec-tơ, và đó chính là khái niệm vec-tơ hay dùng trong tin học ngày nay: đối với nhiều ngồn ngữ lập trình thì một vec-tơ chính là một dãy số.

Nói đến vec-tơ, không thể không nói đến đại số tuyến tính, tức là bộ môn toán học về các phép biến đổi tuyến tính và giải các hệ phương trình bậc 1 (gọi là phương trình tuyến tính). Nghiệm của hệ phương trình tất nhiên là một bộ các ẩn số, và đó chính là vec-tơ. Việc giải quyết các hệ phương trình tuyến tính (kiểu vừa gà vừa chó bó lại cho tròn ba mươi sáu con một trăm chân chẵn) đã được con người biết đến từ thời trước công nguyên (ít ra là ở Trung Quốc). Ngay từ thời đó người ta dù chưa biết đến từ vec-tơ, nhưng đã biết tính toán với các vec-tơ!

Nguồn: các tài liệu về lịch sử toán học bằng tiếng Anh và tiếng Pháp có trên internet.

Please follow and like us:

Khoa học vui: Lề trái lề phải

Published / by admin

Dù có là thiên tài chứ không phải … con cừu, thì vẫn phải đi theo lề tạo ra bởi các … con ngựa!

Đây là câu chuyện về lịch sử hình thành nguyên tắc đi xe bên trái hay bên phải ở các nước trên thế giới. Tại thời điểm hiện tại, có xấp xỉ 2/3 số nơi trên thế giới là đi theo nguyên tắc bên phải, còn 1/3 là theo nguyên tắc bên trái. Tuy nhiên, trong lịch sử, không phải lúc nào cũng như vậy. Và các nguyên tắc này không phải do người nào bịa ra, cũng chẳng phải do “Napoleon ép đặt”, mà là do các con ngựa tạo thành!

Đây là một vấn đề nghiêm túc đấy. Nó gắn với những khái niệm như “hội tụ”, “attractor”, “locking”, “quy luật vi vô dẫn đến quy luật vĩ mô”, và có cả một báo cáo tại một hội nghị quốc tế về toán kinh tế xung quanh chuyện này.

Thời đế chế La Mã, có các tuyến đường đá được xây nối rất nhiều các thành phố khác nhau ở châu Âu và vùng bắc Phi quanh Địa Trung Hải. Phương tiện vận tại chủ yếu trên các con đường đó là xe ngựa. Những người đánh xe ngựa thường thuận tay phải, cầm roi ngựa tay phải, quất vào lưng con ngựa từ phải sang trái, trong khi tay trái giữ dây kéo cổ ngựa. Để tránh tai nạn xảy ra do quất roi vào người đi hướng ngược lại, thì các con ngựa phải đi theo lề bên trái, roi quất ra phía ngoài đường. Các nhà khảo cổ, khi phân tích các con đường lã mã còn lại, cũng công nhận lý thuyết đi theo lề trái này là đúng. Ví dụ tại các mỏ đá La Mã, đường phía bên trái lún hơn đường phía bên phải, và phía lún phải là đường đi ra, vì xe nặng hơn nhiều so với khi đi vào.

Sau khi đế chế la mã sụp đổ, nhiều đoạn đường bị dân các thành phố phá đi, vì không muốn dân ngoại lai sử dụng các con đường đó đến quấy rầy. Tuy nhiên, kiểu đi theo lề trái vẫn còn lại, và tồn tại ở Anh cho đến ngày nay.

Cũng từ thời La Mã, khoảng cách giữa các bánh xe cùng trục của cỗ xe ngựa đã được chuẩn hóa để tiện đi lại trên các con đường (tạo thành rãnh cho các bánh xe). Khi nước Anh bắt đầu có đường tầu hỏa, thì lấy luôn khoảng cách La mã đó làm khoảng cách giữa các bánh xe tầu hỏa, tức là độ rộng của đường tầu hỏa.

Ở Pháp, vào thế kỷ 18, các con đường được xây dựng lại, với công nghệ mới tốt hơn so với thời La Mã. Nước Pháp khác nước Anh ở chỗ ít biển và sông ngòi hơn, vận tải phần lớn bằng đường bộ. Bởi vậy việc làm các cỗ xe ngựa sao cho kéo được nhiều đồ là quan trọng. Để kéo được nhiều đồ, thì cần đặt nhiều ngựa trước đầu xe. Nếu đặt 2 con thì người lái xe có thể ngồi trên xe điểu khiển ngựa, đặt 4 con vẫn ngồi trên xe điều khiển được, nhưng khi đặt đến 6 con thành 3 hàng, thì ngồi bên trong xe điều khiển rất vất vả, nên thường có người ngồi lên một trong các con ngựa để điều khiển dễ hơn. Mà phải ngồi con ngựa bên trái, vì ngồi bên phải mà quất sang tít phía bên trái thì khó hơn. Khi ngồi con ngựa bên trái, thì xe ngựa lại phải đi theo lề bên phải mới dễ điều khiển hơn (tương tự như xe ô tô), và bởi vậy khi xuất hiện các xe 6 ngựa, ở Pháp người ta chuyển sang đi theo lề bên phải. Các xe “vận tải nặng tấn” do ngựa kéo này chỉ phổ biến trong khoảng 40 năm, sau đó người ta thay bằng đường sắt, nhưng 40 năm đủ để nguyên tắc đi theo lề phải trở thành luật lệ mọi người tuân theo (khi đa phần đi theo lề phải, thì ai đi theo lề trái sẽ chuốc lấy tai nạn giao thông vào mình).

Cùng với chiến tranh Napoleon, các nước như Ý, Tây Ban Nha, … bị Pháp chiếm, cũng trở nên đi theo lề phải theo Pháp. Không phải ở nơi nào cũng vậy, vì vùng Tây Ban Nha thời đó mà Pháp không chiếm thì vẫn đi theo lề trái, nhiều năm sau mới chuyển sang lề phải. Khi Pháp bị thua, các nước châu Âu khác tự hỏi “không còn Pháp nữa thì ta đổi lại đi theo lề trái như cũ ?”, nhưng do thói quen đi theo lề phải đã ngấm sâu, nên họ không muốn đổi lại thêm lần nữa.

Điều tương tự xảy ra ở Mỹ: vùng Miền Đông nước Mỹ thời đó chủ yếu theo phong tục của Anh, đi theo lề trái. Nhưng những người tiên phong đi khám phá miền Tây thì đi theo lề phải. Lý do là các cỗ xe của họ rất nặng và to, nhiều ngựa kéo, như là ở Pháp, nên người đánh xe cũng ngồi ngựa bên trái và đi theo lề phải cho tiện.

Coach

Canada từng có một ngày hội gọi là Free Lunch Day. Khi Canada muốn thống nhất luật lệ đi lại trong nước vào những năm 1920, chuyển hết thành đi theo lề phải, thì có một vấn đề lớn đặt ra: đấy là có những đàn bò trước nay vẫn đi theo lề trái và đã quen như vậy. Làm sao có thể bắt bò chuyển lề được. Người ta nghĩ ra cách giải quyết, đó là cho dân chúng nghỉ một hôm, và hôm đó đem làm thịt các con bò “lề trái” đi! Do nhiều bò đem ra thịt như vậy, nên thịt bò hôm đó trở nên rẻ vô cùng, và người ta phát không cho mọi người ăn.

Vùng Siberi cận Đông ở Nga là vùng có tỷ lệ tai nạn xe cộ cao nhất nước Nga. Vấn đề là, tuy đi theo lề phải, nhưng phần lớn xe là nhập từ Nhật, và các xe này lại có tay lái bên phải. Lái xe lề phải mà tay lái cũng bên phải, thì kém an toàn hơn so với tay lái bên trái hay là lái theo lề trái. Thế nên thỉnh thoảng Siberi lại đệ đơn xin đổi luật lái xe của vùng đó thành lái lề trái, nhưng chính phủ trung ương không chịu, vì trong cùng một nước nơi lái lề trái nơi lái lề phải cũng dễ đâm nhau.

Nếu không muốn bị đi theo lề trái hay lề phải thì sang châu Phi. Nhiều phố xá bên đó lái xe “đan nhau” một xe chiều này đi kẹp giữa hai xe đi chiều kia, chứ không có lề nào hết :-)

 

Please follow and like us:

Đố vui kỳ này (cho Newsletter Số 2-2017)

Published / by admin

Đây là những câu đố vui sẽ được đăng kèm lời giải trong Sputnik Newsletter Số 2-2017.

Xin mời các bạn tham gia giải đố. Lời giải xin gửi về newsletter@sputnikedu.com, ghi kèm: Họ và tên, địa chỉ, trường học và lớp học (nếu có), số điện thoại liên lạc. Những ai có lời giải hay, được đăng lại trong Newsletter sẽ được tặng quà là sách Sputnik (được chọn sách). Thời hạn cuối cùng để gửi lời giải: hết ngày 25/1/2017 (giờ Việt Nam).

Câu đố 1 (Tetris). Có 25 hình “tetris” dạng “que chữ nhật” 1 \times 4 (một chiều là 1, một chiều là 4). Hỏi có thể xếp chúng lại với nhau để phủ kín một hình vuông 10 \times 10 được không? Nếu có thì chỉ ra ví dụ, nếu không thì giải thích tại sao.

tetris

Câu đố 2 (Chồng phó mát và tháp Hà Nội). a) Bạn có thể đã nghe nói về bài toán Tháp Hà Nội: Có 3 cái cột, và có 8 miếng gỗ tròn có đục lỗ ở giữa được xếp vào cột thứ nhất tạo thành hình một cái tháp, sao cho miếng ở trên nhỏ hơn miếng ở dưới (tựa như các tầng tháp ở các ngôi chùa càng lên cao càng nhỏ dần).  Bây giờ cần dịch chuyển các miếng tròn giữa các cột với nhau, với nguyên tắc miếng to hơn thì không được xếp lên trên miếng thấp hơn, sao cho cuối cùng di chuyển được toàn bộ cái tháp từ cột thứ nhất sang cột thứ ba. Hỏi phải làm thế nào, và di chuyển mất (ít nhất) bao nhiêu nước? (Mỗi nước là di chuyển một tầng tháp từ cột này sang cột khác). Nếu thay số 8 bằng một số n bất kỳ thì sao?

b) Bây giờ chúng ta thay các các cột bằng các cái ghế, và các tầng tháp hình tròn bằng các miếng phó mát tròn kích cỡ tăng dần từ nhỏ đến to, thì bài toán vẫn như vậy. Nhưng bây giờ, thay vì có 3 cái ghế, ta có những 4 cái ghế, và được di chuyển các miếng phó mát giữa các ghế đó (với điều kiện như cũ: phó mát ở mỗi ghế phái xếp thành chồng, và không được để miếng to lên trên miếng nhỏ), thì cần ít nhất là bao nhiêu bước di chuyển để chuyển toàn bộ chồng phó mát gồm 8 miếng từ ghế thứ nhất sang ghế thứ tư?

01Reve

c) Nếu thay vì 8 miếng phó mát và 4 ghế, ta có một chồng 11 miếng phó mát và 4 ghế thì sao? Cần bao nhiêu bước?

31-GameCâu đố 3 (Trò chơi 31 điểm).  Đây là một trò từng được các tay cờ bạc dùng ở các trường đua ngựa hay trên tàu hỏa để moi tiền dân chúng. Tuy nhiên, bản thân nó là một trò chơi khá thú vị, mà các bạn có thể chơi với nhau.

Có 24 quân bài (từ A=1 đến 6, 4 quân cho mỗi số) như trong hình minh họa, và hai người chơi lần lượt đi. Người thứ nhất  úp một quân bài xuống, ví dụ như quân 2, và đếm “hai”. Người chơi thứ 2 úp một quân bài xuống, ví dụ như quân 5, cộng số đó vào số trước được 7, và nói “bảy”. Người thứ nhất lại úp một quân bài xuống, vì dụ như quân 1, và nói “tám” (7+1=8). Cứ như thế, cho đến khi ai nói được số 31 thì thắng. Còn nếu không có được số 31 thì ai vượt số 31 trước là thua.

Câu hỏi ở đây là, để chiến thắng (với giả sử đối phương của bạn là người chơi rất giỏi), bạn phải đi trước hay nhường đối phương đi trước, và dùng chiến thuật như thế nào?

Câu đố 4 (Nhện đi tìm ruồi). Trong một căn phòng trống hình hộp chữ nhật có kích thước 30 ft chiều dài, 12 ft chiều rộng và 12 ft chiều cao,chỉ có một con nhện và một con ruồi. Con nhện đứng ở điểm giữa của một bức tường, cách trần 1 ft, như điểm A trên hình vẽ, và một con ruồi ở bức tường đối diện, cũng ở giữa bức tường và cách sàn nhà 1 ft, như điểm B trong hình vẽ. Đâu là khoảng cách ngắn nhất mà con nhện phải bò để đến được vị trí của con ruồi khi con ruồi đứng yên một chỗ? Con nhện không được phép nhảy xuống  hoặc dùng mạng nhện, mà chỉ được bò. (ft = foot, đơn vị đo độ dài của Anh, bằng 12 inch)

SpiderFly

Câu đố 5 (Kén chồng trong năm 2017). Được biết nữ thần săn bắn Artemis muốn lấy chồng, nữ thần trí tuệ Athena liền thách đố như sau. Xếp 2017 chàng trai tuấn tú nhất của Hy Lạp thành một hàng dài. Athena và Artemis chơi. Đến lượt mỗi người thì loại đi khỏi hàng hoặc là 1 chàng, hoặc là 2 chàng đứng cạnh nhau. (Ví dụ như chàng số 5 đứng cạnh chàng số 6, nhưng số 5 không đứng cạnh số 7 cho dù số 6  đã bị loại đi). Nếu như sau một lượt đi nào đó của Artemis chỉ còn lại đúng 1 chàng, thì Artemis thắng và được lấy chàng đó làm chồng. Athena chơi rất giỏi và không muốn Artemis thắng, nhưng nhường cho Artemis chọn đi trước hoặc đi sau. Hỏi Artemis phải chọn đi trước hay đi sau, và chơi như thế nào để chắc thắng?

Please follow and like us:

Toán học và thuật toán

Published / by admin

(Bài viết của GS. Nguyễn Tiến Dũng từ năm 2014)

Hồi năm 1992, khi tôi đang làm cộng tác viên ở ICTP (Trung tâm vật lý quốc tế, Italia) thì gặp phải một vấn đề không có lời giải như sau: Tôi được CIMPA (trung tâm toán quốc tế của Pháp) mời sang Nice dự một trường hè về đúng chuyên ngành của tôi. Khi đến Lãnh Sự Quán Pháp xin visa (thời đó chưa có khối Shenghen) thì họ giở nguyên tắc đòi phải có công hàm từ ĐSQ của Việt Nam vì hộ chiếu của tôi là hộ chiếu công vụ (thời đó ai đi nước tư bản cũng được cấp hộ chiếu công vụ). Khi đến ĐSQ Việt Nam ở Roma xin công hàm thì họ đòi phải có giấy công tác từ cơ quan chủ quản ở trong nước. Hỏi về trong nước để xin giấy công tác thì không ai cho, vì tôi chẳng thuộc ai quản lý. Thế là tôi trở thành nạn nhân của một bộ các luật lệ mâu thuẫn, không thể xin visa đi Pháp. Nhưng cuối cùng tôi đã tìm được một thuật toán để giải quyết vấn đề tưởng chừng không có lời giải này, và đã sang Pháp dự trường hè CIMPA một cách hoàn toàn hợp pháp. Bạn đọc tò mò muốn biết thuật toán của tôi thế nào, thì xem đến cuối bài sẽ rõ.

Trong cuộc sống và trong công việc, chúng ta hay gặp phải những tình huống lạ, những tình huống mà chúng ta mới gặp lần đầu, chưa biết trước cách giải quyết. Những tình huống đó gây khó khăn cho chúng ta, đòi hỏi chúng ta phải suy nghĩ về những vấn đề lạ. Nhưng đồng thời đó cũng chính là cơ hội cho chúng ta vươn lên và khám phá được những cái mới, còn những công việc lặp đi lặp lại đã có máy móc dần dần làm thay cho con người.

Để giải quyết một vấn đề mà chúng ta gặp phải, chúng ta cần tìm ra một cách giải, hay có thể gọi là một thuật toán để đi đến lời giải. Trong các môn học ở nhà trường, thì môn toán chính là môn tốt nhất để dạy và học về cách tiếp cận thuật toán đối với các vấn đề. Nếu như qua việc học toán mà học sinh hiểu được bản chất các thuật toán quan trọng nhất để áp dụng trong các tình huống khác nhau trong cuộc sống và công việc, thì có thể coi đây là sự thành công của bản thân môn toán trong giáo dục. Rất tiếc rằng, điều này còn rất lâu mới trở thành hiện thực. Vào thời điểm hiện tại, trên thế giới, khía cạnh thuật toán vẫn còn ít được quan tâm tới trong việc dạy và học toán.

Một ví dụ điển hình cho khẳng định trên chính là kỳ thi toán olympic IMO 2014 vừa qua. Đề bài của IMO 2014 không hề rắm rối phức tạp, đặc biệt nếu so với đề thi HSG của Việt Nam. Và chỉ cần kiến thức toán PTCS chứ cũng không cần đến kiên thức PTTH để có thể hiểu đề bài và lời giải của toàn bộ đề thi. Thế nhưng, điểm thi năm nay tương đối thấp so với các năm khác, nên chỉ cần được 29/42 điểm (tức là chỉ cần làm được 4/6 bài và viết được một hai ý gì đó cho 2 bài còn lại) là được huy chương vàng. Một số bài năm nay khó, không phải là vì chúng phức tạp, mà là vì chúng lạ, khiến cho các thí sinh ngỡ ngàng không biết làm thế nào. Tôi sẽ lấy bài số 5 và bài số 6 của IMO 2014 làm ví dụ, chính là hai bài mà đoàn Việt Nam được ít điểm.

Bài số 5 như sau: Có một đống đồng xu có tổng mệnh giá nhỏ hơn hoặc bằng 99,5, sao cho mệnh giá của đồng xu nào cũng có dạng 1/n với n là số tự nhiên (các đồng xu khác nhau có thể có mệnh giá khác nhau). CMR chia được đống đồng xu thành không quá 100 túi sao cho tổng mệnh giá của mỗi túi không vượt quá 1.

Làm sao để tiếp cận một bài toán “lạ hoắc” như trên, với giả sử là bạn không “trúng tủ”, chưa từng làm một bài rất tương tự như thế? Một số phương pháp tiếp cận chung gồm 4 bước sau (lặp di lặp lại nếu cần thiết): quan sát, suy luận, tính toán, kiểm tra. (Bốn bước này không phải do tôi nghĩ ra, mà là đã được đúc kết từ lâu, và được trình bày rất hay trong quyển sách “3 ngày ở nước Tí Hon” cho học sinh cấp 2 mà tôi gần đây có dịch lại sang tiếng Việt, do Sputnik Education đang xuất bản). Trong các bước quan sát và lý luận có việc quan sát các tương quan trong bài toán, làm thử các trường hợp riêng, dựa vào các trường hợp riêng để đưa ra các giả thuyết liên quan rồi xét các giả thuyết đó, biến đổi để đơn giản hóa bài toán, đưa về các dạng bài toán quen thuộc hơn hay dễ giải hơn. Nhiều khi, tổng quát hóa cũng chính là một cách để đơn giản hóa. Nếu là vấn đề lớn, phức tạp, thì phải chia để trị, tức là làm sao chia nó ra thành các bước nhỏ hơn, giải quyết từng bước đó dễ dàng hơn là giải quyết toàn bộ vấn đề.

Có một anh bạn của tôi, là chuyên gia máy tính, có nói với tôi một câu từ cách đây hơn 20 năm mà đến bây giờ tôi vẫn rất tâm đắc: khi được giao một nhiệm vụ lập trình, lập trình viên nào mà ngồi vào hì hụi viết chương trình ngay thì là lập trình viên tồi. Lập trình viên tốt trước khi viết chương trình thì phải quan sát, suy nghĩ đã. Trong toán hay trong nhiều lĩnh vực khác cũng vậy, trước khi “bổ củi” cần quan sát và suy luận để hình dung vấn đề.

Trong trường hợp bài toán số 5 trên, thì có thể quan sát ngay là số 99,5 gần với số 100. Từ đó ta có giả thuyết là nếu thay 99,5 và 100 bởi N -1/2 và N trong đó N là số tự nhiên bất kỳ thì vẫn đúng. Nếu như bài toán chỉ đúng khi N = 100 chứ không đúng với N khác, khi đó thì bài toán chắc là khá phức tạp, nhưng đây là đề thi để học sinh có thể làm trong vòng một vài tiếng, không quá phức tạp được, nên giả thuyết là bài toán đúng với N bất kỳ là giả thuyết tương đối khả dĩ. Việc thay 100 bằng N tùy ý này cho phép chúng ta giả sử là không có đồng xu nào có mệnh giá 1. Thật vậy, nếu có m đồng có mệnh giá 1 thì cho các đồng đó vào m túi, còn lại N = 1 -100 túi và số tiền <= 99,5 – m = N – 1/2.

Một bước lý luận thông dụng quan trọng là: ta cứ thử giải quyết vấn đề một cách “ngây thơ” nhất, để xem nó tắc ở chỗ nào, khó ở chỗ nào. Ở đây có nghĩa là, ta cứ thử bỏ dần tiền vào 100 túi, cho đến bao giờ bỏ được hết hoặc bị tắc không bỏ được nữa thì thôi. Nhưng khi nào thì có thể bị tắc? Đó là khi còn 1 đồng tiền mà cứ bỏ vào túi nào cũng khiến cho mệnh giá của túi đó vượt quá 1. Vì có N túi mà tiền <= N – 1/2, nên có túi có tiền <= (N -1/2)/N = 1 – 1/2N. Điều đó có nghĩa là, nếu có đồng tiền còn lại không bỏ được vào túi nào, thì mệnh giá của nó phải > 1/2N. Cách giải quyết “ngây thơ” này cho ta quan sát sau, làm đơn giản vấn đề: ta có thể giả sử tất cả các đồng tiền có mệnh giá > 1/2N, chứ không cần quan tâm đến các đồng tiền có mệnh giá <= 1/2N nữa (các đồng có mệnh giá <= 1/2N luôn có thể bỏ vào, sau khi đã giải quyết các đồng có mệnh giá > 1/2N)

Một bước lý luận thông dụng quan trọng khác là: làm sao đơn giản hóa bài toán, đưa về những trường hợp đơn giản nhất có thể (gọi là phương pháp reduction trong toán). Ở đây, có thể hiểu là có ít xu thì đơn giản, càng có nhiều xu thì phức tạp hơn. Như vậy, ta có thể tìm cách làm giảm số đồng xu. Có 1 cách hiển nhiên là: nếu có thể đối 2 hay nhiều đồng xu trong đống lấy 1 đồng xu khác (có mệnh giá bằng tổng mệnh giá của các đồng kia), thì ta đơn giản hóa được đống đồng xu: nếu giải được sau khi đã đổi, thì sau khi giải xong ta có thể đổi lại để có lời giải cho đống đồng xu ban đầu. Cứ đổi xu để đơn giản hóa như vậy, ta đưa được bài toán về trường hợp mà không còn đổi xu được nữa.

Đến đây, bài toán đã đơn giản hóa đi đáng kể, vì ta chỉ còn cần xét trường hợp sau: tổng mệnh giá <= N -1/2, không có đồng xu nào có mệnh giá bằng 1, không có một nhóm các đồng xu nào có thể đổi thành 1 đồng xu khác, và không có đồng xu nào có mệnh giá <1/2N. Tất cả các trường hợp còn lại đều suy giản về được trường hợp này. Bây giờ lại quan sát tiếp xem trường hợp cuối cùng này ra sao.
Ta sẽ quan sát thấy là với mọi số tự nhiên k thì không có quá 1 đồng xu có mệnh giá 1/2k và không có quá (2k-2) đồng xu có mệnh giá 1/(2k-1) (vì sao thế?). Từ đó có cách xếp xu vào túi như sau: túi k chứa các đồng xu mệnh giá 1/(2k-1) và 1/2k, với k =1, …, N. (Bạn đọc hãy tự kiểm tra rằng cách này OK).

Tôi viết lời giải cho bài số 5 phía trên khá dài dòng để giải thích quá trình suy nghĩ dẫn đến lời giải mà bản thân tôi sử dụng khi thử làm bài đó, còn tất nhiên khi viết thành lời giải “tròn trịa” thì có thể viết ngắn hơn nhiều. Nhìn từ quan điểm thuật toán, bài số 5 này thật ra khá đơn giản, vì chỉ sau vài bước lược giản hóa dễ thấy là đã đưa về được trường hợp chia được ngay thành các túi. Bạn nào học về lập trình máy tính chắc sẽ nghĩ ngay được cách viết chương trình chia xu dựa trên các bước phía trên. Rất tiếc là đoàn VN chỉ có 2 bạn giả được bài này.

Bài số 6 của IMO 2014 thì còn lạ hơn bài số 5 nữa, và không có bạn VN nào giải được, tuy có một bạn được 3/7 điểm. Các đoàn khác cũng “rụng” gần hết bài này. Đề bài có thể phát biểu như sau: Giả sử có n đường thẳng trên mặt phẳng, sao cho không có 2 đường nào song song và không có 3 đường nào đồng qui. CMR có thể tô ít nhất \sqrt{n} đường bằng màu xanh, sao cho không có miền bị chặn nào trên mặt phẳng có biên toàn là màu xanh.

Con số \sqrt{n} trong đề bài có lẽ là con số gây hoang mang, bởi thoạt nhìn chẳng biết nó từ đâu ra. Số các điểm cắt nhau thì là n(n-1)/2, còn số các miền bị chặn thì là (n-1)(n-2)/2, tức là đều so được với n^2, chứ chẳng có cái gì trên mặt phẳng có số lượng dạng \sqrt{n}. Những hoang mang như vậy có thể ảnh hưởng xấu đến tâm lý, khiến việc tìm lời giải trở nên khó khăn hơn. Bỏ qua các hoang mang, ta cứ thử làm một thuật toán “ngây thơ” để giải quyết vấn đề tô màu, xem nó sẽ gặp khó khăn bế tắc ở đâu. Thuật toán ngây thơ đó là: đầu tiên ta tô một đường bất kỳ màu xanh. Sau đó cứ còn tô được thêm đường màu xanh (sao cho không có miền bị chặn nào trên mặt phẳng có biên toàn là màu xanh) thì tô tiếp, còn đến lúc không tô được thêm nữa thì dừng lại. Gọi số đường tô được lúc dừng lại là k. Nếu thuật toán đơn giản này mà OK, thì tức là ta có k^2 >= n. Như vậy, nếu ta chứng minh dược k^2 >= n thì OK.

Một phương pháp chứng minh thông dụng là dùng phản chứng. Tức là ta sẽ chứng minh rằng, nếu đã tô được k đường, và n > k2, thì còn tô thêm được đường nữa. Để chứng minh điều đó, chỉ cần CMR số đường cấm không vượt quá k^2 – k = k(k-1). Đường cấm tức là đường mà nếu tô nó thì sẽ có miền bị chặn với biên toàn màu xanh. Bây giờ lại vận dụng nhận xét sau: số điểm nút xanh (= giao điểm của các đường xanh) là k(k-1)/2, nên nếu ta làm sao thiết lập quan hệ được giữa các đường cấm và các nút xanh, kiểu “đương cấm nào cũng cho bởi nút xanh, và mỗi nút xanh không cho quá 2 đường xanh” thì là OK. Ý tưởng là như vậy. Đi vào cụ thể hơn, thì quan hệ sẽ là: mỗi đường cấm ứng với ít nhất 2 đoạn cấm (1 đoạn cấm là một đoạn màu xanh đi từ 1 nút xanh đến đường cấm), còn từ mỗi nút xanh chỉ đi ra được nhiều nhất là 4 đoạn cấm thôi. Và lời giải đến đây gần như là kết thúc (bạn đọc có thể tự viết lại lời giải hoàn chỉnh, sẽ không quá 1 trang giấy).

Đấy là chuyện thi toán quốc tế. Quay lại chuyện dạy toán và học toán “bình thường”. Năm nay, tôi có dạy toán cho một lớp đại học năm thứ nhất chuyên ngành tin học, thay cho một đồng nghiệp nghỉ đẻ. Một số bạn sinh viên phàn nàn với tôi là chương trình toán chán quá, chẳng thấy liên quan gì đến tin học. Mà đúng thế thật, tôi đọc chương trình cũng thấy chán. Nhưng tôi chỉ là “lính đánh thuê” chứ không soạn chương trình nên không thay đổi được nó.
Cái mà tôi cố gắng làm để “bù trừ” lại là giải thích thêm cho các sinh viên những khái niệm mà họ học chính là các thuật toán có ý nghĩa ra sao. Ví dụ như, công thức nội suy Lagrange chính là thuật toán để vẽ đường cong “đơn giản nhất, đẹp mắt nhất” đi qua một số điểm cho trước, và khi người ta thiết kế ô tô, tàu bay thì thay vì vẽ toàn bộ các điểm người ta chỉ cần vẽ ít điểm thôi rồi nội suy ra các điểm còn lại theo kiểu công thức đó. Hay như chuỗi Taylor để làm gì? Nó cũng chính là thuật toán cho phép chúng ta tính xấp xỉ một cách rất chính xác các giá trị của các hàm phức tạp, v.v. Ví dụ như, ta có thể tính nhẩm bằng tay các số như e, sin(1), v.v. với độ chính xác rất cao mà không cần máy tính (máy tính nó cũng dùng các thuật toán như ta tính nhẩm thôi), v.v. Khi học sinh sinh viên (đặc biệt là sinh viên tin học) được giải thích ý nghĩa thuật toán của các khái niệm toán học, thì họ cũng phấn khởi lên nhiều. Đối với sinh viên sinh vật, hóa học, v.v. thì có thể cần dạy hơi khác đi, với nhiều minh họa ứng dụng toán học trong ngành của họ hơn, ví dụ như tại sao lại dùng hàm lũy thừa khi khảo sát dân số, v.v. Cuối cùng thì toán học vẫn là một tổng hợp các công cụ để mô hình hóa và các thuật toán đề giải quyết các vấn đề nảy sinh trong mọi lĩnh vực, chứ không phải là một mớ khái niệm từ trên trời rơi xuống và xa vời thực tế.

Thế còn thuật toán để giải quyết vấn đề visa thì sao? Với hộ chiếu công vụ, thì tôi không thể đi Pháp. Như vậy tôi phải thay hộ chiếu. Không ai tự nhiên lại cho thay hộ chiếu, như vậy tôi phải mất hộ chiếu. Thế là một hôm đẹp trời, tôi ra đồn cảnh sát Italia báo mất ví có hộ chiếu trong đó. (Không ai phải chứng minh chuyện mình bị móc mất hộ chiếu với cảnh sát, vì làm sao có thể chứng minh được điều đó, chỉ chứng minh được là mình có hộ chiếu nếu chưa mất thôi). Với chứng nhận mất hộ chiếu của cảnh sát, tôi lên ĐSQ VN làm hộ chiếu khác, và ở đó, khác với ở VN, người ta chỉ cấp hộ chiếu phổ thông chứ không cấp hộ chiếu công vụ cho loại không phải cán bộ nhà nước như tôi :)

Please follow and like us:

Tất cả tại Ên-Trô-Pỳ

Published / by admin

– Lịch sử đã cho VN một sứ mệnh anh hùng: hết đuổi giặc Tàu, giặc Pháp, đến giặc Mỹ, rồi lại đuổi gì tiếp ?

– Tiên sư cha thằng lịch sử, toàn bắt VN làm những việc khó !

Tay sai của thằng lịch sử

Thằng lịch sử đúng là oái oăm, làm khổ VN. Nhưng thằng lịch sử cũng không làm được vậy, nếu không có một quỉ sứ tay sai đắc lực của nó mang tên Ên Trô Pỳ. Nghe có vẻ như tên Tàu, nhưng thực ra đây là tên Tây. Thằng quỉ sứ này luôn làm những việc phá phách, nhưng nó ẩn danh cho đến tận năm 1865 mới bị một lão người Đức tên là Clausius phát giác ra, và gọi nó là thằng Entropy, có nghĩa là thằng xáo trộn hỗn độn. Theo gốc Hy Lạp, “tropy” (τροπή ), có nghĩa là thay đổi, chuyển hướng, còn “en” có nghĩa là “bên trong”. Khi sang tiếng Việt thì Entropy trở thành Ên Trô Pỳ (chữ trô đọc chờ nặng). Số là, có lần tôi gọi taxi để đi đến Ciputra. Tôi nói Ci-pu-t-ra, anh lái taxi mãi mới hiểu ra là Ci-pu-tra, và chê tôi nhà quê không biết nói tiếng Tây. Từ đó tôi cứ nói Ci-pu-tra, ai cũng hiểu, và entropy thì gọi là Ên Trô Pỳ cho chuẩn.

Ở đâu có lộn xộn, là ở đó có En Trô Pỳ hoành hành. Không chỉ ở những trận đánh nhau chết cả triệu người, mà ngay trong căn nhà nhỏ của bạn, En Trô Pỳ cũng ra tay quấy phá. Bạn có biết vì sao phòng của bạn cứ dọn sạch được 1-2 hôm lại bừa đâu vào đấy không, vì sao hàng xóm hay đồng nghiệp thỉnh thoảng lại cãi nhau chí chóe không ? Chính là tại bởi Ên Trô Pỳ!

Ên Trô Pỳ luồn lách mọi nơi, ảnh hưởng đến mọi vật, một cách cộng tính: Ên Trô Pỳ (độ lộn xộn) của một tổng thể các vật (các “systems”), thì bằng tổng của các Ên Trô Pỳ của các vật. Một đặc điểm nhận biết thằng En Trô Pỳ là, nó là thằng ăn hại năng lượng. Ví dụ, khi xe ô tô đi trên đường phẳng nằm ngang vẫn tốn xăng, chính là vì thằng Entropy ăn mất năng lượng do động cơ chạy xăng tao ra, qua các thứ ma sát. Cụ Newton đã nói năng lượng luôn bảo toàn, không bị mất đi. Thế nhưng, năng lượng dự trữ trong xăng là năng lưỡng hữu ích, có thể dùng để làm việc này việc nọ, còn năng lượng khi đã bị thằng En Trô Py ăn vào, thì trở thành năng lượng vô dụng, ta khó có thể đòi lại để dùng đươc nữa! Tuy nhiên, bản thân Ên Trô Pỳ không phải là năng lượng, nó chỉ là thằng phá phách biến năng lượng hữu dung thành vô dụng trong quá trình béo lên của nó thôi. Lão Clausius cũng biết điều đó; đầu tiên lão định tìm từ gì tương tự như năng lượng để đặt tên cho nó, trước khi nghĩ ra từ Entropy.

Càng nóng càng khó béo lên

Clausius nhận thấy rằng, chỗ nào càng nóng thì entropy càng khó béo lên, tức là càng cần bơm vào nhiều năng lượng (ở dạng nhiệt năng) để nó béo lên. Nói một cách chính xác hơn:

dS = \frac{\delta q}{ T }

trong đó S là độ lớn của entropy (của một hệ nào đó), dS là sự thay đổi độ lớn của Ên Trô Pỳ, T là nhiệt độ (tuyệt đối), còn {\delta q} là độ thay đổi nhiệt năng của hệ đó. Nói cách khác, nếu ta cho thêm một lượng nhiệt năng \delta q vào một vật nào đó đang ở nhiệt độ T, thì entropy của nó sẽ tăng lên một lượng là \frac{\delta q}{ T } . Ngược lại, nếu ta hút đi một lượng nhiệt năng là \delta q, thì entropy của vật cũng giảm đi một lượng là \frac{\delta q}{ T } .

Công thức trên cũng cho thấy, đơn vị đo của entropy là đơn vị năng lượng chia cho nhiệt độ. Người ta thường viết đơn vị của entropy là J/K, trong đó J là Joule là đơn vị năng lượng dùng để đo nhiệt năng, con K là đơn vị độ Kelvin để đo nhiệt độ.

Theo công thức phía trên, để giảm entropy của một vật, cần rút bớt nhiệt ra. Nhưng nhiệt rút ra đó đi vào chỗ nào ? Theo một định luật vật lý (gọi là định luật nhiệt động học thứ hai), chỗ nhận được nhiệt đó phải lạnh hơn là vật ban đầu nếu ta không muốn tiêu thêm năng lượng vào đó. (Khi Bác Hồ ôm cục gạch nóng, thì là gạch sưởi cho Bác chứ không phải Bác sưởi cho gạch). Chẳng hạn chỗ đó có nhiệt độ T_1 < T. Khi đó phần được truyền nhiệt sang sẽ có entropy S_1 tăng lên một lượng bằng

dS_1 = \frac{\delta q}{ T_1 }

trong đó \delta q là lượng nhiệt chuyển từ vật nóng sang vật lạnh. Vật nóng thì có entropy giảm đi một lượng bằng dS = - \frac{\delta q}{ T } . Công lại ta có

dS + dS_1 = \frac{\delta q}{ T_1 } - \frac{\delta q}{ T} > 0

(vì T_1 < T_0\delta q > 0). Có nghĩa là entropy của tổng hai vật tăng lên! Đây chính là định luật:

Ên Trô Pỳ làm gì cũng đúng

Theo định luật này, thì entropy của thế giới không thể giảm đi, mà chỉ có thể tăng lên theo thời gian. Nếu entropy ở chỗ nào đó giảm đi, thì ở các chỗ xung quanh sẽ phải tăng lên một lượng nhiều hơn lượng giảm đi đó để bù lại, và tính tổng cộng thì vẫn là tăng lên. Định luật Ên Trô Pỳ làm gì cũng đúng chẳng qua là một cách phát biểu khác của định luật nhiệt động học thứ hai.

Chính vì sự tăng lên không ngừng theo thời gian của entropy, nên thời gian không đảo nghịch được, và không thể có các chuyến “du hành vũ trụ” đi ngược lại thời gian được! Giá ta có thể đi về thế kỷ 17 tán phét với cụ Newton một lúc rồi quay lại thế kỷ 21 thì vui biết mấy. Nhưng quỉ sứ entropy không cho ta làm điều đó!

Có thể nói, thằng entropy ngày càng béo ra bằng cách ăn vào năng lượng hữu ích biến thành năng lượng vô ích để rồi làm loạn thế giới, nhưng ta không có cách nào “chọc mỡ” nó cả!

Nếu đến một lúc nào đó, thằng En Trô Pỳ ăn hết năng lượng của thế giới này thì sao? Lúc đó thì nó đạt đến mức béo nhất có thể (gọi là maximal entropy). Nhưng lúc đó cũng sẽ không còn năng lượng có thể sử dụng được nữa, và đó sẽ là ngày tận thế của thế giới. Mấy ông hủ lý thì gọi đó là ngày của cái chết nhiệt (heat death hay thermal death). Nhưng ngày đó nếu có xảy ra, cũng còn phải hàng ty tỷ năm nữa, ta chưa vội gì mà phải “mặt ủ mày chau”!

Một mình chống lại Ên Trô Pỳ

Tuy Ên Trô Pỳ làm gì cũng đúng, nhưng thỉnh thoảng vẫn có các anh hùng hảo hớn dám ra đương đầu với nó. Một trong các anh hùng hảo hớn đó là thần đồng Ludwig Boltzmann (1844-1906), một nhà toán học mà khi 25 tuổi đã là giáo sư (full professor) ở nước Áo. Từ những năm 1870, Boltzmann đã tìm cách vạch mặt bản chất chân tướng của thằng Ên Trô Pỳ bằng cơ học thống kê, và đi đến công thức sau:

S = k. \ln W

trong đó k = 1.38 \times 10^{-23} J/K là một hằng số (gọi là hằng số Boltzmann), còn W là số trạng thái vi mô (microstate) khác nhau mà nhìn vào hệ ta không phân biệt được (tức là cho cùng một trạng thái vĩ mô của vật). Trong suốt hơn 30 năm từ khi Boltzmann nghĩ ra công thức trên, thì bị thằng Ên Trô Pỳ trả thù bằng cách xúi giục các nhà khoa học lớn khác (như Planck, Poincaré) chế diễu công thức này, coi nó lẩm cẩm, khiến cho Boltmann uất chí đến mức tự tử ở Duino (Italia) vào năm 1906.

Ngày nay các nhà hủ lý đều chấp nhận công thức trên của Boltzmann, và trên bia mộ của ông ta có khắc nó.

Theo công thức Boltzmann, thì càng nhiều khả năng (nhiều microstate có thể) càng lắm hỗn loạn (entropy càng cao). Khi ta ghép 2 hệ với nhau, thì số khả năng của tổng bằng tích của các số khả năng, trong khi entropy của tổng chỉ là tổng của các entropy. Bởi vậy để chuyển từ số khả năng sang entropy phải lấy log.

Làm sao để tính entropy ?

Đây có vẻ là vấn đề rất khó khăn. Đối với các vật đơn giản, ví dụ nhưng một lượng nguyên chất của một loại phân tử nào đó, thì có thể dùng công thức của Clausius để mà tính: Khi nhiệt độ bằng 0K (= – 273 độ C), thì các phân tử cũng đứng im không có thể nhúc nhích gì hết, bởi vậy coi như là “có trật tự”, và entropy của nguyên chất khi nhiệt độ bằng 0 (độ Kelvin) được coi là bằng 0. (Đây là định luật thứ 3 của nhiệt động học). Từ mức nhiệt độ sát 0, ta nhồi nhiệt năng từng ít một vào vào để nhiệt độ tăng lên dần đến mức ta muốn, và trong quá trình nhồi đó đo nhiệt độ, rồi lấy các lượng nhiệt năng cho vào chia cho nhiệt độ để ra các độ tăng của entropy, rồi cộng chúng lại với nhau. (Nói một cách toán học hơn, thì là lấy tích phân của dạng vi phân \delta q / T). Ví dụ, người ta tính ra được rằng 1kg nước (H2O) ở nhiệt độ 25 độ C có entropy bằng 367 J/K [edit: đây là con số tương đối tính từ 1 mốc nào đó, còn con số tuyệt đối, theo GS Đàm Thanh Sơn, là những 3890 J/K]. Tất nhiên, đây chỉ là một trong các cách tính, và các hủ lý có thể còn sáng tạo ra nhiều cách khác. (Xem chẳng hạn: R.K. Rajput, A textbook of engineering thermodynamics).

Tại sao tủ lạnh lại lạnh ?

Bình thường, theo định luật thứ hai của nhiệt học, nhiệt phải truyền từ chỗ nóng sang chỗ lạnh (và trong quá trình truyền nhiệt đó thì entropy tăng lên). Thế nhưng tủ lạnh mà máy điều hòa nhiệt độ có vẻ làm ngược lại: tủ lạnh hút nhiệt bên trong tủ thổi ra ngoài, làm bên trong thì lạnh đi, còn bên ngoài nóng lên. Có sự mâu thuẫn nào ở đây không ? Tất nhiên là không, vì thằng Ên Trô Pỳ làm gì cũng đúng, đời nào chịu thua thiệt. Nó chỉ cho phép tủ lạnh hay máy điều hòa làm lạnh với điều kiện là phải xì cho nó năng lượng: khi máy điều hòa làm giảm nhiệt năng trong phòng, thì làm tăng nhiệt năng ngoài trời một lượng nhiều hơn là lượng giảm đi trong phòng, và độ chênh lệch giữa hai lượng chính là lượng điện năng mà máy tiêu thụ. Nhiệt độ ngoài trời mà càng cao hơn bên trong nhà, thì càng phải cúng nhiều điện năng cho thằng Ên Trô Py nó mới cho phép thổi nhiệt ngược từ chỗ lạnh trong nhà ra chỗ nóng ngoài trời ! Điện có thể được dùng để hút nhiệt qua hiệu ứng Peltier, hoặc qua cách nén khí bằng compressor rồi sử dụng hiệu hứng thay đổi áp suất dẫn đến thay đổi nhiệt sau đó, hoặc là các cách khác, nhưng kiểu gì thì cũng phải nộp cống cho thằng Ên Trô Pỳ.

Những kẻ “ăn theo”

Như người ta thường nói “không chống được chúng, thì hãy theo chúng”. Có những kẻ đã khôn ngoan đi ăn theo, mượn vía Ên Trô Pỳ. Đầu tiên có thể kể đến Claude Shannon (1916-2001), cha đẻ của lý thuyết thông tin. Khi Shannon nghĩ ra công thức đo lượng thông tin (hay là lượng thông tin bị mất mát đi khi truyền tin) vào quãng những năm 1944-1948, định gọi nó là “độ bất xác định”, nhưng John von Neumann đã khuyên nên đặt tên nó là entropy, với hai lý do: một là công thức của Shannon trông giống y chang công thức entropy trong vật lý thống kê (như kiểu công thức của Boltzmann), và hai là “không ai thực sự biết entropy là gì, nên cậu gọi như vậy thì sẽ lợi thế khi tranh luận!”.

Nếu không gian xác suất chia làm n tập con với các xác suất p_1, \hdots, p_n tương ứng (\sum p_i = 1), thì entropy của phép chia này bằng

- \sum p_i \log_2 p_i

Hiểu công thức trên như thế nào ? Để cho đơn giản, hình dung là chia đều thành 8 phần, mỗi phần xác suất 1/8, khi đó entropy bằng 3. Số 3 ở đây hiểu là “3 bit thông tin”: Xét 8 số nhị phân có 3 chữ số: 000, 001, 010, 011, 100, 101, 110, 111. Giả sử cần lấy ra 1 số trong 8 số đó. Để biết là cần lấy ra số nào, thì cần có 3 bit thông tin: chữ số đầu là gì, 0 hay 1, là 1 bit thông tin, chữ số thứ 2 cũng ứng với 1 bit, và chữ số thứ 3 cũng 1 bit.

Sau khi Shannon “ăn theo” thì tiếp ngay đến Kolmogorov, với định nghĩa “metric entropy” cho các hệ động lực, vào đầu những năm 1950. Tiếp theo đó là một loạt các nhà toán học khác như Sinai, Adler, Dinaburg, Bowen, … nghiên cứu metric entropy rồi topological entropy cho các hệ động lực, rồi tiếp đến Ghys, Walczak, Langevin xét entropy hình học cho các phân thới, v.v. Đấy mới chỉ là tụi “làm toán ăn theo” không kể các hội vật lý, tin học, v.v. khác ăn theo entropy.

Kẻ thừa giấy vẽ con voi này cũng đang đi ăn theo với “entropy của các cấu trúc hình học”, mà trường hợp riêng là các đa tạp Poisson, hay các singular distributions nào đó. Việc nó liên quan đến quỉ sử Ên Trô Pỳ (trong tự nhiên) thế nào thì chưa hề rõ.

Trong kinh tế, những kẻ ăn theo cũng đưa vào khái niệm corporate entropy, để chỉ sự rắm rối của các doanh nghiệp dẫn đến giảm hiệu quả lao động.

Entropy của thức ăn

Một lần kẻ thừa giấy vẽ voi này có được hầu chuyện Alain Connes trong một bữa đánh chén. Câu chuyện huyên thuyên một lúc không hiểu sao lại nhảy sang entropy. Connes say sưa với lý thuyết entropy về thức ăn của mình: thức ăn vào bụng thì kiểu gì cũng sẽ phải đạt mức entropy nào đó. Hãy để cho dạ dày và ruột của ta làm việc đó (tăng entropy của thức ăn lên, là một cách làm giảm entropy của bản thân chúng ta, giúp ta khỏe lên). Đừng ăn thức ăn có entropy cao sẵn (khi đó cơ thể người còn ít việc để làm, không làm giảm entropy của người đi được). Hẵy học tập người Nhật: đồ ăn của họ thường ở dạng entropy thấp (ví dụ như ăn cá sống). Đừng có ăn nhiều đồ đã băm nát trộn lẫn xào xáo nhiều … Cũng có thể đồ ăn có entropy thấp là một trong các bí quyết sống lâu của người Nhật thật.

Entropy âm ?

Trong lúc Connes kể chuyện về entropy của thức ăn, thì kẻ này có liều mình hỏi một câu provocative: thế entropy có âm được không ? Connes liền kể chuyện Boltzmann bị người đời không hiểu dẫn đến chán đời tự tử ra sao.

Tất nhiên theo các công thức của Boltzmann hay Shannon hay này nọ, thì entropy không thể âm. Thế nhưng câu hỏi “triết học” vì sao entropy lại phải dương không hẳn là câu hỏi dở hơi, đặc biệt khi ta coi mọi thứ chỉ là tương đối. Năng lượng có thể âm thoải mái không sao, vì nếu lấy hàm năng lượng trừ đi một hằng số, thì không hề ảnh hưởng đến phương trình chuyển động. (Hay như Dirac nghĩ ra các phản hạt xả láng, âm có làm sao đâu ?!) Entropy cũng vậy, nếu trừ đi một hằng số thì có lẽ chẳng ảnh hưởng gì hết đến các lý thuyết, vì cái người ta đo thực ra là độ thay đổi entropy, chứ không phải entropy tuyệt đối.

Kẻ vẽ voi này đi tìm hiều về “entropy âm”, thì phát hiện ra có khái niệm đó thật! Chính Schroedinger đưa ra khái niệm “negative entropy”, hay còn gọi là negentropy, trong quyển sách What is life. Thực ra thì cũng không có gì dám “báng bổ” quỉ sử Ên Trô Pỳ về bản chất. Có thể coi entropy + negentropy là hằng số, tức là negentropy là phần “dư ra” chưa bị entropy chén mất, và phần này ứng với phần năng lượng còn dùng được. Sự sống có được là nhờ có negentropy.

Entropy của các cấu trúc tổ chức xã hội ?

Một câu hỏi thú vị đặt ra với các nhà xã hội học: các mô hình, cơ chế xã hội nào tạo entropy cao nhất, làm tăng entropy nhanh nhất ?

Câu hỏi này rất khó, kẻ vẽ voi không dám vẽ bậy ở đây. Nhưng trộm nghĩ rằng các cơ chế “cào bằng”, “xin cho”, tham nhũng v.v. ắt hẳn dẫn đến entropy cao ?!

(Nguyễn Tiến Dũng)

Please follow and like us:

Tô pô là gì và có ích gì?

Published / by admin

(Nguyễn Tiến Dũng)

Lần đầu tiên tôi được tiếp xúc với tô-pô là qua quyển sách “Tô pô đại cương” (General Topology) của Kelley do GS Đỗ Đức Thái cho mượn từ năm 1986 khi còn ở Việt Nam. Thời xa xưa đó, tất nhiên tôi đọc cũng có hiểu phần lớn các định lý, nhưng là chỉ hiểu một cách rất máy móc, chứ không hiểu ý nghĩa của chúng, sao lại cần chúng để làm cái quái gì (và cũng chẳng có ai dạy cho). Mãi sau này tôi mới từ từ hiểu dần về ý nghĩa của tô-pô. Nhưng khi dạy học lần này (ở trường Shanghai Jiao Tong University), tôi muốn các sinh viên cảm thấy được ý nghĩa ngay từ đầu, để khả năng ứng dụng được cao hơn.

Xuất phát điểm của môn tô-pô là quãng cuối thế kỷ 19 – đầu thế kỷ 20, với những tên tuổi như Poincaré, Cantor, Klein, Mobius, Brouwer, Urysohn, v.v. Poincaré gọi nó là “analysis situs”, tức là “giải tích theo vùng miền”. Nói một cách nôm na, những tính chất tô-pô của các vật thể (hay không gian) được xem xét chính là những tính chất hình học “rough, robust” của nó, không bị mất khi ta thay đổi (biến dạng, bóp méo) nó một cách “liên tục” mà không “làm gãy, khoét đi hay gắn gì vào ở chỗ nào”. Ví dụ như cái chun buộc là một vòng tròn – nhưng đó là một vòng tròn tô-pô, dù xếp méo mó hay kéo dài nó ra đến mấy thì về mặt tô-pô nó vẫn “tròn”, tức là vẫn là một “đường khép kín không có điểm đầu điểm đuôi”, nhưng nếu làm đứt nó thì nó không còn là vòng tròn tô-pô nữa.

Để nhận biết xem các hình (các không gian, đa tạp, …) giống nhau hay khác nhau về mặt tô-pô, người ta phải nghĩ ra các tính chất đặc trưng của chúng (tính compact, tính đầyy đủ, tính tách được, tính liên thông, số chiều, các chỉ số, các nhóm đồng luân đồng điều v.v.), và đại số chính là công cụ quan trọng để nghiên cứu các tính chất đó, nên mới xuất hiện ngành “tô-pô đại số”. Ví dụ như cái bánh có 1 lỗ thì giống cái cốc có 1 quai nhưng khác cái bánh có 2 lỗ về mặt tô-pô, và số “lỗ” ở đây chính là một loại chỉ số đặc trưng để mà phân biệt. Thế tô-pô có ích gì? Nhiều lắm, tôi cũngchỉ biết một vài trong số đó thôi, ở đây xin kể qua.

Thứ nhất là ứng dụng trong giải tích hàm, để mà khảo sát nghiệm của các loại phương trình vi tích phân và đạo hàm riêng v.v. Nhiều khái niệm tô-pô (như là to pô yếu, tô pô mạnh, hội tụ yếu, completion, v.v.) được phát triển chính là vì nhu cầu của việc nghiên cứu các hàm số, và cũng chính vì thế môn tô-pô đại cương hay dược dạy chung với môn giải tích hàm ở đại học.

Thứ hai là trong mô tả toán học nói chung của hình học và của thế giới. Thế giới cần được mô tả bằng hình học, và từ khi có ngôn ngữ tô-pô thì người ta mới mô tả nó dễ dàng hơn chứ trước kia rất lúng túng và nhiều khi tối nghĩa.

Thứ ba là trong vật lý và hóa học. Ba nhà vật lý được giải Nobel 2016 chính là nhờ các công trình về “chuyển pha tô-pô”: các pha khác nhau của vật chất (ví dụ giữa pha cách điện và pha dẫn điện và pha siêu dẫn) khác nhau về mặt tô-pô như thế nào, và điều này chắc chắn có nhiều ứng dụng trong công nghệ vật liệu mới. Trước đó, người ta cũng đã biết hiện tượng “chirality” (bên trái bên phải khác nhau) trong hóa học của các phân tử chính là hiện tượng tô-pô.

Thứ tư là trong lý thuyết trò chơi chiến lược trong các vấn đề chính trị xã hội cũng có sự xuất hiện của tô-pô, ví nhụ như khi người ta nghiên cứu các ổn định Nash, đưa về lý thuyết diểm kỳ dị kiểu như thuyết Morse.

Thứ năm là trong tin học. Ví dụ như “domain theory” (một lý thuyết về mạng thông tin) dùng rất nhiều khái niệm tô-pô …

Và còn nhiều thứ khác nữa …

Một điều thú vị nữa là tô-pô và tổ hợp là hai ngành toán học tưởng chừng rất xa cách nhau nhưng thực rất gần gũi (vì toán học là một thể thống nhất!). Ví dụ như định lý Brouwer về điểm bất động thể phát biểu lại như một bài toán tổ hợp và chứng minh bằng phương pháp tổ hợp :)
Please follow and like us:

Bạn có thích nội dung này không? Hãy chia sẻ!