• #### 2 foxes in 5 (adjacent) holes

From henhanna@gmail.com@21:1/5 to All on Tue Jun 7 17:06:22 2022
(this variation is pretty good)

Consider five holes in a line. One of them is occupied by a fox.
Another one is occupied by another fox.
(A hole is big enough to contain only 1 fox)

Each night, the foxes don't move, OR
one fox moves to the hole on the right.

Each morning, you get to inspect 2 holes of your choice.

What strategy would ensure that both foxes are (eventually)
simultaneously discovered ?

______________________

2 foxes in 3 (adjacent) holes
2 foxes in 4 (adjacent) holes
2 foxes in 5 (adjacent) holes

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Edward Murphy@21:1/5 to henh...@gmail.com on Sun Jun 12 14:41:31 2022
On 6/7/2022 5:06 PM, henh...@gmail.com wrote:

Consider five holes in a line. One of them is occupied by a fox.
Another one is occupied by another fox.
(A hole is big enough to contain only 1 fox)

Each night, the foxes don't move, OR
one fox moves to the hole on the right.

Each morning, you get to inspect 2 holes of your choice.

What strategy would ensure that both foxes are (eventually)
simultaneously discovered ?

Label the holes A (left) through E (right). Then this corresponds to a
single fox and ten holes:

DE
CD CE
BC BD BE

where each morning you get to inspect one hole, and each night the fox
either stays put or moves one hole right or moves one hole up.

One possible strategy: Inspect holes AB AC AD AE BC BD BE CD CE DE in
that order. The fox can never move to a hole you already inspected
before you find it. (Not necessarily optimal. Takes 10 inspections, e.g.
if the fox started in DE and stayed there the whole time.)

This generalizes to any number of foxes (f) and any number of holes (h),
which corresponds to one fox and a larger number of holes in an
f-dimensional layout, where each night the fox either stays put or
moves one hole in the positive direction along some axis. The larger
number of holes is somewhat larger than (h^f)/f, and a good bit less
than h^f; not sure how to find a closed-form representation.

This works even if each inspection only tells you either "you found
both foxes" or "you didn't find both foxes". If you get more detail,
e.g. "the hole on the left contained a fox", then you may be able to
narrow things down more quickly.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From henhanna@gmail.com@21:1/5 to Edward Murphy on Sun Jun 12 19:41:45 2022
On Sunday, June 12, 2022 at 2:41:37 PM UTC-7, Edward Murphy wrote:
On 6/7/2022 5:06 PM, henh...@gmail.com wrote:

Consider five holes in a line. One of them is occupied by a fox.
Another one is occupied by another fox.
(A hole is big enough to contain only 1 fox)

Each night, the foxes don't move, OR
one fox moves to the hole on the right.

Each morning, you get to inspect 2 holes of your choice.

What strategy would ensure that both foxes are (eventually)
simultaneously discovered ?

Label the holes A (left) through E (right). Then this corresponds to a
single fox and ten holes:

. . . . . . DE
. . . . CD CE
. . BC BD BE

where each morning you get to inspect one hole, and each night the fox
either stays put or moves one hole right or moves one hole up.

One possible strategy: Inspect holes AB AC AD AE BC BD BE CD CE DE in
that order. The fox can never move to a hole you already inspected
before you find it. (Not necessarily optimal. Takes 10 inspections, e.g.
if the fox started in DE and stayed there the whole time.)

thanks ! this is really good. if i was Martin Gardner, i sure would
include your approach in my column.

it must be optimal in the sense that a 9-inspection answer is impossible.

at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong
because it was different from my answer. So now i'm wondering
how many answers are there ?

----------- and ... Are all the answers equally good ?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Phil Carmody@21:1/5 to Edward Murphy on Mon Jun 13 17:50:24 2022
Edward Murphy <emurphy42@zoho.com> writes:
On 6/7/2022 5:06 PM, henh...@gmail.com wrote:

Consider five holes in a line. One of them is occupied by a fox.
Another one is occupied by another fox.
(A hole is big enough to contain only 1 fox)

Each night, the foxes don't move, OR
one fox moves to the hole on the right.

Each morning, you get to inspect 2 holes of your choice.

What strategy would ensure that both foxes are (eventually)
simultaneously discovered ?

Label the holes A (left) through E (right). Then this corresponds to a
single fox and ten holes:

DE
CD CE
BC BD BE

where each morning you get to inspect one hole, and each night the fox
either stays put or moves one hole right or moves one hole up.

One possible strategy: Inspect holes AB AC AD AE BC BD BE CD CE DE in
that order. The fox can never move to a hole you already inspected
before you find it. (Not necessarily optimal. Takes 10 inspections, e.g.
if the fox started in DE and stayed there the whole time.)
...
This works even if each inspection only tells you either "you found
both foxes" or "you didn't find both foxes". If you get more detail,
e.g. "the hole on the left contained a fox", then you may be able to
narrow things down more quickly.

More optimal, at least when measuring effort: do bugger all for a year
or two, then inspect DE.

But the problem's underspecified for the reasons you state. Is the
discovery of a single fox a failure of the strategy, given that the
goal was to discover them simultaneously? If so, just waiting for
them to enter the state they can't leave has to be best.

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have gained some understanding of the world in which we live. As such, we can cast aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Mike Terry@21:1/5 to Phil Carmody on Mon Jun 13 17:33:34 2022
On 13/06/2022 15:50, Phil Carmody wrote:
Edward Murphy <emurphy42@zoho.com> writes:
On 6/7/2022 5:06 PM, henh...@gmail.com wrote:

Consider five holes in a line. One of them is occupied by a fox.
Another one is occupied by another fox.
(A hole is big enough to contain only 1 fox)

Each night, the foxes don't move, OR
one fox moves to the hole on the right.

Each morning, you get to inspect 2 holes of your choice.

What strategy would ensure that both foxes are (eventually)
simultaneously discovered ?

Label the holes A (left) through E (right). Then this corresponds to a
single fox and ten holes:

DE
CD CE
BC BD BE

where each morning you get to inspect one hole, and each night the fox
either stays put or moves one hole right or moves one hole up.

One possible strategy: Inspect holes AB AC AD AE BC BD BE CD CE DE in
that order. The fox can never move to a hole you already inspected
before you find it. (Not necessarily optimal. Takes 10 inspections, e.g.
if the fox started in DE and stayed there the whole time.)
...
This works even if each inspection only tells you either "you found
both foxes" or "you didn't find both foxes". If you get more detail,
e.g. "the hole on the left contained a fox", then you may be able to
narrow things down more quickly.

More optimal, at least when measuring effort: do bugger all for a year
or two, then inspect DE.

But the problem's underspecified for the reasons you state. Is the
discovery of a single fox a failure of the strategy, given that the
goal was to discover them simultaneously?

Yes, the goal is to discover them simultaneously, like the problem states.
The statement doesn't explicitly state what info you're given if you look in two holes and only one
of them has a fox - but I think that in practice if you look in a hole with a fox you're going to
see the fox (it doesn't have an invisibility cload hehe). Anyway, Edward's idea works even if
you're not told where single foxes are detected.

If so, just waiting for
them to enter the state they can't leave has to be best.

That doesn't work, because the foxes are not obliged to move. You need to "flush them out" as in
Edward's strategy, which works as he explained.

Another way to visualise the transitions is in a graph like this:

AB
/
AC
/ \
/ \ /
AE BD
\ / \
BE CD
\ /
CE
\
DE

Well, it's obviously the same graph, but making it clear the foxes can only transition one step DOWN
the graph, or stay put - so the hunter just starts at the top and works down each level flushing the
foxes to the bottom of the graph.

Hmm, lots of possible variations - a single fox could have a 2-d grid of holes to move in, which is
much like 2 foxes with a 1-d grid but without the restriction that the fox must stay off the
diagonal (aka two foxes not fitting in one hole), and no restriction for directions. So how many
simultaneous guesses are needed to guarantee finding the fox? E.g. on 3x3 grid? (Seems 3 is easy,
2 not enough, but it reminds me of

The children's game "fox and geese" is essentially another variation of these puzzles, but the foxes
get their revenge playing the hunting role! :) In fox and geese, the target location (the goose)
is known and to balance the game the foxes have quite severe movement restrictions.

I suppose the John Conway's "Angel and Devils" problem also has similarities, but takes place on an
infinite grid.

<https://en.wikipedia.org/wiki/Angel_problem>

Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Edward Murphy@21:1/5 to henh...@gmail.com on Sun Jun 19 15:32:12 2022
On 6/12/2022 7:41 PM, henh...@gmail.com wrote:

it must be optimal in the sense that a 9-inspection answer is impossible.

That's a circular statement, but thinking about it some more, there
seems to be a simple proof of the latter:

* There are 10 pairs of holes, so by the pigeonhole principle, any
9-inspection answer must have at least one pair (call it XY) that
it ends up not checking. This remains true no matter what sort of
"if you see _____, then do _____" conditional logic is included.

* If they started in XY and stayed there the whole time, then that
9-inspection answer won't find both of them at once.

Thus 10 inspections are necessary, and (by previous construction)
also sufficient.

at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong because it was different from my answer. So now i'm wondering
how many answers are there ?

By the above, an optimal answer must be some permutation of all ten
pairs of holes, so upper bound is 10! = 3628800. But the converse isn't
true; a permutation of all ten pairs of holes isn't necessarily optimal,
and it's simple to construct an example (DE AB AC AD AE BC BD BE CD CE,
if they start in CE and then move to DE). I'd be curious to see a method
of determining the exact number, other than just exhaustive brute-force computer analysis.

----------- and ... Are all the answers equally good ?

No, e.g. checking AB twice in a row (then proceeding with the rest of
my previous solution) is guaranteed to finish within 11 days, but not
within 10 days (if they started in DE and stayed there the whole time).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From leflynn@21:1/5 to Edward Murphy on Sun Jun 19 19:34:44 2022
On Sunday, June 19, 2022 at 6:32:24 PM UTC-4, Edward Murphy wrote:
On 6/12/2022 7:41 PM, henh...@gmail.com wrote:

it must be optimal in the sense that a 9-inspection answer is impossible.
That's a circular statement, but thinking about it some more, there
seems to be a simple proof of the latter:

* There are 10 pairs of holes, so by the pigeonhole principle, any 9-inspection answer must have at least one pair (call it XY) that
it ends up not checking. This remains true no matter what sort of
"if you see _____, then do _____" conditional logic is included.

* If they started in XY and stayed there the whole time, then that 9-inspection answer won't find both of them at once.

Thus 10 inspections are necessary, and (by previous construction)
also sufficient.
at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong
because it was different from my answer. So now i'm wondering
how many answers are there ?
By the above, an optimal answer must be some permutation of all ten
pairs of holes, so upper bound is 10! = 3628800. But the converse isn't
true; a permutation of all ten pairs of holes isn't necessarily optimal,
and it's simple to construct an example (DE AB AC AD AE BC BD BE CD CE,
if they start in CE and then move to DE). I'd be curious to see a method
of determining the exact number, other than just exhaustive brute-force computer analysis.

I think Edward Murphy's graph
Another way to visualise the transitions is in a graph like this:

AB
/
AC
/ \
/ \ /
AE BD
\ / \
BE CD
\ /
CE
\
DE

Shows there are eight solutions.
You have to check both of the possibilities for levels with two choices
before you move to the next level but the order does not matter.

L. Flynn

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From leflynn@21:1/5 to Edward Murphy on Mon Jun 20 09:03:55 2022
On Sunday, June 19, 2022 at 6:32:24 PM UTC-4, Edward Murphy wrote:
On 6/12/2022 7:41 PM, henh...@gmail.com wrote:

it must be optimal in the sense that a 9-inspection answer is impossible.
That's a circular statement, but thinking about it some more, there
seems to be a simple proof of the latter:

* There are 10 pairs of holes, so by the pigeonhole principle, any 9-inspection answer must have at least one pair (call it XY) that
it ends up not checking. This remains true no matter what sort of
"if you see _____, then do _____" conditional logic is included.

* If they started in XY and stayed there the whole time, then that 9-inspection answer won't find both of them at once.

Thus 10 inspections are necessary, and (by previous construction)
also sufficient.
at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong
because it was different from my answer. So now i'm wondering
how many answers are there ?
By the above, an optimal answer must be some permutation of all ten
pairs of holes, so upper bound is 10! = 3628800. But the converse isn't
true; a permutation of all ten pairs of holes isn't necessarily optimal,
and it's simple to construct an example (DE AB AC AD AE BC BD BE CD CE,
if they start in CE and then move to DE). I'd be curious to see a method
of determining the exact number, other than just exhaustive brute-force computer analysis.
----------- and ... Are all the answers equally good ?
No, e.g. checking AB twice in a row (then proceeding with the rest of
my previous solution) is guaranteed to finish within 11 days, but not
within 10 days (if they started in DE and stayed there the whole time).

Somewhat brutish. You have to start AB AC and you have to end with CE DE,
so that eliminates quite a few. You can also build dependencies, e.g., you have to check AD before you check AE or BD. I found twelve by hand. In alphabetical order:
AB AC AD AE BC BD BE CD CE DE
AB AC AD AE BC BD CD BE CE DE
AB AC AD BC AE BD BE CD CE DE
AB AC AD BC AE BD CD BE CE DE
AB AC AD BC BD AE BE CD CE DE
AB AC AD BC BD AE CD BE CE DE
AB AC AD BC BD CD AE BE CE DE
AB AC BC AD AE BD BE CD CE DE
AB AC BC AD AE BD CD BE CE DE
AB AC BC AD BD AE BE CD CE DE
AB AC BC AD BD AE CD BE CE DE
AB AC BC AD BD CD AE BE CE DE
L. Flynn

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Richard Heathfield@21:1/5 to leflynn on Tue Jun 21 15:48:24 2022
On 20/06/2022 5:03 pm, leflynn wrote:
On Sunday, June 19, 2022 at 6:32:24 PM UTC-4, Edward Murphy wrote:
On 6/12/2022 7:41 PM, henh...@gmail.com wrote:

it must be optimal in the sense that a 9-inspection answer is impossible. >> That's a circular statement, but thinking about it some more, there
seems to be a simple proof of the latter:

* There are 10 pairs of holes, so by the pigeonhole principle, any
9-inspection answer must have at least one pair (call it XY) that
it ends up not checking. This remains true no matter what sort of
"if you see _____, then do _____" conditional logic is included.

* If they started in XY and stayed there the whole time, then that
9-inspection answer won't find both of them at once.

Thus 10 inspections are necessary, and (by previous construction)
also sufficient.
at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong
because it was different from my answer. So now i'm wondering
how many answers are there ?
By the above, an optimal answer must be some permutation of all ten
pairs of holes, so upper bound is 10! = 3628800. But the converse isn't
true; a permutation of all ten pairs of holes isn't necessarily optimal,
and it's simple to construct an example (DE AB AC AD AE BC BD BE CD CE,
if they start in CE and then move to DE). I'd be curious to see a method
of determining the exact number, other than just exhaustive brute-force
computer analysis.
----------- and ... Are all the answers equally good ?
No, e.g. checking AB twice in a row (then proceeding with the rest of
my previous solution) is guaranteed to finish within 11 days, but not
within 10 days (if they started in DE and stayed there the whole time).

Somewhat brutish. You have to start AB AC and you have to end with CE DE,
so that eliminates quite a few. You can also build dependencies, e.g., you have
to check AD before you check AE or BD. I found twelve by hand. In alphabetical order:
AB AC AD AE BC BD BE CD CE DE
AB AC AD AE BC BD CD BE CE DE
AB AC AD BC AE BD BE CD CE DE
AB AC AD BC AE BD CD BE CE DE
AB AC AD BC BD AE BE CD CE DE
AB AC AD BC BD AE CD BE CE DE
AB AC AD BC BD CD AE BE CE DE
AB AC BC AD AE BD BE CD CE DE
AB AC BC AD AE BD CD BE CE DE
AB AC BC AD BD AE BE CD CE DE
AB AC BC AD BD AE CD BE CE DE
AB AC BC AD BD CD AE BE CE DE

What you need is a shotgun.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Richard Harnden@21:1/5 to Richard Heathfield on Fri Jun 24 15:42:17 2022
On 21/06/2022 15:48, Richard Heathfield wrote:
On 20/06/2022 5:03 pm, leflynn wrote:
On Sunday, June 19, 2022 at 6:32:24 PM UTC-4, Edward Murphy wrote:
On 6/12/2022 7:41 PM, henh...@gmail.com wrote:

it must be optimal in the sense that a 9-inspection answer is
impossible.
That's a circular statement, but thinking about it some more, there
seems to be a simple proof of the latter:

* There are 10 pairs of holes, so by the pigeonhole principle, any
9-inspection answer must have at least one pair (call it XY) that
it ends up not checking. This remains true no matter what sort of
"if you see _____, then do _____" conditional logic is included.

* If they started in XY and stayed there the whole time, then that
9-inspection answer won't find both of them at once.

Thus 10 inspections are necessary, and (by previous construction)
also sufficient.
at first, i thought (AB AC AD AE BC BD BE CD CE DE) must be wrong
because it was different from my answer. So now i'm wondering
how many answers are there ?
By the above, an optimal answer must be some permutation of all ten
pairs of holes, so upper bound is 10! = 3628800. But the converse isn't
true; a permutation of all ten pairs of holes isn't necessarily optimal, >>> and it's simple to construct an example (DE AB AC AD AE BC BD BE CD CE,
if they start in CE and then move to DE). I'd be curious to see a method >>> of determining the exact number, other than just exhaustive brute-force
computer analysis.
----------- and ... Are all the answers equally good ?
No, e.g. checking AB twice in a row (then proceeding with the rest of
my previous solution) is guaranteed to finish within 11 days, but not
within 10 days (if they started in DE and stayed there the whole time).

Somewhat brutish.  You have to start AB AC and you have to end with CE
DE,
so that eliminates quite a few. You can also build dependencies, e.g.,
you have
to check AD before you check AE or BD. I found twelve by hand. In
alphabetical order:
AB AC AD AE BC BD BE CD CE DE
AB AC AD AE BC BD CD BE CE DE
AB AC AD BC AE BD BE CD CE DE
AB AC AD BC AE BD CD BE CE DE
AB AC AD BC BD AE BE CD CE DE
AB AC AD BC BD AE CD BE CE DE
AB AC AD BC BD CD AE BE CE DE
AB AC BC AD AE BD BE CD CE DE
AB AC BC AD AE BD CD BE CE DE
AB AC BC AD BD AE BE CD CE DE
AB AC BC AD BD AE CD BE CE DE
AB AC BC AD BD CD AE BE CE DE

What you need is a shotgun.

Dynamite. Did Caddy Shack teach us nothing?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Edward Murphy@21:1/5 to leflynn on Sun Jun 26 13:34:50 2022
On 6/20/2022 9:03 AM, leflynn wrote:

Somewhat brutish. You have to start AB AC and you have to end with CE DE,
so that eliminates quite a few. You can also build dependencies, e.g., you have
to check AD before you check AE or BD. I found twelve by hand. In alphabetical order:
AB AC AD AE BC BD BE CD CE DE
AB AC AD AE BC BD CD BE CE DE
AB AC AD BC AE BD BE CD CE DE
AB AC AD BC AE BD CD BE CE DE
AB AC AD BC BD AE BE CD CE DE
AB AC AD BC BD AE CD BE CE DE
AB AC AD BC BD CD AE BE CE DE
AB AC BC AD AE BD BE CD CE DE
AB AC BC AD AE BD CD BE CE DE
AB AC BC AD BD AE BE CD CE DE
AB AC BC AD BD AE CD BE CE DE
AB AC BC AD BD CD AE BE CE DE

Eight of these are the "check each tier in some order and move down"
approach from your previous post. The other four involve doing the
following at some point:

1) Check a pair on one tier, e.g. AD.

2) Check a pair on the next tier down, in this case AE, such that
the only way the foxes could have just moved there was from the
pair that you checked in step 1.

3) Check the other pair on the same tier as step 1.

4) Check the other pair on the same tier as step 2.

This could probably form the basis of an analytic proof that no other
optimal solutions exist, by ensuring that it's never possible for the
foxes to move into a pair that you already checked.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)