Running from Samsquanch - Part 1
Puzzle for the week of 8/25/24
Inspired by the Fiddler on the Proof (formerly The Riddler), X’s Puzzle Corner aims to produce a weekly puzzle for readers that enjoy math, probability, and algorithms. Please submit your solution! Solutions will be accepted until 11 pm the following Sunday after the puzzle is posted (in this case 9/1/24). While it isn’t required, I encourage you to opt to have your solution shared so that we all get the chance to see how other’s thought about and attempted the problem!
The answers of all those that volunteered their solutions will be posted Wednesday at 10 am.
In many cases, I expect the readers will be better puzzlers than me so I make no guarantees the solutions are correct. I also make no promises about having worked out the solutions to the puzzles ahead of time so it may be the case that they’re very challenging. Part of the fun is finding out!
In this weeks puzzle, we’re trying to evade—in the words of Trailer Park Boys’ Bubbles—Samsquanch.
You’re thinking about doing a backpacking trip through Rainier National Park but there’s one big concern; that’s Samsquanch territory! After thinking it over for a moment you realize you have one big advantage; Samsquanch’s broad shoulders make it more difficult to navigate dense trees while your small, nerdy frame can fit quite easily. In order to make sure you have a chance to escape, you want to make sure the forest you’re hiking through has sufficient tree density.
Let’s model our forest as a 10x10 square. The top will be the entrance and the bottom will be the exit. For simplicity, we will assume the sides are impassable barriers. Each tree will be modeled by a point and Samsquanch will be modeled by a circle of radius 1. Trees will be distributed uniformly in the 10x10 square. Let’s further assume that Samsquanch can’t fit between any two trees that are less than 2R apart. We need to figure out what density the trees need to be in order for you to evade Samsquanch.
But before tackling this rather tricky probability problem, let’s start with a (hopefully) simpler problem:
Given a randomly sampled forest, what’s the most efficient algorithm you can find to determine if Samsquanch can traverse the forest?
Please submit your answers here.
Cool!