You live in a row house, one of 36 like it on your side of the
block. A disaster strikes, and the city has to be evacuated. Two
years later, with everyone gone for good, the worst-maintained row
house on your side of the block, battered by the elements for too
long, collapses. Within two years, any row house neighboring the
collapsed one also collapses — as does the second-worst-maintained
home on the block, if it wasn’t next to the worst-maintained one.
This contagion continues: Every two years, any row house
next to one that’s already collapsed also becomes rubble, and
houses continue to collapse in order of how badly maintained they
are — the third-worst-maintained house falls in the third round,
the fourth-worst-maintained in the fourth round, and so on,
assuming they were still standing at the start of that round. (The
maintenance rankings are set at the moment the city is evacuated
and don’t change from round to round.) Assuming a random
distribution of poorly maintained homes, what’s the longest your
home can remain standing? What’s the fewest number of years it will
take for all 36 row houses to collapse?
Extra credit: How does either answer change for N rowhouses?
Random Simulation
Year:
{{year}}{{endMessage}}
The shortest simulation
was {{shortestSimulation}} years The longest
simulation was {{longestSimulation}} years
The Longest Time
Your house can survive 72 years when:
You have the 36th-worst-maintained house, and
The houses are arranged exactly in order 1 to 36, or the
reverse.
Year:
{{year}}{{endMessage}}
The Shortest Time
Consider the first house to fall. Its neighborhood will
progress as follows:
Year 2
Year 4
Year 6
Et cetera, where X is a sufficiently large number. By year 12, house 1
will have caused the collapse of five houses to both its left and
right. In the meantime, house 2 will collapse in year 4 and begin the
same pattern. By year 12, the neighborhood could look like:
(X X X X X 1 X X X X X) (X X X X 2 X X X X) (X X X 3
X X X) (X X 4 X X) (X 5 X) (6)
The parenthesis are shown to group the collapses, the groups
may not overlap, and in this case X is are the numbers greater than 6.
Any permutation of these six groups is a scenario where the last house
falls in year 12. Out of the 36! (factorial) possible
permutations of the neighborhood's maintenance, there are 6! = 720
times when the dystopia achieves the shortest time.
Year:
{{year}}{{endMessage}}
The General Case
In the discussion above, the longest time for 36 houses was 72 years.
An induction proof shows that N houses require 2N years at most.
For the shortest collapse, reconsider the table:
Year 2
Year 4
Year 6
When these groups do not overlap, year 2 sees 1 collapse, year 4 sees
3 + 1 collapsed, year 6 sees 5 + 3 + 1 collapsed, ..., and year 2Y
would see the sum of the first Y odd numbers collapsed, which equals
Y^{2}. If N^{2} houses can fall in 2N years, then N
houses can fall in 2√N
years, where that quantity is rounded up to the next even integer
when it is not already an even integer. For example, where N = 5,
2√5 = 4.47, so
it will take 6 years.