Thursday 10 October 2024

Magic Paving Stones

This is a sort of a puzzle, sort a paradox (in the soft sense of running contrary to expectation, rather than involving explicit self-contradiction).

Imagine you are standing the first paving stone of a path that consists of an arbitrary number of paving stones.  At the end of the path is some vague monster that you don’t ever want to reach you.  As happens in a nightmare, your feet are firmly stuck to the paving stone that you are standing on and you can’t run.  Fortunately, you have two facts in your favour.

Fact one: the monster moves at a rate of one paving stone per round.

Fact two: you have a singular (once-off) choice to preset the number of magic paving stones that will be activated per round – just before the monster moves.  These magic paving stones will appear between existing paving stones, at random.  More specifically, the likelihood of the paving stone appearing between any two existing paving stones is evenly distributed across the whole path.  For example, if there are three paving stones, there are two locations where a new paving stone could appear – between #1 and #2 (slot #1#2) and between #2 and #3 (slot #2#3), with equal likelihood of P=0.5.  Like this:

For even more clarity, each magic paving stone is inserted between existing paving stones with equal and independent likelihood.  So, if the number of magic paving stones per round that you preset is two, and there are three paving stones, then each magic paving stone could appear in either slot #1#2 or slot #2#3, with an independent likelihood of P=0.5.  This would lead to a likelihood distribution of P=0.25 for both to appear in slot #1#2 or both in slot #2#3, and P=0.5 for one each in slots #1#2 and #2#3 (because there are two variants of this outcome as shown below).


The apparently simple question is: what is the minimum number of magic paving stones do you have to preset for activation each round to ensure that the monster never reaches you?

---

Note that your only decision involves the preset number of magic paving stones that appear each round.  You don't place those stones, they just appear.  Once you set the number, that's it, you can't change it.  Since we are after the minimum number, and we are talking about magic paving stones, we could also add that if you choose a number to be the minimum that is wrong, the stones won't activate at all and the monster gets you.

No comments:

Post a Comment

Feel free to comment, but play nicely!

Sadly, the unremitting attention of a spambot means you may have to verify your humanity.