I. Các câu hỏi

Chồng bạn có lừa dối bạn?

Ở một thị trấn nọ có 100 cặp vợ chồng. Họ sống với nhau với điều luật khá kỳ lạ: nếu một người chồng ngoại tình với người khác thì người chồng đó sẽ bị hành hình ngay khi người vợ phát hiện ra. Các bà vợ hay hay nói chuyện với nhau về chuyện của những ông chồng nhưng không một ai nói với một bà vợ là chồng của chị đó ngoại tình. Vì vậy tất cả các bà vợ biết về chuyện ngoại tình của tất cả các ông chồng trong thị trấn ngoại trừ chính chồng họ. Một ngày nọ thị trưởng của thị trấn tuyên bố là có ít nhất 1 ông chồng đã ngoại tình. Giả sử thị trưởng của thị trấn nằm ngoài 100 cặp vợ chồng kia, theo bạn thì chuyện gì sẽ xảy ra với thị trấn đó?

100 người tù

Có 100 người đang ngồi tù. Một ngày nọ cai ngục cảm thấy chán nên đưa cho họ một thử thách. Mỗi ngày ông ta sẽ chọn ngẫu nhiên một người tù và đưa họ vào một căn phòng đặc biệt. Trong đó có một bóng đèn và một công tắc. Các người tù khác không thể nhìn thấy hay điều khiển bóng đèn. Người tù chỉ có thể bật, tắt bóng đèn mà không thể viết hay để lại ký hiệu gì khác. Vào ngày nào đó, một người tù nào đó mà có thể nói "Tất cả người tù đã từng ở trong phòng này" mà đúng thì tất cả sẽ được thả. Còn sai thì tất cả sẽ bị hành hình. Các người tù sẽ có thời gian để thảo luận với nhau. Họ sẽ có chiến lược gì để đảm bảo rằng chắc chắn tất cả sẽ được thả?

Đi bộ trên địa cầu

Có bao nhiêu điểm trên địa cầu mà đi xuống phía Nam 1 km, sau đó đi sang phía Đông 1 km rồi đi về phía Bắc 1 km thì sẽ trở về điểm ban đầu?

Hộp bi lỗi

Trong 10 hộp bi thì có 9 hộp bi mỗi viên nặng 10 g, còn lại là hộp bi lỗi với mỗi viên chỉ nặng 9 g. Nếu bạn có một chiếc cân điện tử, hỏi làm sao chỉ với 1 lần cân mà biết được đâu là hộp bi bị lỗi?

Chia vàng

Bạn thuê một người làm việc trong vòng 7 ngày và bạn có một thỏi vàng để trả công cho anh ta. Bạn phải trả công cho anh ta vào mỗi cuối ngày. Vì khối lượng công việc mỗi ngày như nhau nên số vàng phải trả cũng phải như nhau. Nếu chỉ được bẻ thỏi vàng 2 lần thì làm sao để trả công?

II. Đáp án

Chồng bạn có lừa dối bạn?

Nếu có 1 ông chồng ngoại tình. Sẽ có 99 người biết người đó là ai. Vợ anh ta thì biết chuyện của các ông chồng khác nên biết là 99 ông chồng kia không ngoại tình. Nhưng vì thị trưởng nói là có ít nhất 1 người ngoại tình nên chị vợ này sẽ suy luận ra đó chính là chồng mình. Anh ta sẽ bị hành hình ngay ngày hôm đó. Nếu có 2 ông chồng ngoại tình thì 2 bà vợ này sẽ biết chắc là có 1 người ngoại tình hoặc 2 người ngoại tình (chồng của bà vợ kia hay chồng mình). Qua ngày đầu tiên họ không thấy ai bị hành hình cả nên họ kết luận là ông chồng của mình ngoại tình. Vì nếu không ngoại tình thì sẽ chỉ có 1 người ngoại tình mà như ở trên thì ông chồng này sẽ bị hành hình ngày đầu tiên. Kết quả là sẽ có 2 ông chồng bị hành hình vào ngày thứ 2. Quy nạp hóa giả sử với n - 1 ông chồng ngoại tình thì vào ngày thứ n - 1 tất cả họ bị hành hình. Xét trường hợp có n ông chồng ngoại tình thì các bà vợ của họ sẽ biết là có chắc chắn n - 1 hoặc n ông chồng ngoại tình (nếu chồng mình ngoại tình), nhưng vào ngày thứ n - 1 chẳng có ai bị hành hình cả nên không thể ứng với trường hợp có n - 1 ông chồng ngoại tình được. Do đó họ suy ra là chồng mình ngoại tình và tất cả n ông chồng sẽ bị hành hình vào ngày thứ n.

100 người tù

Những người tù sẽ họp với nhau và chọn ra một người thủ lĩnh, gọi người đó là Bob. Chiến lược của họ sẽ như sau: Nếu một người không phải Bob vào phòng, nếu đó là lần đầu tiên người đó vào phòng thì sẽ bật đèn lên còn không thì họ sẽ vẫn để như vậy. Đến lượt Bob vào phòng nếu anh thấy đèn sáng thì chứng tỏ phải có ít nhất một người mới vào phòng, Bob sẽ cộng thêm 1 vào tổng của những người đã vào. Còn không thì anh ta sẽ không làm gì cả. Đến khi Bob đếm tới 99 anh ta sẽ thông báo là đã có 100 người vào phòng.

Đi bộ trên địa cầu

Điểm mà các bạn sẽ nghĩ tới đầu tiên chắc là Bắc Cực. Nhưng liệu đó có phải là điểm duy nhất? Vẽ một vòng tròn có chu vi là 1km ở Nam Cực. Ta bắt đầu từ 1 điểm ở phía Bắc vòng tròn đó 1 km. Khi đi xuống phía Nam 1km sẽ ta sẽ ở trên vòng tròn. Đi về phía Đông 1 km sẽ đi hết chu vi vòng tròn do đó về lại điểm khi ta bắt đầu tới vòng tròn, đi tiếp về phía Bắc 1 km thì sẽ trở về lại điểm ban đầu. Nhưng liệu đã hết. Ta vẽ tiếp vòng tròn khác có chu vi 0.5 km. Cũng bắt đầu từ điểm cách vòng tròn về phía Bắc 1km thì khi tới vòng tròn và đi về phía Đông 1 km, ta sẽ đi được 2 vòng nên sẽ về lại vị trí ban đầu khi tới vòng tròn. Đi tiếp về phía Bắc 1 km lại về điểm ban đầu. Ta có thể làm như thế với vòng tròn có chu vi là 1/n km. Khi đi về phía Đông 1 km thì sẽ đi được n vòng nên sẽ trở về điểm bắt đầu ở vòng tròn. Do đó kết luận là có vô số điểm thỏa mãn câu hỏi.

Hộp bi lỗi

Đánh số các hộp bi từ 1 tới 10. Hộp bi thứ 1 lấy ra 1 viên bi, hộp thứ 2 lấy ra 2 viên và cứ làm như vậy với các hộp khác. Cân tất cả các viên bi lấy ra. Nếu cả 10 hộp đều không lỗi thì ta sẽ cân được 10 + 20 + ... + 100 = 550 (g). Nếu hộp 1 chứa những viên bi lỗi thì sẽ nhẹ hơn số đó 1 g, hộp 2 chứa bi lỗi thì sẽ nhẹ hơn 2 g. Cứ như vậy số g nhẹ hơn so với 550 g là số của hộp chứa những viên bi lỗi.

Chia vàng

Nếu suy nghĩ theo hướng phải chia thỏi vàng thanh 7 phần bằng nhau với chỉ 2 lần bẻ thì khó mà tìm được đáp án. Chìa khóa của vấn đề là chia thỏi vàng làm sao để có thể thực hiện giao dịch với người làm thuê sao cho mỗi ngày anh ta đều nhận được số vàng như nhau. Với 2 lần bẻ ta có thể chia thỏi vàng thành 3 phần: phần 1 chiếm 1/7 thỏi vàng (thỏi 1), phần 2 chiếm 2/7 (thỏi 2), phần 3 chiếm 4/7 (thỏi 4) Ta sẽ trả công như sau Ngày đầu tiên: trả thỏi 1 Ngày thứ hai: trả thỏi 2, nhận lại thỏi 1 Ngày thứ ba: trả thỏi 1 Ngày thứ tư: trả thỏi 4 nhận lại thỏi 1 và 2 Ngày thứ năm: trả thỏi 1 Ngày thứ sáu: trả thỏi 2 nhận lại thỏi 1 Ngày thứ bảy: trả thỏi 1 Vậy vào mỗi ngày ta chỉ trả số lượng tương đương với 1/7 thỏi vàng, thỏa mãn đề bài.

III. Tham khảo

Bài viết được dịch lại và có sửa chữa từ http://www.mytechinterviews.com/10-famous-microsoft-interview-puzzles