Một bài toán rất thú vị

[Nguyễn Hoàng Mai (NguyenMai)]

em cũng có 1 bài gần giống bài bật đèn tắt đèn của anh Minh

Có n người bị bắt nhốt vào n phòng khác nhau, các phòng được sắp xếp sao cho nếu 1 phòng có người đóng hoặc mở cửa thì tất cả n-1 người trong n-1 phòng còn lại đều nghe được.
trong tòa nhà này có 1 căn phòng trống chỉ có 1 bóng đèn và 1 công tắc để bật và tắt đèn.
luật chơi đặt ra là sẽ có 1 người đi đến 1 trong n phòng pick randomly 1 người đưa vào phòng có bóng đèn. khi người này được đưa vào phòng thì có thể tắt, bật, hoăc để nguyên trạng thái của đèn.
tất cả n người sẽ được thả nếu 1 trong số họ khẳng định đúng là tất cả đã có mặt trong phòng.
trước khi bị nhốt vào n phòng n người có 1 tiếng để tìm strategy...
câu hỏi là họ phải làm ntn?

 

[Vũ Ngọc Nam (Vũ Ngọc Nam)]

đố vui bài này: một làng co 50 cặp vợ chồng. Nêu ông chồng A mà lăng nhăng thì tất cả các bà vợ (trừ vợ A) đều biết là A lăng nhăng (khiếp và nếu vợ A mà biết A lăng nhăng thì sẽ "giết" A ngay tối hôm biết tin đó.
Cuộc sống thanh bình cứ thế trôi đi cho đến một hôm có một tay Sultan đạo hồi đến nói ầm lên: trong số 50 đức ông khả kính có ít nhất một ông có thói quen ăn "phở" thay "cơm". Điều gì xảy ra với cái làng đó nếu biết rằng có đúng 10 ông chồng lăng nhăng trong số 50 ông.
XS

Những điều xảy ra tiếp theo là :

Các ông chồng bụng bảo dạ: "Ôi dào, các bà ấy biết hết rồi, có gì khác đâu". Có vẻ như thực tế diễn ra đúng như các ông mong đợi. Ngày thứ nhất, ngày thứ hai,...rồi đến ngày thứ 9, cuộc sống trong làng vẫn trôi đi một cách êm ả. Đến đêm thứ mười, không khí tĩnh lẵng bỗng bị xé toang bởi nhưng tiếng thét khủng khiếp. Sáng hôm sau ngưởi ta gặp lại tay Sultan đạo hồi nọ. Hắn vừa đi vừa lải nhải như người mất hồn: " làng này không còn người ngoại tình nữa rồi..." :cry:


Tóm lại, nếu có n người ngoại tình thì cần đến n đêm để các bà đồng thời phát hiện ra và đem "giết". Cái hay của bài là tay đạo hồi, vì thông tin mà hắn đưa ra có giá trị hơn ta tưởng ( mặc dù ai cũng đã biết là có người ngoại tình ). Em không lý giải được chuyện này, anh có lý giải được không hả anh Sơn??

Bài THÔNG MINH và THÀNH THỰC tớ đề cập ở trên cũng là một dạng phân tích thông tin cặn kẽ kiểu như thế. :x

nếu anh không giải thích được chuyện này(em không hiểu là anh có thể giải thích hay không, thôi, cứ cho là không được nhá ) ) thì em giải hộ cho.
Giả sử có 1 ông chồng nhá, thì sau 1 đêm bà vợ không thấy ai chết=> giết thằng chồng mình. 2 thằng thì sau 2 đêm, 3 thằng 3 đêm.... cứ như vậy thôi

 

[Nguyễn Hoàng Dũng (ThomasTran)]

nếu anh không giải thích được chuyện này(em không hiểu là anh có thể giải thích hay không, thôi, cứ cho là không được nhá ) ) thì em giải hộ cho.
Giả sử có 1 ông chồng nhá, thì sau 1 đêm bà vợ không thấy ai chết=> giết thằng chồng mình. 2 thằng thì sau 2 đêm, 3 thằng 3 đêm.... cứ như vậy thôi

Wow, chú quả là thông minh!! =D> --> xấu hổ quá ( . Mà bài này thuộc dạng đơn giản đúng không, mấy cái bài bật tắt đèn khó như gì ý :-s

 

[Phan Nhật Minh (phannhatminh)]

em cũng có 1 bài gần giống bài bật đèn tắt đèn của anh Minh

Có n người bị bắt nhốt vào n phòng khác nhau, các phòng được sắp xếp sao cho nếu 1 phòng có người đóng hoặc mở cửa thì tất cả n-1 người trong n-1 phòng còn lại đều nghe được.
trong tòa nhà này có 1 căn phòng trống chỉ có 1 bóng đèn và 1 công tắc để bật và tắt đèn.
luật chơi đặt ra là sẽ có 1 người đi đến 1 trong n phòng pick randomly 1 người đưa vào phòng có bóng đèn. khi người này được đưa vào phòng thì có thể tắt, bật, hoăc để nguyên trạng thái của đèn.
tất cả n người sẽ được thả nếu 1 trong số họ khẳng định đúng là tất cả đã có mặt trong phòng.
trước khi bị nhốt vào n phòng n người có 1 tiếng để tìm strategy...
câu hỏi là họ phải làm ntn?

Bài này cách giải hoàn toàn giống bài của bác Điềm, đề bài dễ hiểu hơn nhờ chỉ sử dụng 1 công tắc thay vì 2 công tắc như bài của bác Điềm. Có điều anh nghĩ điều kiện mọi người đều nghe thấy có người đóng hay mở cửa là thừa, không cần thiết.
Cheers

 

[Nguyễn Hoàng Mai (NguyenMai)]

Điều kiện nghe được đấy giúp đưa ra lời giải thứ 2 cho bài toán:

vì mọi người đều nghe được tiếng mở và đóng cửa nên họ sẽ xác định được thứ tự của mình khi được đưa vào phòng.
strategy sẽ là như thế này:
+xét n lần vào phòng đầu tiên:
người đầu tiên vào phòng sẽ bật đèn lên, những người sau vào phòng, nếu là lần đầu tiên thì để nguyên trạng thái của đèn, nếu đã vào phòng nhiều hơn 1 lần thì tắt đèn đi
đến lần thứ n, người vào phòng thấy đèn sáng và mình vào lần đầu tiên thì chứng tỏ tất cả mọi người đã vào phòng (như vậy có thể nói), nếu thấy đèn tắt thì bật lên và đi ra.
+sau đấy quá trình lại được đếm lại từ đầu (cancel n lần đầu tiên và bắt đầu đếm lại từ 1)...
như vậy lần thứ n, 2n, 3n, 4n...sẽ có khả năng có người nói được tất cả đã có mặt ở trong phòng ...nếu đèn bật...

em thấy cách giải này cũng ko hay lắm, nhưng cũng chưa tính được probability thành công là bao nhiêu, em cũng ko biết fai tính probability thành công của cách giải kia áp dụng cho bài toán này ra sao...
ko hiểu như thế nào thì được coi là 1 lời giải chặt chẽ!!!

 

[Trần Tuấn Anh (Ipsen)]

nếu anh không giải thích được chuyện này(em không hiểu là anh có thể giải thích hay không, thôi, cứ cho là không được nhá ) ) thì em giải hộ cho.
Giả sử có 1 ông chồng nhá, thì sau 1 đêm bà vợ không thấy ai chết=> giết thằng chồng mình. 2 thằng thì sau 2 đêm, 3 thằng 3 đêm.... cứ như vậy thôi

Wow, chú quả là thông minh!! =D> --> xấu hổ quá ( . Mà bài này thuộc dạng đơn giản đúng không, mấy cái bài bật tắt đèn khó như gì ý :-s

Em vẫn không hiểu 8-} Nếu sau một đêm, tất cả các bà vợ đều nghe ngóng, không thấy bên hàng xóm có động tĩnh gì, vác dao ra cả thì lúc đấy chết cả 50 lão chứ đâu chỉ có 10 lão :-/ Nếu cứ giả sử cách nghĩ của các bà vợ như thế nào đó đi, để cho mỗi đêm một lão chết, thì đến bà thứ 3, nếu lão sultan không tiếp tục thay mặt "cụ Giáp" <j/k> đến thông báo hoàn cảnh gia đình hàng ngày thì nhỡ các bà yên chí "nhiều hơn một tức là 2, mà hai lão chết rồi, vậy là yên ổn", thì lúc đấy lại trở lại như ban đầu không?
Em nghĩ cần thêm điều kiện về thời gian ngoại tình nữa Nếu mà ngoại tình trong nội bộ làng thì khác, mà ngoại tình xuyên làng thì khác

 

[Vũ Ngọc Nam (Vũ Ngọc Nam)]

anh thông cảm, văn em hơi kém nên diễn đạt chán lắm, em giải lại nhé. Nếu co 1 người ngoại tình => bà vợ biết ngay vì bà ta không thấy những thằng khác ngoại tình mà lại biết chắc trong làng có người ngoại tình. nếu có 2 người thì sau 1 đêm bà vợ không thấy ai chết => có ít nhất 2 thằng, mà mình chỉ thấy ngòai chồng mình có mỗi một thằng khác nữa=> xử lý luôn ) .... cứ như thế là xong

 

[Nguyễn Hoàng Mai (NguyenMai)]

thêm 1 giữ kiện nữa là tất cả các bà vợ có chồng ngoại tình đều biết có 9 ông chồng khác ngoại tình, vì thế sau 9 ngày nếu ko có ai chết thì chắc chắn chồng mình cũng ngoại tình...

 

[Nguyễn Hoàng Dũng (ThomasTran)]

Nếu co 1 người ngoại tình => bà vợ biết ngay vì bà ta không thấy những thằng khác ngoại tình mà lại biết chắc trong làng có người ngoại tình. Nếu có 2 người...

Anh công nhận là về logic chú hoàn toàn chính xác. Ta có thể lý luận quy nạp từng bước để giải bài toán này.. Tuy nhiên cái câu " nếu có 1 người ngoại tình" của chú rất có vấn đề!! Vì có 10 người ngoại tình nên mỗi bà đều biết là có ít nhất là 9 ông ngoại tình, Thế nên không thể nói " nếu chỉ có 1 người ngoại tình " được! Hơn nữa, để thực sự thuyết phục, chú phải giải thích được vai trò của tay Sultan đạo Hồi. Câu nói của hắn có giá trị như thế nào? Nên nhớ là bà nào cũng đã rõ là trong làng có ít nhất 9 người ngoại tình?? :-s . Giải thích điều này không đơn giản đâu. Có lẽ phải nhờ bác Xuân Sơn, hoặc là Ngô Quang Hưng mới được >-

 

[Vũ Ngọc Nam (Vũ Ngọc Nam)]

em nói nếu có 1 người ngoại tình là để tổng quát hóa bài toán với lại để qua bước đầu tiên. Khó có thể bắt đầu từ 10 người luôn được, vì như thế trong khi diễn đạt thì lại phải kéo ngược lại các ngày trước đó, em không biết cách diễn đạt^^. Vai trò của gã sultan chỉ có 1 ý nghĩa duy nhất đó là xác định có người ngoại tình để giúp cho bắt đầu vào bước 1(tức là bước nếu có 1 người). Từ bước 2 trở đi em nghĩ đều có thể suy ra từ bước 1.
Nếu em viết khó hiểu quá thì sorry^^.

 

[Trần Tuấn Anh (Ipsen)]

Chuyện vượt qua bước 1 không cần, vì hoàn toàn có thể suy luận từ 2 người: Bà A thấy chồng bà B ngoại tình, nhưng mãi chẳng thấy vấn đề gì, thế nên nghĩ rằng chỉ có thể bà B biết một người khác ngoại tình nên mới yên chí lớn là không phải chồng bà ta, theo như lời lão Sultan.
Như vậy, mỗi bà vợ đều phải giả thiết là các bà kia ngu hơn mình, như vậy mới có thể giải quyết được theo kiểu quy nạp ngược. Nhưng thực tế, vì các bà vợ thông minh như nhau, thế nên cả xóm có ngày giỗ chung

 

[Bùi Lê Bình (builebinh)]

Bài này phải suy luận thật chặt chẽ thi mới ra đuợc cái hay của nó. Còn cứ nói đại khái như các chú thì vẫn chưa thấu được cốt lõi cùa vấn đề.

Giả sử có 4 bà A,B,C,D, và có 4 ông ngoại tình. Trường hợp N bà hoàn toàn tủơng tự.
Chứng minh rằng trước lúc lão Sultan đến thì

A nghĩ là (B nghĩ là (C nghĩ là (D nghĩ là không có ai ngoại tình))))

Vai trò của lão Sultan là lão ta phủ nhận mệnh đề trên.

 

[Nguyễn Hoàng Dũng (ThomasTran)]

Bài này phải suy luận thật chặt chẽ thi mới ra đuợc cái hay của nó. Còn cứ nói đại khái như các chú thì vẫn chưa thấu được cốt lõi cùa vấn đề.

Giả sử có 4 bà A,B,C,D, và có 4 ông ngoại tình. Trường hợp N bà hoàn toàn tủơng tự.
Chứng minh rằng trước lúc lão Sultan đến thì

A nghĩ là (B nghĩ là (C nghĩ là (D nghĩ là không có ai ngoại tình))))

Vai trò của lão Sultan là lão ta phủ nhận mệnh đề trên.

Yep!! Đây chính là cái mình muốn nghe. Bây giờ thì em đã hiểu. ) >- Dù sao các chú em cũng rất đáng khen

 

[Trần Tuấn Anh (Ipsen)]

Bài này phải suy luận thật chặt chẽ thi mới ra đuợc cái hay của nó. Còn cứ nói đại khái như các chú thì vẫn chưa thấu được cốt lõi cùa vấn đề.

Giả sử có 4 bà A,B,C,D, và có 4 ông ngoại tình. Trường hợp N bà hoàn toàn tủơng tự.
Chứng minh rằng trước lúc lão Sultan đến thì

A nghĩ là (B nghĩ là (C nghĩ là (D nghĩ là không có ai ngoại tình))))

Vai trò của lão Sultan là lão ta phủ nhận mệnh đề trên.

Yep!! Đây chính là cái mình muốn nghe. Bây giờ thì em đã hiểu. ) >- Dù sao các chú em cũng rất đáng khen

Vô lý, theo đề bài, trong trường hợp ông A ngoại tình, bà B,C,D biết ngay. Như vậy thì làm sao có chuyện là "D nghĩ là không có ai ngoại tình" được???

 

[Bùi Lê Bình (builebinh)]

Vô lý, theo đề bài, trong trường hợp ông A ngoại tình, bà B,C,D biết ngay. Như vậy thì làm sao có chuyện là "D nghĩ là không có ai ngoại tình" được???

Đề bài đâu có bắt chứng minh "D nghĩ là không có ai ngoại tình" đâu ?
Chú đi thi mà làm bài kiểu này là được điểm âm như chơi đấy )

 

[Tạ Tuấn Thành (Tuấn Thành)]

Bài này phải suy luận thật chặt chẽ thi mới ra đuợc cái hay của nó. Còn cứ nói đại khái như các chú thì vẫn chưa thấu được cốt lõi cùa vấn đề.

Giả sử có 4 bà A,B,C,D, và có 4 ông ngoại tình. Trường hợp N bà hoàn toàn tủơng tự.
Chứng minh rằng trước lúc lão Sultan đến thì

A nghĩ là (B nghĩ là (C nghĩ là (D nghĩ là không có ai ngoại tình))))

Vai trò của lão Sultan là lão ta phủ nhận mệnh đề trên.

Yep!! Đây chính là cái mình muốn nghe. Bây giờ thì em đã hiểu. ) >- Dù sao các chú em cũng rất đáng khen

Vô lý, theo đề bài, trong trường hợp ông A ngoại tình, bà B,C,D biết ngay. Như vậy thì làm sao có chuyện là "D nghĩ là không có ai ngoại tình" được???

Cả 4 ông đều ngoại tình cả thì:
Bà A biết ông B,C,D ngoại tình, nghĩ rằng chồng mình không ngoại tình
-->bà A nghĩ (bà B sẽ chỉ biết 2 ông ngoại tình là C, D)-->bà A nghĩ (bà B nghĩ(bà C chỉ biết 1 ông D ngoại tình)) -->mệnh đề

 

[Nguyễn Xuân Sơn (NguyenXuanSon)]

việc thông tin của Sultan có tác dụng như một tương tác giữa các bà vợ. Nếu không có Sultan, do các bà vợ không trao đổi với nhau số ông chồng ngoại tình cho nên ho không thể nào đi đến kết luận về sự chung thủy của ông chồng.
Về mặt vật lý, có thể tưởng tượng 50 bà vợ như là 50 observers. Nếu 50 là độc lập thì không có thêm thông tin gì mới ngoài số ông chồng ngoại tình mỗi bà biết. Việc SUltan nôi với các bà vợ giống như một tương tác giữa 50 bà vợ. Có thể chứng minh dễ dàng là nếu tương tác này không mang tính global (chỉ nói với 49 bà) thì hoàn toàn có khả năng các ông chồng sống mãi.
Tóm lại, muốn nghiên cứu một vấn đề (khoa học, xã hội) , cần nghiên cứu trong tương quan giữa các đối tượng trong vấn đề.

 

[Nguyễn Hoàng Dũng (ThomasTran)]

việc thông tin của Sultan có tác dụng như một tương tác giữa các bà vợ. Nếu không có Sultan, do các bà vợ không trao đổi với nhau số ông chồng ngoại tình cho nên ho không thể nào đi đến kết luận về sự chung thủy của ông chồng.
Về mặt vật lý, có thể tưởng tượng 50 bà vợ như là 50 observers. Nếu 50 là độc lập thì không có thêm thông tin gì mới ngoài số ông chồng ngoại tình mỗi bà biết. Việc SUltan nôi với các bà vợ giống như một tương tác giữa 50 bà vợ. Có thể chứng minh dễ dàng là nếu tương tác này không mang tính global (chỉ nói với 49 bà) thì hoàn toàn có khả năng các ông chồng sống mãi.
Tóm lại, muốn nghiên cứu một vấn đề (khoa học, xã hội) , cần nghiên cứu trong tương quan giữa các đối tượng trong vấn đề.

Anh Sơn ra đề xong 1 tháng sau quay lại, được đấy .