Enigma 807: Track tickets
From New Scientist #1962, 28th January 1995 [link] [link]
Susan is on a 2-day holiday, staying near one of the stations on the East-West railway line. There are stations every mile along the line. Tickets are sold in packs. The Go East pack contains a random selection of 9 tickets and each one is for travel of 1 or 2 or 3 or 4 or 5 miles in an easterly direction. The Go West pack contains a random selection of 5 tickets and each one is for travel of 1 or 2 or 3 or 4 or … or 9 miles in a westerly direction.
Susan’s plan for the first day of her holiday starts at her local station, where she will buy one pack of each kind. From the Go East pack she will choose a ticket at random and catch a train going east. When the ticket is used up she will alight; she will then take the pack for travel towards her home station, select a ticket at random, catch a suitable train and alight when the ticket is used up. She hopes to carry on in this way until she alights at a station she has been to before; she will then walk home.
The second day of her holiday again starts at her local station with her buying one pack of each kind. She will sort through the two packs and try to find a selection of East tickets and a selection of West tickets so that the total distances for the two selections are the same; she will then use all the selected tickets to make a trip that ends at her home station.
Q1. On day one, is there a possibility Susan might find herself on a station, wanting a ticket in a particular direction and having none of those left?
Q2. On day one, is she certain eventually to reach a station she has been to before?
Q3. On day two, is she certain to be able to find selections of tickets that meet her requirements?
The only way Susan’s plan for the first day can fail is if she arrives at a station she has visited before, and has no valid ticket to allow her to travel towards the starting station.
So we can look for this situation happening. If it can happen then the answer to Q1 is “Yes”, and the answer to Q2 is “No”. If it can’t happen then the answer to Q1 is “No”, and the answer to Q2 is “Yes”.
For the second day, the only way to fail is if there is a set of tickets in one direction that is not balanced by a set of tickets in the other direction.
This Python program looks for failure scenarios for both days. It runs in 508ms.
Run: [ @replit ]
Solution: Q1: No; Q2: Yes; Q3: Yes.
So Susan’s plans for both the first and second day must both succeed.