Bài toán cầu hôn và giải pháp cho Bộ Giáo dục

Tại ngày hội “Một ngày với Toán học” diễn ra tại Viện Toán học hôm 10/10, GS. Hà Huy Khoái đã có bài giảng “Toán học với thị trường, tuyển sinh và gả chồng dựng vợ” trước đông đảo người yêu toán. 

Bài toán gả chồng dựng vợ mà ông còn gọi là “bài toán cầu hôn” chính là thuật toán “chấp nhận trì hoãn” của Gale Shapley mà ứng dụng của GS. Alvin Roth vào lĩnh vực kinh tế đã giành giải Nobel Kinh tế năm 2012.

Thuật toán Gale Shapley được GS. Hà Huy Khoái giải thích bằng bài toán cầu hôn như sau: Có 4 chàng trai là Adam, Bob, Charlie, Don và 3 cô gái là Mary, Jane và Kate. 4 chàng trai có cảm tình với 3 cô gái theo một thứ tự ưu tiên nhất định và ngược lại 3 cô gái cũng có cảm tình với 4 chàng trai theo một thứ tự ưu tiên khác.

Và thuật toán G. Shapley sẽ giải quyết vấn đề này bằng cách đưa ra phương án tốt nhất cho 4 chàng trai (hoặc 3 cô gái) dựa trên thứ tự ưu tiên của họ.

Giả sử thứ tự ưu tiên của 4 chàng trai như sau:

Giả sử thứ tự ưu tiên của 3 cô gái như sau:

Giả sử bài toán này sẽ ưu tiên quyền lợi của 4 chàng trai trước, nghĩa là để các chàng trai đưa ra lựa chọn của mình trước (nếu dựa trên ưu tiên quyền lợi của các cô gái, kết quả sẽ khác đôi chút).

Ngày đầu tiên, 4 chàng trai đi cầu hôn ưu tiên số 1 của mình, nghĩa là Bob cầu hôn Jane, và cả 3 chàng trai Adam, Charlie và Don đều cầu hôn Mary.

Mary vì có tới 3 sự lựa chọn nên sẽ chọn ưu tiên tốt nhất của mình trong số 3 chàng trai, đó là Don (ưu tiên số 1 của Mary).

Jane vì chỉ có Bob cầu hôn nên sẽ chọn Bob tạm thời (chấp nhận tạm thời). Kate chưa có ai cầu hôn trong ngày đầu tiên.

Sang ngày thứ hai, vì Mary đã chọn Don nên Adam và Charlie đi cầu hôn ưu tiên số 2 của mình. Adam cầu hôn Jane và Charlie cầu hôn Kate. Vì ưu tiên số 1 của Jane là Adam nên Jane chấp nhận Adam, loại Bob. Kate chỉ có duy nhất Charlie cầu hôn nên tạm thời chấp nhận Charlie.

Ngày thứ ba, chỉ còn Bob chưa được ai chấp nhận, Bob cầu hôn Kate. Bob là ưu tiên số 1 của Kate, trong khi Charlie là ưu tiên số 3 nên Kate chọn Bob, loại Charlie.

Như vậy, theo cách nói vui của GS. Hà Huy Khoái, cuối cùng Charlie “ế vợ”.

Quá trình “cầu hôn” và “chọn lựa” này có thể được biểu diễn bằng bảng sau:

Bài toán cầu hôn không có thực trong cuộc sống thực tiễn nhưng cách giải quyết vấn đề của thuật toán này có thể áp dụng ở nhiều lĩnh vực. Theo GS. Hà Huy Khoái, giai đoạn 1945-1951, thị trường tuyển dụng bác sĩ ở Mỹ bùng nổ do nhu cầu bác sĩ ở các bệnh viện quá lớn. Hậu quả của việc các bác sĩ tự ứng tuyển và các bệnh viện tự chọn lọc theo nhu cầu của riêng mình là các bệnh viện đưa ra thời hạn chấp nhận gấp, sinh viên y khoa nhận chỗ làm quá sớm… Vì thế, Chính phủ Mỹ đã thành lập một trung tâm điều phối có tên là National Resident Matching Program (NRMP) để tiếp nhận tất cả nguyện vọng của các bác sĩ cũng như các bệnh viện, từ đó điều phối sao cho phù hợp nhất. Năm 1984, nhà kinh tế Alvin Roth phát hiện ra thuật toán của NRMP áp dụng gần với thuật toán “chấp nhận trì hoãn” của Gale Shapley.

Trước năm 2004, quá trình tuyển sinh vào các trường công ở New York áp dụng lý thuyết “chấp nhận tức khắc” cũng dẫn tới tình trạng học sinh không đăng ký nguyện vọng thật của mình. Do đó, cần có một phương án giải quyết những vấn đề trên nhằm đảm bảo tính ổn định cũng như khuyến khích sự thành thật trong việc đăng ký nguyện vọng.

GS. Hà Huy Khoái khẳng định, Bộ Giáo dục có thể áp dụng kết quả của thuật toán này vào công tác xét tuyển nguyện vọng đại học, cao đẳng để tránh tình trạng rút ra rút vào hồ sơ, gây mệt mỏi cho thí sinh như mùa tuyển sinh vừa qua.

Giống như bài toán cầu hôn, vẫn là quá trình rút ra rút vào nhưng tất cả được thực hiện bởi máy móc, phần mềm. Việc của các thí sinh là đưa ra danh sách thứ tự ưu tiên của mình, các trường cũng đưa ra thứ tự ưu tiên của mình: điểm thi, học bạ, hạnh kiểm… Với các trường đặc thù có thể là chiều cao, cân nặng, năng khiếu… Sau đó máy móc sẽ thực hiện toàn bộ quá trình rút ra rút vào đó và đưa ra một kết quả tốt nhất cho các thí sinh, đảm bảo rằng sẽ không có thí sinh nào điểm thấp hơn mình vào được trường đó mà mình không vào được.

Theo GS. Hà Huy Khoái, đây là giải pháp duy nhất cho vấn đề tuyển sinh hiện nay. Giải pháp này đảm bảo các yếu tố: cho phép các trường đề ra thứ tự ưu tiên cho mình, đảm bảo quyền lợi của học sinh: nêu nguyện vọng thật, học sinh được theo học tại trường ưu tiên cao nhất có thể theo thứ tự ưu tiên tùy thuộc kết quả của thí sinh, loại bỏ được yếu tố “ảo” và tiết kiệm chi phí.

“Chúng tôi đã thử nghiệm và cho kết quả tốt. Chỉ trong vòng 2 tiếng xứ lý được dữ liệu của 1 triệu thí sinh. Làm tất cả chỉ trong vòng 1 ngày là xong” – GS. Hà Huy Khoái khẳng định.

Ông cũng cho biết Cục Khảo thí cũng tỏ ra rất tâm đắc với phương án này và có mời ông tới nói chuyện với các trường. “Các trường tốp đầu hiểu rất nhanh và thích phương án này nhưng không hiểu sao lãnh đạo nhiều trường khác thì không muốn áp dụng. Họ bảo cứ để họ tự làm theo cách truyền thống” – ông nói.

“Tôi cũng rất tiếc vì năm vừa rồi Bộ không áp dụng. Có lẽ Bộ còn lo ngại các trường”.

GS. Hà Huy Khoái cũng cho rằng cái khó trong vấn đề này không phải là vấn đề kỹ thuật mặc dù để áp dụng vào tuyển sinh cần phải cải tiến đôi chút, mà khó nhất là thuyết phục được xã hội, làm thế nào để các phụ huynh, các em học sinh, các trường hiểu được và đồng tình. Ban đầu, giải pháp NRMP ở Mỹ cũng không phải bác sĩ nào cũng tham gia nhưng sau đó họ nhận ra không tham gia thì bị thiệt.

Ông cũng cho biết các nhà khoa học cũng đã gợi ý Bộ trước mắt dùng 80% chỉ tiêu để áp dụng thuật toán này. “ Tôi rất hy vọng năm sau Bộ sẽ áp dụng. Theo tôi đây là giải pháp duy nhất” – ông nói.

Nguyễn Thảo - VNN

 Xem thêm Bài toán hôn nhân bền vững

Read More

Lý giải đằng sau những bài toán tính gà kiểu Mỹ

Những bài toán đơn giản nhưng có lời giải khó hiểu và phức tạp thậm chí với cả người lớn gần đây được chia sẻ nhiều trên các phương tiện truyền thông của Mỹ. Đây được cho là những bài toán được giải theo quy định trong bộ Sáng kiến Tiêu chuẩn chung liên bang – Common Core State Standards Initiative (gọi tắt là Common Core).

Phụ huynh Mỹ lúng túng

Chị Jennifer Craig nhìn chằm chằm vào bài tập toán của cô con gái. Đó là một phép nhân 3 chữ số khá đơn giản. Nhưng cô con gái 10 tuổi của chị giải nó bằng cách vẽ biểu đồ, tách số, nhân, cộng và một số bước rắc rối khác.

“Tôi thấy điên đầu” – bà mẹ 31 tuổi nói.

Và đó là lý do tại sao chị có mặt trong lớp học của con gái vào tối thứ Hai, cùng với nhiều phụ huynh khác, ngồi trên những chiếc ghế trẻ con, nghe cô giáo Alyshia Thomas giảng giải về cách làm toán mới.

Hầu hết học sinh ở các trường công của Mỹ đều đang học Toán rất khác với thời của bố mẹ chúng do sự xuất hiện của Common Core.

Những thay đổi này khiến nhiều phụ huynh lúng túng khi giúp con làm bài tập về nhà, đặc biệt là những người có con học tiểu học.

Melissa Palermo là một giáo viên lớp 4 tràn đầy nhiệt huyết. Cô là người tập huấn cho các giáo viên khác cách giải Toán mới ở Trường Nathaniel Hawthorne. “Phần khó khăn nhất là bài tập về nhà bởi vì nó rất khó với các bậc phụ huynh. Nhiều phụ huynh nghi ngờ chính mình vì họ chưa từng nhìn thấy những cách giải như thế này trước đây”.

“Họ thất vọng vì không thể giúp được con mình” – Bill Hanlon, một giáo viên dạy Toán ở Las Vegas cho hay. “Một trong những thông điệp mà tôi muốn gửi tới các giáo viên là nếu bạn giao những bài tập về nhà mà phụ huynh chưa từng thấy trước đây, hãy gửi kèm một mẩu giấy giải thích việc mà chúng ta đang làm, tại sao chúng ta lại làm vậy đồng thời đưa ra vài ví dụ. Nếu không, bạn sẽ nhận được rất nhiều thắc mắc”.

Cô Diane Dunaskiss – hiệu trưởng Trường Tiểu học Pine Tree khẳng định: “Phương pháp làm toán mới khuyến khích học sinh nghĩ sâu hơn. Khi bạn hiểu mình đang học cái gì, bạn sẽ ứng dụng nó vào việc bạn đang làm trong cuộc sống thực”.

Trước đây, Toán được học theo kiểu ghi nhớ một loạt các công thức, số liệu, mẹo vặt. Các chuyên gia cho rằng hậu quả của cách học này là học sinh Mỹ phải vật lộn với môn Toán. Gần 2/3 học sinh từ lớp 4 đến lớp 8 không đạt trong các bài kiểm tra Toán quốc gia. Phương pháp Common Core khác với phương pháp cũ ở chỗ tập trung vào bản chất đằng sau các hoạt động Toán học và nhấn mạnh vào việc có nhiều cách để đưa ra cùng một câu trả lời.

Common Core kỳ vọng học sinh sẽ không chỉ tìm được đáp án mà còn giải thích được tại sao.

Tại sao cần Common Core?

Bộ tiêu chuẩn giáo dục liên bang đã có từ đầu những năm 90.

Nhưng đến đầu những năm 2000, mỗi bang lại phát triển và áp dụng những tiêu chuẩn học tập riêng của mình.

Lúc này mỗi bang đều có những khái niệm riêng về “đủ điều kiện”. Việc thiếu một chuẩn hóa chung cộng với thực tế thành tích của học sinh Mỹ khá khiêm tốn so với các quốc gia khác trên các bảng xếp hạng quốc tế là lý do tại sao các bang quyết định phát triển Common Core vào năm 2009.

Common Core là tập hợp các tiêu chuẩn học thuật cao ở môn Toán và Đọc hiểu. Common Core được tạo ra để đảm bảo rằng tất cả học sinh tốt nghiệp phổ thông đều có đủ kỹ năng và kiến thức cần thiết để học tốt ở đại học, để làm một công việc nào đó và để bước vào cuộc sống, bất kể các em sống ở đâu.

Bộ tiêu chuẩn này được soạn thảo bởi các chuyên gia và giáo viên trên khắp nước Mỹ. Những tiêu chuẩn này cũng là cách để giáo viên đo lường sự tiến bộ của học sinh trong suốt năm học và để đảm bảo rằng các em đang đi đúng hướng để đạt được thành công trên con đường học tập.

Tranh cãi vẫn chưa dứt

Bất chấp việc Common Core được áp dụng nhanh chóng và rộng rãi, nhóm chỉ trích vẫn phản ứng dữ dội. Một số phụ huynh đăng tải những bài toán và lời giải theo kiểu Common Core bằng giọng điệu mỉa mai, châm biếm. 

Read More

Bài toán lớp 7 khiến phụ huynh, học sinh thắc mắc

Bạn Nguyễn Thanh Như gửi đến VnExpress bài toán trong đề kiểm tra lớp 7 của con với các cách giải khác nhau.

Cách giải một là của con chị Như và một số học sinh trong lớp; cách hai của phụ huynh học sinh; cách ba của cô giáo; còn cách thứ tư là phương pháp giải của sách giáo khoa cũng như đa số sách tham khảo toán 7. 

Dưới đây là bài viết theo tinh thần của độc giả Nguyễn Thanh Như. 

Theo bạn trong 4 cách giải trên, cách nào đúng, cách nào sai và vì sao?

Qua bài viết "Bài toán lớp 7 khiến phụ huynh, học sinh thắc mắc" tôi thấy rất nhiều người quan tâm và comment trái chiều. Tôi cũng thấy hào hứng, xin góp bài viết nêu ra quan điểm của mình.

Về các lời giải thì trò sai trong việc chuyển vế, cô giáo sai vì hiểu sai khi đơn giản biểu thức, phụ huynh và sách giáo khoa giải đúng.

Vấn đề mấu chốt của bài toán chính là việc biểu thức 1/2 : 2x đơn giản thành x/4 hay là 1/4x?

Quan điểm tôi là 1/2 : 2x phải hiểu là 1/4x chứ không phải là x/4 vì:

Thứ nhất: Khi viết 2x có nghĩa tương đương 2*x, tuy nhiên nó còn có nghĩa là x phụ thuộc hoàn toàn vào số 2 trước nó. Tùy vai trò của số 2 trong biểu thức mà x phải đi theo và có ý nghĩ trong biểu thức. Như trong bài toán số 2 là số chia của phân số 1/2 nên 2x cũng phải là số chia của 1/2 luôn.

Thứ hai: Ngoài ra phép nhân có tính giao hoán 2x hay 2*x = x*2, vì vậy 1/2 : 2x có thể viết lại.

1/2 : x*2 hay 1/2 : x2.

Nếu "cụm" 2x này không hiểu nhất quán lúc này 1/2 : 2*x và 1/2 : x*2 lại khác nhau?! Vậy thì cứ quan điểm như phía trên dù có viết 1/2 : x*2 hay 1/2 : 2*x vẫn đơn giản lại là 1/4x.

Thứ ba: Về cách ra đề đối với học sinh đã học qua phân số thì nên thay các dấu tường minh "x - nhân", ": - chia" thành "." hay "/", các dấu tường minh này chỉ còn phù hợp cho học sinh cấp 1.

Khi ra đề nên tối giản, đưa đúng mục tiêu và trọng tâm yêu cầu đến học sinh, không nên để ghép các phép tính dễ gây hiểu nhằm, nhất là trong các phương trình. Ví dụ phương trình ax2 - b = 0 thì không cần triển khai từ số hằng a hay b hay một biểu thức loằng ngoằng bằng các phép tính + - x : của cấp 1.

Thứ tư: Các ý kiến của bạn đọc dùng kết quả thế vào để biết đúng sai thì cũng vô ích khi không thống nhất 1/2 : 2x là x/4 hay là 1/4x. Các máy tính điện tử đầu vào cũng phải theo quan điểm (1) thì mới cho kết quả đúng.

Tôi là kỹ sư phần mềm, từng học chuyên toán Amsterdam (Hà Nội) và đã được trải qua cả nền giáo dục trong, ngoài nước. Thực chất bài toán lớp 7 không phải về vấn đề toán học mà là vấn đề thống nhất quy chuẩn. Nếu không thống nhất được thì dĩ nhiên sẽ ra những kết quả khác nhau. Mọi người nhầm tưởng toán học luôn thống nhất, nhưng thực ra toán học từ xưa nay vẫn luôn tồn tại những kết quả khác nhau trong những trường hợp khác nhau. Lấy ví dụ mọi người luôn được dạy x/0 không được định nghĩa, nhưng thực tế trong một số cấu trúc toán học, vẫn có thể định nghĩa được. Hoặc phép toán 1+2+3+... = -1/12 nghe có vẻ vô lý nhưng lại rất quan trọng trong lý thuyết dây (string theory). Trở lại bài toán lớp 7 này, vấn đề cơ bản gây hiểu nhầm là 1/2:2x nên được hiểu là (1/2:2)x=(1/4)x hay 1/2:(2x)=1/(4x). Trong một số nền toán học từ trước đến nay, ax luôn được ưu tiên (implied multiplication) với a được gọi là hệ số của x. Tuy nhiên, điều này dễ gây hiểu nhầm nên toán học hiện đại hầu như đã bỏ sự ưu tiên này và chỉ tuân theo quy tắc trái sang phải cho nhân chia. Điển hình như engine toán học lớn Wolfram Alpha đã bỏ implied multiplication từ năm 2013. Các bạn có thể thử 1/2x vào Wolfram Alpha sẽ cho kết quả x/2. Vấn đề thứ hai là dấu ":". Ở Việt Nam và một số nền toán học không dùng tiếng Anh thì ":" được hiểu là phép chia. Tuy nhiên thực tế là ":" được sử dụng làm tỷ lệ trong toán học hiện đại. Ví dụ 2:1:3 được hiểu là tỷ lệ giữa cam táo nho chẳng hạn, chứ không phải phép chia kết quả 2/1/3=2/3. Tỷ lệ này phải được giữ nguyên ví dụ 2x:3y là một tỷ lệ và khác với 2x/3y. Ở đây bài toán nhiều khả năng dùng ":" cho phép chia chứ không phải tỷ lệ. Nên được viết lại thành (1/2)/2x=-1/3 tức (1/4)x=-(1/3) tức x=-(4/3).

Độc giả Nguyễn Chiến Thắng chia sẻ cách nhìn của anh sau bài toán lớp 7 gây tranh cãi.

 

 

 

 

 

 

 

 

 Nguồn: Vnexpress [1],[2],[3],[4]

Read More