ĐỐ VUI KIẾN THỨC

[nqbinhdi]

Nina viết

Nhân tiện em xin phép đả động đến lời giải mấy câu đố của bác nqbinhdi nhé. Câu đố thứ ba em xin trả lời như sau


Em xin phép chỉ đưa ra điểm chính, nếu bác nqbinhdi chấm đúng thì sẽ biện luận chi tiết, tính em vốn lười, nhưng lại thích được thưởng nên nó thế đây

1. - Người thứ nhất có thể bắt đầu từ đống nào cũng được, nếu đống đó còn nhiều hơn 1 que diêm (tức đống đó có 2 que trở lên), khi đó người thứ nhất chỉ để lại 1 que diêm thôi.
   
2. - Khi đó, hoặc là người thứ hai phải lấy que diêm còn lại của đống đó, hoặc lấy đống khác.
   
3. - Người thứ nhất chuyển sang đống khác, làm tương tự bước 1

Không chính xác!

Thí dụ nhé, giả sử ta có 3 đống A, B, C với số que lần lượt là 7, 2, 6 chẳng hạn. Như bạn nói, giả sử bạn lấy 6 que từ A, vậy còn lại là: A: 1, B: 2 và C: 6. Tới lượt tôi, tôi lấy từ C 3 que. Tình hình còn lại là A: 1, B: 2 và C: 3. Bây giờ bạn sẽ lấy thế nào để khỏi bị thua ạ?

[Nina]

Dạ vâng, đúng là được thầy nqbinhdi chỉ dẫn, thông qua Google em đã tìm được đường đi của bài này. Vì em là sinh viên lười, nên không thể trình bày đầu đuôi (có biết đâu mà trình bày, keke), chỉ ... xơi lúa non thôi. Nên xin giải đáp chiến thuật để người thứ nhất luôn luôn thắng như sau

Gọi n1, n2, n3 là số que diêm mỗi đống.

1. Viết n1, n2, n3 theo hệ đếm cơ số 2
2. Tính n12 theo hệ số 2, trong đó mỗi chữ số trong mỗi cột của n12 là XOR từng cột của n1 và n2
3. Tìm n3* sao cho XOR (n1, n2) bằng 0
4. Nếu n3 > n3* thì bước đi đầu tiên của người thứ nhất sẽ là - lấy (n3 - n3*) que diêm từ đống thứ 3, sau đó chờ người thứ 2 đi, và quay lại bước 1. Nếu n3 < n3* thì ta đổi thứ tự các đống (các số n1, n2, n3) và lặp lại từ bước 1. Nếu n3 = n3* dù đã đổi chỗ nhiều lần thì khả năng thắng của người thứ nhất giảm hẳn đến bằng 0, nếu người thứ 2 cũng biết chiến thuật này, các trường hợp còn lại chắc cũng thế.

Em không học toán một cách chuyên nghiệp, không biết thuyết trò chơi, nên chỉ hiểu được đến đó. Tuy nhiên, trong bài mà thầy nqbinhdi ví dụ ở bước trước (ba đống que diêm tương ứng có 7,2 và 6 que), vận dụng chiến thuật trên thì bước đầu tiên, người thứ nhất sẽ lấy đi 3 que diêm ở đống thứ ba.

Một ví dụ khi người thứ nhất có rất ít cơ may chiến thắng - đó là khi ba đống có số que diêm tương ứng là 1,2,3. Tất nhiên chúng ta không xét trường hợp người thứ hai cố tình thua

[Nina]

nqbinhdi viết

Có cả đố vui cơ à, hay nhở.

Mời các bác thử tài tí nhé:

Một nhà ga có hệ đường sắt hình tam giác đều với các cạnh có độ dài đủ lớn, các đỉnh lần lượt là A, B, C. Từ đỉnh A có nhánh đi ra ngoài sang ga khác. Từ đỉnh B có nhánh đường tránh (chạy từ đỉnh B ra phía ngoài tam giác theo đường phân giác kéo dài của góc ABC) với độ dài 5m; từ đỉnh C có nhánh đường tránh (chạy từ đỉnh C ra phía ngoài tam giác theo đường phân giác kéo dài của góc ACB) với độ dài 2m. Trên cạnh AB và AC có các toa tàu I và II với độ dài mỗi toa là 2m. Trên cạnh đáy BC có đầu máy L dài 3m.

Hãy lập kế hoạch để dùng đầu máy L kéo/đẩy/nối toa thế nào đó nhằm hoán chuyển vị trí các toa I và II còn đầu máy sau đó lại về nằm chỗ cũ.

Ghi chú: Chỉ bẻ ghi cho đầu máy hay đoàn tàu đi theo các góc tù, không rẽ theo/qua góc nhọn được.

Bác nqbinhdi ơi, em thử mãi mà chưa đạt được yêu cầu. Em đã dùng hết cả các đường tránh, nhưng vẫn chưa đưa được đầu máy về vị trí cũ. Kính mong bác xem lại đầu bài, hoặc... gợi ý ạ!

[nqbinhdi]

Nina viết

Bác nqbinhdi ơi, em thử mãi mà chưa đạt được yêu cầu. Em đã dùng hết cả các đường tránh, nhưng vẫn chưa đưa được đầu máy về vị trí cũ. Kính mong bác xem lại đầu bài, hoặc... gợi ý ạ!

Đầu bài chắc chắn đúng.

Hint:
Phải chuyển được đầu máy vượt qua toa I sang bên kia. Bài này có thể phát biểu dưới dạng khác: Giả sử hai toa đứng như đầu bài song đầu máy chạy từ ga khác tới và phải chui vào đứng trên cạnh BC, vị trí hai toa vẫn như cũ hoặc hoán đổi (tùy chọn).

[nqbinhdi]

Nina viết

Dạ vâng, đúng là được thầy nqbinhdi chỉ dẫn, thông qua Google em đã tìm được đường đi của bài này. Vì em là sinh viên lười, nên không thể trình bày đầu đuôi (có biết đâu mà trình bày, keke), chỉ ... xơi lúa non thôi. Nên xin giải đáp chiến thuật để người thứ nhất luôn luôn thắng như sau

Gọi n1, n2, n3 là số que diêm mỗi đống.

1. Viết n1, n2, n3 theo hệ đếm cơ số 2
2. Tính n12 theo hệ số 2, trong đó mỗi chữ số trong mỗi cột của n12 là XOR từng cột của n1 và n2
3. Tìm n3* sao cho XOR (n1, n2) bằng 0
4. Nếu n3 > n3* thì bước đi đầu tiên của người thứ nhất sẽ là - lấy (n3 - n3*) que diêm từ đống thứ 3, sau đó chờ người thứ 2 đi, và quay lại bước 1. Nếu n3 < n3* thì ta đổi thứ tự các đống (các số n1, n2, n3) và lặp lại từ bước 1. Nếu n3 = n3* dù đã đổi chỗ nhiều lần thì khả năng thắng của người thứ nhất giảm hẳn đến bằng 0, nếu người thứ 2 cũng biết chiến thuật này, các trường hợp còn lại chắc cũng thế.

Em không học toán một cách chuyên nghiệp, không biết thuyết trò chơi, nên chỉ hiểu được đến đó. Tuy nhiên, trong bài mà thầy nqbinhdi ví dụ ở bước trước (ba đống que diêm tương ứng có 7,2 và 6 que), vận dụng chiến thuật trên thì bước đầu tiên, người thứ nhất sẽ lấy đi 3 que diêm ở đống thứ ba.

Một ví dụ khi người thứ nhất có rất ít cơ may chiến thắng - đó là khi ba đống có số que diêm tương ứng là 1,2,3. Tất nhiên chúng ta không xét trường hợp người thứ hai cố tình thua

Cậu ruột tôi, ông Đàm Quang Vỹ (nguyên hiệu trưởng trường tư thục trấn Ninh Giang thời trước CM, trưởng ty GD Sơn Tây ngày mới hòa bình), là người đã tạo ra trò chơi này từ trước 1945. Thoạt tiên chỉ là có một số quy tắc chơi ít ỏi để thắng, chủ yếu là từ kinh nghiệm.

Đến năm 1965, anh ruột tôi (sinh viên khoa Toán của ĐHSP Vinh) đã giải được bài toán tổng quát. Trò chơi này sau này được trình bày dưới dạng bài toán trò chơi Hái hoa dân chủ và đăng trên báo Toán học và tuổi trẻ dạo những năm 1970s khi tôi còn là học sinh chuyên toán Thái phiên.

Nina đã tìm được lời giải bài toán này thế nào vậy?

[Nina]

Dạ, thưa bác nqbinhdi, mặc dù rất muốn... phét lác rằng em tự nghĩ ra lời giải từ đầu đến đuôi , nhưng em cũng thuộc loại còn có chút lương tâm, mà phét lác kiểu này thế nào cũng bị lật tẩy , nên em xin khai thật như sau

Mới đầu em chỉ nghĩ - trường hợp nào người thứ nhất dễ thắng nhất. Tất nhiên, đó là khi có 1 đống diêm, anh này chỉ việc để lại 1 que, thế là xong! Giàu chí tưởng bở, em bèn phóng tác ngay cũng kịch bản này cho các đống còn lại, thế là có được lời giải thứ nhất, mà bác đã chỉ rõ là sai toét

Sau khi được bác chỉ ra chỗ sai, em bèn chịu khó tư duy thêm một chút, bây giờ sáng kiến nghĩ đến những trường hợp người thứ nhất chắc chắn thua, tất nhiên là xét trường hợp người thứ hai cũng thông minh sáng láng và muốn thắng. Kết quả thì ra được kịch bản này: n1 = 0, n2 = n3 = 1.

Vậy thì nếu làm sao đưa về được trường hợp n1 = n2 = n3 =1 thì chắc chắn người thứ nhất sẽ thắng. Còn nếu đưa về n1=1; n2 = 2, n3 = 3 như bác đã đưa ra ở trên thì người thứ nhất chắc chắn thua. Nhưng ở đây thì em gặp khó khăn, chẳng nghĩ ra được gì, ngoài việc quanh quẩn trở lại kịch bản sai ở trên, nhưng cũng có cái gì đó hơi hơi có lý. Tất nhiên cũng còn vài suy nghĩ quẩn nhanh chóng đi vào ngõ cụt, kiểu như dựa vào tính chẵn lẻ

Tuy nhiên đến đây thì em lại chợt nảy ra ý tưởng hay là hỏi Google. Và nhờ mấy trường hợp dở hơi tự nghĩ ra ở trên mà em tìm được lý thuyết trò chơi NIM. Đến đây thì em còn mỗi việc đọc và trình bày lại cho nó có vẻ ... hiểu biết một chút.

Và nhân đây em cũng xin lỗi là trong bài trước vì quá vui mừng đã tìm được chiến thuật, nên vận dụng sai bét. Nếu ba đống diêm có số que lần lượt là 7,2,6 thì người thứ nhất phải lấy đi 1 que diêm ở đống thứ ba, khi đó thì tổng NIM của 3 đống mới bằng 0.

Đúng là ... bây giờ không còn trẻ, lại còn có Google đâm ra cũng ỷ lại ra trò...

[Nina]

nqbinhdi viết

Đầu bài chắc chắn đúng.

Hint:
Phải chuyển được đầu máy vượt qua toa I sang bên kia. Bài này có thể phát biểu dưới dạng khác: Giả sử hai toa đứng như đầu bài song đầu máy chạy từ ga khác tới và phải chui vào đứng trên cạnh BC, vị trí hai toa vẫn như cũ hoặc hoán đổi (tùy chọn).

Bác nqbinhdi ơi, hai bài này khác nhau mà. Bài về đoàn tàu chạy từ ga khác tới giải dễ hơn mà, vì trên con đường từ ga khác đến (ở cả hai đầu) có thể để cả đầu máy lẫn hai toa, khác với quãng đường tránh 5m ở bài đầu tiên bác cho. Hoặc là bác cho em cái hình được không ạ, để tránh việc em hiểu sai đầu bài.

[nqbinhdi]

Nina viết

Bác nqbinhdi ơi, hai bài này khác nhau mà. Bài về đoàn tàu chạy từ ga khác tới giải dễ hơn mà, vì trên con đường từ ga khác đến (ở cả hai đầu) có thể để cả đầu máy lẫn hai toa, khác với quãng đường tránh 5m ở bài đầu tiên bác cho. Hoặc là bác cho em cái hình được không ạ, để tránh việc em hiểu sai đầu bài.

Bạn chắc không hiểu sai đầu bài đâu. Hình vẽ đây:

[hanoi]

Mấy câu đố của bác nguyenbinhdi hay nhưng ít tính giải trí, có câu đố sau đây không yêu cầu cái gì cao siêu cả, mọi người ai cũng có thể giải được, lời giải rất đơn giản, xin mời các bác giải giúp:



Có một điểm ảnh bị lỗi hiển thị ko đúng màu, sửa lại điểm ảnh đó để được một đẳng thức đúng.

[hanoi]

hoan hô, bác giải nhanh quá, bà con còn chưa kịp vào đọc đề bài, bác xóa hộ lời giải đi cho bà con còn giải nữa chứ.

Nếu ai lỡ nhìn thấy lời giải của câu trên rồi thì giải bài sau đây vậy, đây là bài mà Google phỏng vấn tuyển nhân viên của mình:

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

[notforsale]

Khi con kiến chạm vào con kiến khác và cùng đổi hướng, vì tốc độ (tính chất) của các con kiến là như nhau nên có thể coi các con kiến này không va chạm nhau mà tiếp tục giữ nguyên hướng đi mà không ảnh hưởng gì tới kết quả.

Vì vậy, thời gian lâu nhất để 10 con kiến cùng rơi khỏi que là thời gian một con kiến bò từ đầu này sang đầu kia, 1 giờ.

Tùy từng điều kiện, thời gian này có thể ít hơn, nhưng không quá 1 giờ.

[hanoi]

Hoan hô vậy là cả 2 bài đều đã được giải gọn gàng bởi thành viên NNN. Bài đầu tiên mà bác ngbinhdi giải được là bài trên trang web của Nga, có thể tìm các câu đố tương tự trên trang này ở địa chỉ ghi trên hình. Bài thứ hai là bài toán khá nổi tiếng thời cấp 2 mà ai học chuyên toán đều có thể đã từng nghe qua. Lời giải của bài toán này cũng có thể tìm được bằng cách google đề bài, kết quả google sẽ dẫn đến trang web của GS Ngô Bảo Châu và blog khoa học máy tính của GS Ngô Quang Hưng nơi mà các bạn có thể tìm thấy các câu đố tương tự khi phỏng vấn.

[nqbinhdi]

hanoi viết

Hoan hô vậy là cả 2 bài đều đã được giải gọn gàng bởi thành viên NNN. Bài đầu tiên mà bác ngbinhdi giải được là bài trên trang web của Nga, có thể tìm các câu đố tương tự trên trang này ở địa chỉ ghi trên hình. Bài thứ hai là bài toán khá nổi tiếng thời cấp 2 mà ai học chuyên toán đều có thể đã từng nghe qua. Lời giải của bài toán này cũng có thể tìm được bằng cách google đề bài, kết quả google sẽ dẫn đến trang web của GS Ngô Bảo Châu và blog khoa học máy tính của GS Ngô Quang Hưng nơi mà các bạn có thể tìm thấy các câu đố tương tự khi phỏng vấn.

Tôi cũng đã giải chưa đến 1 phút bài mấy con kiến, với lập luận rằng các con kiến đều bình đẳng với nhau, do vậy xem như không đổi hướng khi va chạm. Do vậy tối đa 1 giờ tất cả sẽ rơi khỏi que.

Chỉ là không muốn lại phải xóa bài thôi, bạn hanoi ạ.

[Nina]

Tối qua sau khi (hay là trước khi) đi xem bắn pháo hoa thì em tư duy ra lời giải bài toán 2 đoàn tàu của bác nqbinhdi

1. Đầu máy đi theo cạnh BC, hướng CB đến đoạn đường tránh BB'
2. Đầu máy đi tới cạnh AB, hướng B'BA, móc vào toa tàu số 1
3. Đầu máy kéo toa số 1 theo chiều AB tới đoạn đường tránh BB' (đoạn này dài 5m, đủ chỗ cho đầu máy 3m và toa tàu 2 m)
4. Đầu máy đẩy toa số 1 từ đoạn B'B đi theo cạnh BC tới đoạn tránh CC' (đoạn này đủ chỗ cho toa tàu số 1)
5. Đầu máy tách toa số 1 ra, chạy theo lộ trình theo cạnh BC tới B rồi tới đoạn BB', rồi từ BB' theo cạnh AB tới đoạn tránh AA', từ đoạn AA' theo cạnh AC tới móc vào toa tàu số 2
6. Đầu máy kéo toa số 2 đi theo cạnh AC tới đoạn AA', rồi từ AA' tới đoạn AB, tách toa số 2, để toa số 2 trên đoạn AB
7. Đầu máy lại đi tới AA'. từ AA' đi theo cạnh AC tới móc vào toa số 1
8. Đầu máy lại kéo toa số 1 đi theo lộ trình CA - AA', rồi đẩy toa số 1 đi theo cạnh AB đến móc vào toa số 2
9. Đầu máy kéo 2 toa (1 và 2) đi tới đoạn AA', rồi đầu máy đẩy 2 toa (1 và 2) đi theo cạnh AC tới hết cạnh, khi đó toa số 2 sẽ ở đoạn tránh CC', tách toa số 2 ra
10. Đầu máy kéo toa số 1 đến trong đoạn AC, tách toa số 1 ra, bỏ lại.
11. Đầy máy đi tới AA', rồi theo cạnh AB tới đoạn BB', rồi theo cạnh BC tới điểm C, móc vào toa số 2
12. Đầu máy kéo toa số 2 đi tới BB', rồi đẩy toa số 2 theo cạnh AB, tách toa số 2 ra.
13. Đầu máy chạy tới đoạn BB' và rồi về lại cạnh BC

Như vậy tới đây nhiệm vụ đã hoàn thành - toa số 1 ở cạnh AC, toa 2 ở cạnh AB, đầu máy ở cạnh BC, phù, rắc rối quá!

[nqbinhdi]

Hoan hô Nina, tuy nhiên hơi thừa một động tác. Có thể chạy ngắn hơn.

[hanoi]

Bác ngbinhdi tốt nghiệp ở Hungary chắc có biết đến hai bác này Vũ Hà Văn, và An Hải Đoàn, đây là hai GS được cho là người VN làm nghiên cứu computer science thành công nhất. Cả hai đang làm GS ở các trường đại học danh tiếng nhất nước Mỹ và cả hai đều tốt nghiệp ở Hung. Theo tôi nghĩ thì có lẽ Hung là nơi đào tạo Toán ưng dụng nhất là mảng toán tổ hợp rất tốt đã tạo nên thành công của cả hai bác kể trên chăng?

[nqbinhdi]

hanoi viết

Bác ngbinhdi tốt nghiệp ở Hungary chắc có biết đến hai bác này Vũ Hà Văn, và An Hải Đoàn, đây là hai GS được cho là người VN làm nghiên cứu computer science thành công nhất. Cả hai đang làm GS ở các trường đại học danh tiếng nhất nước Mỹ và cả hai đều tốt nghiệp ở Hung. Theo tôi nghĩ thì có lẽ Hung là nơi đào tạo Toán ưng dụng nhất là mảng toán tổ hợp rất tốt đã tạo nên thành công của cả hai bác kể trên chăng?

Rất tiếc là tôi không biết mấy người này. Tuy nhiên, dân tộc Hung đã sản sinh ra rất nhiều người tài giỏi. Người Hung vẫn tự hào họ là dân tộc có số người đoạt giải Nobel tính trên đầu người đứng vào hàng đầu thế giới. Cả thảy có đến 15 người Hung hoặc gốc Hung đoạt giải Nobel trên dân số 10 triệu. Với tỷ lệ ấy, dân tộc Nga cần có chừng hơn 200 người, Trung quốc cần có chừng gần 2000 người.

Ngoài ra, Teller Ede, cha đẻ bom khinh khí cũng là người gốc Hung. Trong những người chủ chốt đầu tiên tham gia thiết kế, chế tạo bom nguyên tử cũng có mấy người Hung (cái gọi là nhóm mafia Hung theo cách gọi đùa của các đồng nghiệp Mỹ lúc đó: Szilárd Leó, Wigner Jeno và Teller Ede).

[Len90]

hanoi viết

Bác ngbinhdi tốt nghiệp ở Hungary chắc có biết đến hai bác này Vũ Hà Văn, và An Hải Đoàn, đây là hai GS được cho là người VN làm nghiên cứu computer science thành công nhất. Cả hai đang làm GS ở các trường đại học danh tiếng nhất nước Mỹ và cả hai đều tốt nghiệp ở Hung. Theo tôi nghĩ thì có lẽ Hung là nơi đào tạo Toán ưng dụng nhất là mảng toán tổ hợp rất tốt đã tạo nên thành công của cả hai bác kể trên chăng?

Cho em lạc đề theo bác hanoi một tí với. Bác hanoi, không biết em có nhớ nhầm không, hình như đ/c An Hải Đoàn học ở Nga, Matxcova? Cùng năm các đ/c này học ở Hung còn có Hà Anh Vũ, giải Olympic toán năm ....Bác hanoi có quen không ạ?

[hanoi]

Len90 viết

Cho em lạc đề theo bác hanoi một tí với. Bác hanoi, không biết em có nhớ nhầm không, hình như đ/c An Hải Đoàn học ở Nga, Matxcova? Cùng năm các đ/c này học ở Hung còn có Hà Anh Vũ, giải Olympic toán năm ....Bác hanoi có quen không ạ?

Anh Đoàn An Hải học đại học tại Kossuth Lajos University, Hungary vào năm 1989-1993 sau đó sang Mỹ học master rồi PhD tại University of Washington Seatle. Những năm này ở Nga đang loạn lạc nếu anh ấy sang Nga có khi cũng đã ra chợ vòm đi buôn theo phong trào. Anh An hải có viết một đoạn tâm sự ngắn về thế hệ của anh được ví như hoa lông chông trên cát rất hay.

[notforsale]

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