Back to riddler solutions

{{greeting}}

The June 1st, 2018 Riddler Express states:
    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

{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
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:
{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
Year: {{year}} {{endMessage}}

The Shortest Time

Consider the first house to fall. Its neighborhood will progress as follows:
Year 2
1
Year 4
1 X
Year 6
1 X
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.
{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
{{rottingOrder[$index]}}
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
1
Year 4
1 X
2
Year 6
1 X
2 X
3
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 Y2. If N2 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.

Back to riddler solutions