City of Oneway

Probability Level 4

The city of Oneway has a 3×5 3 \times 5 park, and a 513×1025 513 \times 1025 grassland that they own.

To make it easier to run search and rescue, they want to fill several grid squares with huge trees that prevent passage, so that in the remaining area there is exactly one path between any two grid squares that does not revisit any cells. (We only allow for moving between squares that share a side, and not squares that share a corner.)

For the 3×5 3 \times 5 park, several proposals were submitted, of which 2 are displayed:

The proposal on the left was immediately rejected because there were two ways to go between A and B, and no ways to go between A and C. The proposal on the right was accepted, as it fulfilled their conditions.

The town is under some economic hardship, so they will award the contract to the construction company that uses the fewest trees. For the park, they eventually awarded the contract to another proposal that only used 3 squares of trees.

The 513×1025 513 \times 1025 grassland represents a huge contract that your company wants to be awarded. Determine the minimum number of squares of trees that are needed to fulfill the desires of the town, and allow your company to come out on top.


Problem Loading...

Note Loading...

Set Loading...