## 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.

## 100 comments found