During a thread in a private usenet newsgroup, involving finding a stud in a stud wall, somebody posted what I believe is the typical procedure (when the typical hardware store studfinder doesn't work)...
Scott D wrote: ...take a a very thin long nail and hammer it in to a random place. Now try it again two inches to the right and then keep going, making a line of holes until you find a stud. --scott
But that got me thinking about whether or not that typical test-hole-distribution procedure is optimal, whereby I followed up...
off-topic (and just curious): so is that mathematically optimal?,
i.e., after, say, $10,000$ trials, what test-hole procedure gives you
the minimal average #holes drilled/nailed before finding a stud?
Suppose studs are $t$ inches thick (default $2.0$"), and there's a distance $d$ (default $16.0$") between stud centers. Further,
suppose you want a hole within $c$ inches of a stud center, i.e.,
maybe you don't want just an edge, but default $c=t/2$ allows edges.
Then let $h$ inches (default $h=t$) be your distance between test holes. Using the default values, then $h=2$" guarantees you'll get the
first stud to the right (or left) of your first test hole.
But maybe $h=3$" results, on average over many trials, in fewer
necessary holes. (Moreover, if $c<1$", then $h=2$", or other even
divisors of $d$, could go on forever.) Or maybe $h=2",3",2",3"...$,
or some other irregular pattern of holes is optimal.
It's not even clear to me how to approach the problem for
a closed-form solution.
So is there any kind of closed-form solution for this kind of problem? Or at least a way to set it up such that it could be solved?
E d i t
-----------------
Several followups in that newsgroup suggested related (more general)
problems...
- Kal wrote: This is called the Multi-Armed Bandit problem. When RAND was working on it during WWII some smart-aleck suggested typing up the problem in German and dropping leaflets to distract their war efforts.
- dhs wrote: Morse, Phillip M, & Kimball, George E, How to Hunt a Submarine
In any case, the exact problem specified above is simple enough to program. Below are some results for the given default values, $d=16,t=2,c=1$. Then the hole distribution is uniform, with $41$ sets of $50,000$ trials $1\le h\le3$ in increments $\Delta h=.05$. Displayed results are min<avg<max #holes needed to find a stud, and then the average distance from stud center for that final hole.
Note that the naively-expected $h=2$ indeed seems to be the optimal choice. And I'd kind of expected the collection of numbers to be some more-or-less smooth function of $h$. But this expectation is not quite the case...
For 50000 trials: h=1.000, 1 < avg#holes=7.525 < 15, avg_c=0.501
For 50000 trials: h=1.050, 1 < avg#holes=7.290 < 15, avg_c=0.473
For 50000 trials: h=1.100, 1 < avg#holes=7.008 < 14, avg_c=0.458
For 50000 trials: h=1.150, 1 < avg#holes=6.787 < 14, avg_c=0.444
For 50000 trials: h=1.200, 1 < avg#holes=6.564 < 13, avg_c=0.430
For 50000 trials: h=1.250, 1 < avg#holes=6.345 < 13, avg_c=0.430
For 50000 trials: h=1.300, 1 < avg#holes=6.155 < 12, avg_c=0.424
For 50000 trials: h=1.350, 1 < avg#holes=5.980 < 12, avg_c=0.419
For 50000 trials: h=1.400, 1 < avg#holes=5.817 < 11, avg_c=0.426
For 50000 trials: h=1.450, 1 < avg#holes=5.671 < 11, avg_c=0.415
For 50000 trials: h=1.500, 1 < avg#holes=5.526 < 11, avg_c=0.421
For 50000 trials: h=1.550, 1 < avg#holes=5.403 < 11, avg_c=0.431
For 50000 trials: h=1.600, 1 < avg#holes=5.276 < 10, avg_c=0.426
For 50000 trials: h=1.650, 1 < avg#holes=5.183 < 10, avg_c=0.431
For 50000 trials: h=1.700, 1 < avg#holes=5.060 < 10, avg_c=0.444
For 50000 trials: h=1.750, 1 < avg#holes=4.950 < 9, avg_c=0.454
For 50000 trials: h=1.800, 1 < avg#holes=4.844 < 9, avg_c=0.451
For 50000 trials: h=1.850, 1 < avg#holes=4.754 < 9, avg_c=0.464
For 50000 trials: h=1.900, 1 < avg#holes=4.678 < 9, avg_c=0.483
For 50000 trials: h=1.950, 1 < avg#holes=4.590 < 9, avg_c=0.495
For 50000 trials: h=2.000, 1 < avg#holes=4.505 < 8, avg_c=0.502
For 50000 trials: h=2.050, 1 < avg#holes=4.592 < 15, avg_c=0.494
For 50000 trials: h=2.100, 1 < avg#holes=4.672 < 15, avg_c=0.484
For 50000 trials: h=2.150, 1 < avg#holes=4.766 < 15, avg_c=0.475
For 50000 trials: h=2.200, 1 < avg#holes=4.852 < 15, avg_c=0.508
For 50000 trials: h=2.250, 1 < avg#holes=4.962 < 15, avg_c=0.548
For 50000 trials: h=2.300, 1 < avg#holes=5.642 < 27, avg_c=0.555
For 50000 trials: h=2.350, 1 < avg#holes=4.830 < 13, avg_c=0.526
For 50000 trials: h=2.400, 1 < avg#holes=4.864 < 13, avg_c=0.478
For 50000 trials: h=2.450, 1 < avg#holes=4.971 < 13, avg_c=0.429
For 50000 trials: h=2.500, 1 < avg#holes=5.043 < 13, avg_c=0.454
For 50000 trials: h=2.550, 1 < avg#holes=5.085 < 13, avg_c=0.520
For 50000 trials: h=2.600, 1 < avg#holes=5.585 < 19, avg_c=0.565
For 50000 trials: h=2.650, 1 < avg#holes=9.195 < 49, avg_c=0.610
For 50000 trials: h=2.700, 1 < avg#holes=6.763 < 29, avg_c=0.598
For 50000 trials: h=2.750, 1 < avg#holes=5.381 < 17, avg_c=0.551
For 50000 trials: h=2.800, 1 < avg#holes=4.880 < 11, avg_c=0.524
For 50000 trials: h=2.850, 1 < avg#holes=4.926 < 11, avg_c=0.449
For 50000 trials: h=2.900, 1 < avg#holes=4.968 < 11, avg_c=0.415
For 50000 trials: h=2.950, 1 < avg#holes=5.022 < 11, avg_c=0.433
For 50000 trials: h=3.000, 1 < avg#holes=5.058 < 11, avg_c=0.500
So that especially noticeable peak around $h=2.65$ is expanded below, $2.6\le h\le2.7, \Delta h=0.005$...
For 50000 trials: h=2.600, 1 < avg#holes=5.607 < 19, avg_c=0.568
For 50000 trials: h=2.605, 1 < avg#holes=5.656 < 19, avg_c=0.569
For 50000 trials: h=2.610, 1 < avg#holes=5.726 < 19, avg_c=0.579
For 50000 trials: h=2.615, 1 < avg#holes=5.894 < 19, avg_c=0.587
For 50000 trials: h=2.620, 1 < avg#holes=6.096 < 25, avg_c=0.588
For 50000 trials: h=2.625, 1 < avg#holes=6.347 < 25, avg_c=0.592
For 50000 trials: h=2.630, 1 < avg#holes=6.527 < 25, avg_c=0.597
For 50000 trials: h=2.635, 1 < avg#holes=6.927 < 31, avg_c=0.600
For 50000 trials: h=2.640, 1 < avg#holes=7.388 < 31, avg_c=0.604
For 50000 trials: h=2.645, 1 < avg#holes=8.112 < 37, avg_c=0.608
For 50000 trials: h=2.650, 1 < avg#holes=9.185 < 49, avg_c=0.609
For 50000 trials: h=2.655, 1 < avg#holes=11.471 < 67, avg_c=0.618
For 50000 trials: h=2.660, 1 < avg#holes=16.759 < 109, avg_c=0.620
For 50000 trials: h=2.665, 1 < avg#holes=55.469 < 409, avg_c=0.627
For 50000 trials: h=2.670, 1 < avg#holes=29.142 < 209, avg_c=0.622
For 50000 trials: h=2.675, 1 < avg#holes=14.233 < 89, avg_c=0.619
For 50000 trials: h=2.680, 1 < avg#holes=10.595 < 59, avg_c=0.615
For 50000 trials: h=2.685, 1 < avg#holes=8.775 < 47, avg_c=0.609
For 50000 trials: h=2.690, 1 < avg#holes=7.831 < 35, avg_c=0.607
For 50000 trials: h=2.695, 1 < avg#holes=7.168 < 35, avg_c=0.602
For 50000 trials: h=2.700, 1 < avg#holes=6.797 < 29, avg_c=0.599
And now that $h=2.665$ peak really stands out. It's not quite clear to me which number(s) are or aren't even divisors (or incommensurate in some other way) of which others to make that happen in this case. But the somewhat goofy behavior suggests to me that there's not likely to be any closed-form solution (or at least not any easily-discoverable one).
