Background

This past weekend I was walking around downtown Berkeley with my friends to get Kingpin Donuts when I thought of this contradiction involving the quickest way to traverses a square with infinitely small street blocks street blocks.

Problem

Setup

Consider a 1 x 1 unit square and a particle starting at the bottom left of the square: (0,0). This particle wants to move to (1,1) [top right] as quickly as possible while moving only along the edges [streets] of the square. In the 1 x 1 case, you have two paths each involving two steps: (1) up, right and (2) right, up. Since these paths are symmetric, we'll treat them as a single path. In this single path, we clearly travel a distance of 2 units [1 unit per step and 2 steps].

Smaller Blocks

Now, what if we divide our existing block into forths; that is, we have four 0.5 x 0.5 unit squares. Now, consider the following two paths that each take four steps: (1) right, right, up, up and (2) right, up, right, up. Just as the previous 1 x 1 case, both of these paths travel a total distance of 2 units [each of the four steps travels 0.5 units].

Say we repeat this dividing of the square n times so our original 1 x 1 unit block is split into 2^n x 2^n sub-blocks, each with side length 1/2^n. Now both the outermost and alternating paths each take 2 * 2^n steps: (1) right 2^n times followed by up 2^n more times and (2) right, up 2^n times. Again, both travel a total distance of 2 units for all n > 0.

Contradiction

However, as we take n to infinity the alternating path looks more and more like particle is travelling along the hypotenuse line from (0,0) to (1,1). But, we know that the distance traveled is always 2 units. How can this be if the particle is travelling along the distance of the hypotenuse which has a distances of √2 units?!

Explanation

This contradiction stumped me for a bit, but I thought of three different ways to explain this seeming contradiction while showering last night.

1: Kinematics

We know that the particle takes a total of 2 * n^2 steps, each of which are at a constant speed [lets say 1 unit/second]. In the original 1 x 1 case, we travel 2 units so we take 2 seconds. In each following case, we take just as long since both the speed and distance are constant so we know that the time we travel is constantly 2 seconds. Therefore, in the 2^n x 2^n sub-blocks case, since we know that we're traveling at a constant 1 unit/sec and taking 2 seconds meaning we're traveling 2 units.

If we watched this scenario play out, we would see the particle appearing to move at a speed of 1/√2 units/sec. That is, even though the line looks like the hypotenuse, it isn't. This makes sense because we cannot travel along the hypotenuse, no matter how small we get: At the very beginning we said the particle can only move along the edges [streets] of the square, meaning only travel right and up. So when we see the particle travel along the hypotenuse at 1/√2 units/sec, we're actually seeing the particle move right and up [or up and right] a tiny amount that we only assume to be along the hypotenuse.

Again, the time staying constant because our speed and distance stay the same: we keep moving 1 unit/sec and we travel a distance [2 for up/right] * [paths] * [distance/path] = 2 * 2^n * 1/2^n = 2 so we take 2 seconds to traverse the grid even as we push n to infinity.

2: Additive

Instead of dividing the square into sub-squares, what if we tiled instead so that we doubled each existing square. That is, we'd start with a single 1 x 1 unit block, then grow to 2 x 2, 4 x 4, 8 x 8, ... etc. However, while we exponentially increase perimeter, we'll also increased our speed proportionally [starting at 1 unit/sec, then 2, 4, 8, ... units/sec]. That way, the particle will always take 2 seconds to complete the square.

In addition to seeing that this 2 seconds is a constant for any resolution, we can also see that the two steps of both right and up movements are finite distances. That means that both the up and right movements are not, and cannot ever, be treated as a single move diagonally [this is what we implicitly assumed was happening when the sub-square sides were of length 1/2^n x 1/2^n].

3: Limit

Adding on to the explanation involving tiling above, we can write an equation to relate the total distance traveled [units] per speed [in units/sec]: 2n/n. With this, we can take the limit of n to infinity and clearly this ends up as 2. This result has the units seconds which is consistent with our other for the particle to travel all paths.

Implications given Constraint

With that being said, this seems to say that travelling eight blocks east and eight blocks north should take the same time as travelling east then north eight times (eight is arbitrary).

In the real world, this isn't often true¹. Blocks aren't perfect rectangles made from streets and your steps are rarely parallel/orthogonal to the x/y axis so, unlike the idealized example, you're rarely moving in just the x or y direction at a single time. Regardless, I still think it's an interesting thought puzzle of sorts.

Shout out to David Jiang + Jack Guerrisi for helping me wrap my head around this problem and to Frank Liu and Phoebe Chen for listening to me try to explain this while toasted on the way to Asian Ghetto! :)

---

¹ Update #1: I found a set of stairs outside the MSRI (fitting!) which is a sort of tiling switchback in that it constrains you to moving like the particle in this problem. It was very foggy that night, so here's a scuffed photo:

---

Update #2: Aidan McNabb (cowboy hat) showed me a contradiction that pi equals four (the staircase paradox) which follows a similar line of reasoning (has the same faults). Turns out this is a fairly old problem and there's a entire form of geometry called Taxicab geometry .