Hide-and-Seek
Jason Shaw
2026-05-16
Hide-and-Seek
Here is the Friday, May 15, 2026 Fiddler on the Proof problem verbatim.
From Nis Jørgensen comes a game wrapped in a puzzle (wrapped in an enigma?):
I am playing hide-and-seek with my nephew. I start at point O, whereas my nephew can hide at point A, B or C. I can walk from O to A in 2 minutes, from O to B in 3 minutes, from O to C in 4 minutes, and from B to C in 5 minutes. To get from A to B or from A to C, I must pass through O.
My goal is to minimize the time it takes to find him, no matter how clever his strategy might be. What is this optimal time?
Solution
What order does the uncle want to search these hiding places in? He must consider ABC, ACB, BAC, BCA, CAB, and CBA. Let’s call those paths 1 through 6, respectively. I’ll explore a naive strategy first by setting up a uniform probability vector and checking the mean time it will take to find the nephew. If the nephew is hiding at node A, for example, it will take 2 minutes to find him if the uncle takes any of the first two paths, 8 minutes if he takes the third path, 10 minutes if he takes the fifth path, and 14 minutes each if he take paths 4 or 6.
## Uniform probability vector
p <- rep(1/6,6)
## Time it will take me to find my nephew if he's hiding at node A if I take
## each of the paths I've defined.
A <- c(2, 2, 8, 14, 10, 14)
## Do the same for nodes B and C
B <- c(7, 13, 3, 3, 15, 9)
C <- c(12, 8, 14, 8, 4, 4)Let’s now check the mean distances using this naive strategy.
## mean for A
sum(p*A)## [1] 8.333333# mean for B
sum(p*B)## [1] 8.333333# mean for C
sum(p*C)## [1] 8.333333Thus, if we were to use this naive strategy, it doesn’t matter what path the uncle takes. He will find his nephew in about 8.33 minutes on average. But, is there a better strategy? I’d like to find a vector \(p\) such that all the means are the same but at a minimum. To do this, we’ll use the R package called ‘caracas’.
We have three equations we can use as constraints. First, there is \(\sum_{i=1}^6 p_i = 1\). Next, we would like to use \(p(A - B) = -5p_1 - 11p_2+5p_3+11p_4-5p_5+5p_6 = 0\). And finally, we can use a third equation \(p(A-C)= -10p_1-6p_2-6p_3+6p_4+6p_5+10p_6 = 0\). Notice that \(p(B-C) = p(A-C) - p(A-B)\), a combination of the other two.
# define the symbols
p1 <- symbol("p1")
p2 <- symbol("p2")
p3 <- symbol("p3")
p4 <- symbol("p4")
p5 <- symbol("p5")
p6 <- symbol("p6")
# plug in the equations
pathProbs <- c(
p1 + p2 + p3 + p4 + p5 + p6 - 1,
-5*p1 - 11*p2 + 5*p3 + 11*p4 - 5*p5 + 5*p6,
-10*p1 - 6*p2 - 6*p3 + 6*p4 + 6*p5 + 10*p6
)
# solve the system in terms of p4, p5, and p6 (left for completeness)
solve_sys(pathProbs, c(p1,p2,p3))## Solution 1:
## p1 = 3*p4 + 3*p5 + 4*p6 - 3/2
## p2 = 3*p4 5*p5 5*p6 5
## - ---- - ---- - ---- + -
## 2 2 2 4
## p3 = 5*p4 3*p5 5*p6 5
## - ---- - ---- - ---- + -
## 2 2 2 4# solve in terms of p3, p5, and p6 (this works out best)
solve_sys(pathProbs, c(p1,p2,p4))## Solution 1:
## p1 = 6*p3 6*p5
## - ---- + ---- + p6
## 5 5
## p2 = 3*p3 8*p5 1
## ---- - ---- - p6 + -
## 5 5 2
## p4 = 2*p3 3*p5 1
## - ---- - ---- - p6 + -
## 5 5 2Let’s solve \(p*A = 2p_1+2p_2+8p_3+14p_4+10p_5+14p_6\) in terms of the ‘other’ variables.
In terms of \(p_4\), \(p_5\), and \(p_6\): \(p*A = -3p_4-p_5-3p_6 + \frac{19}{2}\). If we want to minimize this, it seems we’d want to stack as much probability in \(p_4\) and \(p_6\) as we can, and leave \(p_5=0\). This method got a little hairy, so I tried solving in terms of other variables.
In terms of \(p_3\), \(p_5\), and \(p_6\): \(p*A = \frac65 p_3+\frac45 p_5 + 8\). This is much more clean and dry. To minimize this, let’s set \(p_3=0\) and \(p_5=0\) and see what relationships we get among the other variables.
We get \(p_1 = p_6\), \(p_2 = \frac12 - p_6\), and \(p_4 = \frac12 - p_6\). So, for some \(p \in [0,1/2]\), the probability vector is in the form \(\left(p, \frac12 -p, 0, \frac12 - p, 0, p \right)\). Let’s test this out.
set.seed(42)
(q <- runif(1, 0, .5))## [1] 0.457403p <- c(q, 0.5-q, 0, 0.5-q, 0, q)
## mean for A
sum(p*A)## [1] 8# mean for B
sum(p*B)## [1] 8# mean for C
sum(p*C)## [1] 8So, using the strategy of choosing a random uniform value \(p\) in \([0,1/2]\), and then creating the path probability decision distribution \((p, 1/2-p, 0, 1/2 - p, 0, p)\), we can expect our path to be of length 8 on average.
Hide wherever you’d like, kid.
Extra Credit
Here is the extra credit posed by the Fiddler verbatim.
My nephew can no longer hide at C, and is instead limited to A and B. But this time, he has a teleporter that can instantaneously transport him from A to B or from B to A. He can use the teleporter as many times as he wants. However, he can’t react to my approach, and must instead plan out his transport schedule ahead of time. That said, he does know the precise time when the game starts.
My goal is to minimize the average time it takes to find him, no matter how clever his strategy might be. What is this optimal time?
Attempt at a solution
The nephew has to set his teleport schedule ahead of time and cannot react to his seeker uncle. He definitely does not want to be sitting at node A at the 2-minute mark because what if that is where his uncle will be headed? The question is where does the nephew want to be sitting at the 3-minute mark, when the uncle could be arriving at node B or sitting in wait at node A? At the outset, the nephew will have to make a probabilistic decision to either teleport to A at the 3-minute mark with probability \(p_A\) or to stay put at node B with probability \(p_B = 1-p_A\).
A conundrum, indeed.
Since he sets the schedule at the outset, the nephew has to pretend that he’ll never be found and produce a schedule. So, he must assume in every case that he hid effectively and must then decide on staying put or teleporting again in 5 minutes, the time it would take the uncle to traverse to the other node if he so chooses.
On the reverse side, the seeking uncle must decide at the outset to head to node A with some probability \(p'_A\) or node B with probability \(p'_B = 1- p'_A\). If A is the node he chooses to go to, he will definitely not find his nephew immediately upon getting there because his nephew isn’t a blathering idiot like our 47th president and all those voters who decided to support him. So, he’ll wait a minute. At the 3 minute mark, he’ll either find his nephew who has telported to A or make a decision based on the probabilities \(p'_A\) and \(p'_B\) to stay at node A or begin walking to node B. After 5 minutes, he’ll either find his nephew or begin the decision again.
If the uncle had initially decided to go to node B, then he’ll either find his nephew immediately upon arriving or make a decision exactly as described above.
So, he can expect to find his nephew in 3 minutes with probability \(p_A*p'_A + (1-p_A)*(1-p'_A)\).
Let’s fix a probability for the nephew: \(p_A = p\), and then calculate the probability \(p'_A = x\) for the uncle that minimizes \(f(x) = xp + (1-x)(1-p) = 1-x-p+2xp\). We see that \(f(x)\) is minimized when \(f'(x) = 2p - 1 = 0\), or when \(p = 1/2\), since \(f''(x) = 2 >0\).
Knowing that the uncle will pick probability \(1/2\), what \(x\) should the nephew choose to maximize \(f(x) = \frac12 x + \frac12(1-x) = 1/2\)? It doesn’t matter, it looks like.
Again, hide where you’d like, kid.
We see that there is a \(\frac12\) probability of finding/being found at each node (as well as the same probability of not finding/being found). So, the expected time is \[ \begin{eqnarray} E(\text{Time to Find}) &=& 3(\frac12)+8(\frac12)^2+13(\frac12)^3+18(\frac12)^4 + \ldots \\ &=& -1 + 5(\frac12)+8(\frac12)^2+13(\frac12)^3 + 18(\frac12)^4 + \ldots \end{eqnarray} \]
Now, if we multiply the first row above by 1/2, note that \((\frac12)*E(\text{Time to Find}) =3(\frac12)^2+8(\frac12)^3+13(\frac12)^4+ \ldots\), and that if we subtract this from the same first row above we also get the equality \((\frac12)*E(\text{Time to Find}) =3(\frac12)+5(\frac12)^2+5(\frac12)^3+5(\frac12)^4 \ldots\). Solving for this, we get \[ \begin{eqnarray} (\frac12)*E(\text{Time to Find}) &=& 3(\frac12)+5(\frac12)^2+5(\frac12)^3+5(\frac12)^4 \ldots \\ &=& -1 + 5(\frac12) +5(\frac12)^2+5(\frac12)^3+5(\frac12)^4 \ldots \\ &=& -1 + 5*\sum_{i=1}^\inf (\frac12)^i \\ &=& -1 + 5\left(\frac{1/2}{1-1/2}\right) \\ &=& -1 + 5 \\ &=& 4 \end{eqnarray} \] Multiplying both sides by 2, we find that the expected time to find my nephew is 8.