Can you solve the penniless pilgrim riddle? - Daniel Finkel

After months of travel, you’ve arrived at Duonia, home to the famous temple that’s the destination of your pilgrimage. Entering from the northwest, you pass through the city gates and the welcome center, where you’re given a map and a brochure. The map reveals that the town consists of 16 blocks, formed by five streets that run west to east, intersecting five more that run north to south. You’re standing on the northernmost street facing east, with the two blocks containing the gate and the welcome center behind you. The temple’s only entrance lies at the very southeast corner. It’s not a long walk, but there’s a problem. As you learn from the brochure, Duonia imposes a unique tax on all visitors, which must be paid when they arrive at their destination within the city. The tax begins at zero, increases by two silver for every block you walk east, and doubles for every block you walk south. However, a recent reform to make the tax fairer halves your total bill for every block you walk north and subtracts two silver for every block you walk west. Just passing through the gate and the welcome center means you already owe four silver. As a pilgrim you carry no money and have no way of earning any. What’s more, the rules of your pilgrimage forbid you from walking over any stretch of ground more than once during your journey— though you can cross your own path. Can you figure out a way to reach the temple without owing any tax or walking the same block twice in any direction? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 You look at the map to consider your options. Walking towards the temple always increases the tax, and walking away decreases it, so it seems like you can never reach it without owing silver. But what happens when you walk around a single block? If you start out owing four silver and go clockwise starting east, your tax bill becomes six, then 12, then 10, then five. If you looped again, you’d owe seven, 14, 12, and six. It seems that each clockwise loop leaves you owing one extra silver. What about a counterclockwise loop then? Starting owing four again and going south first, your bill changes to eight, 10, five, and three. Looping again you’d owe six, eight, four, and two. Each counterclockwise loop actually earns you one silver. That’s because any tax doubled, plus two, halved, and minus two, always ends up one smaller than it started. The key here is that while the different taxes for opposite directions may seem to balance each other out, the order in which they’re applied makes a huge difference. You start off owing four silver, so four counterclockwise loops would get you down to zero. Unfortunately, it’s not that simple, since you can’t walk the same block twice. But there’s another way to reduce your bill: walking one large counterclockwise loop through the city. From your starting position, walk three blocks south. You need to leave the southernmost street clear for the final stretch, so continuing counterclockwise means going east. Walk two blocks to the eastern wall and you owe a whopping 36 silver. But now you can start reducing your bill. Three blocks north and one block west cuts it to 2.5. You can’t go west from here —that would leave you with no way out. So you go one block south, and the remaining three blocks west, leaving you with a debt of -1 silver. And since doubling a negative number still gives you a negative number, walking the three blocks to the south wall means the city owes you eight. Fortunately, that’s exactly enough to get you through the final blocks to the temple. As you enter, you realize what you’ve learned from your pilgrimage: sometimes an indirect route is the best way to reach your destination.