• 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
    AB AC AD AE

    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
    AB AC AD AE

    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
    AB AC AD AE

    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
    AB AC AD AE

    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
    / \
    AD BC
    / \ /
    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
    / \
    AD BC
    / \ /
    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)