Đáp án bài toán 25 con ngựa thi Olympic

Nhiều người tham gia giải không thể đưa ra đáp án đúng cho bài toán tìm ra những chú ngựa nhanh nhất.

Đề bài:

Tại một cuộc thi Olympic cho 25 con ngựa có vận tốc khác nhau để trao huy chương cho 3 con ngựa chạy nhanh nhất, nhì và ba, phương pháp tìm ra những con ngựa chiến thắng là nhận biết con nào "chạm vạch đích trước - sau" mà không dùng đồng hồ.

Biết trường đua có 5 làn đường để đua và mỗi lần chỉ có tối đa 5 con ngựa đua với nhau. Hỏi cần ít nhất bao nhiêu lần đua để xác định được 3 con ngựa chạy nhanh nhất, nhì và ba trong 25 con ngựa?

Hướng dẫn:

Do có 25 con ngựa và mỗi lần có tối đa 5 con đua với nhau nên sau ít nhất 5 lần đua mới xác định được 5 con chạy nhanh nhất trong từng lần đua và cần có thêm 1 lần đua để xác định được con chạy nhanh nhất trong 5 con này, tức là chạy nhanh nhất trong 25 con. Từ đó suy ra cần ít nhất 7 lần đua mới xác định đủ 3 con chạy nhanh nhất, nhì, ba trong 25 con ngựa. Ta sẽ chỉ ra với 7 lần đua sau đây sẽ xác định đủ 3 con chạy nhanh nhất, nhì, ba trong 25 con ngựa.

Đánh số 25 con ngựa với thứ tự từ phải sang trái theo 5 cột A, B, C, D, E và từ trên xuống dưới theo 5 hàng 1, 2, 3, 4, 5. Khi đó 25 con ngựa sẽ có ký hiệu theo tọa độ Xk chỉ cột-hàng là: (A1, A2, A3, A4, A5); (B1, B2 ,B3, B4, B5); (C1, C2, C3, C4, C5); (D1, D2, D3, D4, D5) và (E1, E2, E3, E4, E5).

Thực hiện các cuộc đua theo 2 vòng với 7 lần sau đây:

Vòng 1: Thực hiện 5 lần đua cho 5 con ngựa cùng chung một cột. Không mất tính tổng quát giả sử kết quả 5 lần đua được xếp thứ tự theo thời gian giảm dần từ trái sang phải:

Lần 1: kết quả có thứ tự A5, A4, A3 ,A2, A1, suy ra A1 nhanh nhất lần 1.

Lần 2: kết quả có thứ tự B5, B4, B3, B2, B1, suy ra B1 nhanh nhất lần 2.

Lần 3: kết quả có thứ tự C5, C4 , C3, C2, C1, suy ra C1 nhanh nhất lần 3.

Lần 4: kết quả có thứ tự D5, D4, D3, D2, D1, suy ra D1 nhanh nhất lần 4.

Lần 5: kết quả có thứ tự E5, E4, E3, E2, E1, suy ra E1 nhanh nhất lần 5.

Vòng 2: Thực hiện 2 lần đua, mỗi lần cho 5 con ngựa qua sơ tuyển vòng 1.

Lần 6: Chọn 5 con ngựa A1, B1, C1, D1, E1 nhất 5 lần thi đấu với nhau. Giả sử kết quả 5 con ngựa này được xếp thứ tự theo thời gian giảm dần từ trái sang phải: E1, D1, C1, B1, A1, khi đó kết hợp với vòng 1 suy ra A1 nhanh nhất trong 25 con ngựa.

Lần 7: Chọn 5 con ngựa C1, B2 , B1, A3, A2 thi đấu với nhau. Con nào chạy nhanh nhất, nhì lần 7 sẽ là con chạy nhanh nhì và ba trong 25 con ngựa.

Kết luận:

Vậy cần ít nhất 7 lần đua để xác định 3 con ngựa chạy nhanh nhất, nhì và ba.

Trần Phương

• Bài toán 25 con ngựa thi Olympic