Bài toán hóc búa xe vượt hầm núi của tác giả người Anh

Tác giả Alex Bellos của Guardian vừa giới thiệu bài toán liên quan tình trạng xe lưu hành trên đường hầm qua núi.

Đề bài như sau:

Khi đang lái xe qua một ngọn núi, nhóm tài xế phải dừng lại do tảng đá rơi xuống, chắn lối vào hầm.

Một số người xuống xe để di dời tảng đá. Tuy nhiên, khi lối vào hầm đã thông thoáng, vấn đề khác lại xuất hiện khi phía sau họ là hàng dài xe dừng lại vì tắc đường.

Tình trạng tắc nghẽn trên con đường có hai làn này do 18 chiếc xe màu trắng và 18 chiếc xe màu đen gây ra. Chiếc đầu tiên nằm ở làn bên trái màu trắng trong khi chiếc đầu tiên nằm trên làn phải màu đen.

Những chiếc xe kế tiếp có màu sắc xen kẽ (như vậy, làn bên trái sẽ là trắng – đen – trắng…, làn bên phải là đen – trắng – đen…).

Đi qua đường hầm chật hẹp, hai làn xe phải hợp lại thành một và khi đi hết đoạn đường hầm, các xe lại tách làm hai nhánh để đi qua trạm thu phí.

Giả sử chiếc xe đầu tiên ra khỏi đường hầm có màu đen, chiếc cuối cùng có màu trắng và các xe đi qua trạm thu phí thành từng cặp (hai xe đi đầu cùng qua trạm tại một thời điểm rồi lại đến hai xe tiếp theo).

Như vậy, tối đa có bao nhiêu cặp xe có màu giống nhau cùng qua trạm?