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