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

# What does this mean and what are the limits?

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^{1}. 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! :)

---

^{1}
*Update:* 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: