Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

When we talk of tomorrow, the gods laugh.


interests / rec.puzzles / Re: 2 foxes in 5 (adjacent) holes

SubjectAuthor
* 2 foxes in 5 (adjacent) holeshenh...@gmail.com
`* Re: 2 foxes in 5 (adjacent) holesEdward Murphy
 +* Re: 2 foxes in 5 (adjacent) holeshenh...@gmail.com
 |`* Re: 2 foxes in 5 (adjacent) holesEdward Murphy
 | +- Re: 2 foxes in 5 (adjacent) holesleflynn
 | `* Re: 2 foxes in 5 (adjacent) holesleflynn
 |  +* Re: 2 foxes in 5 (adjacent) holesRichard Heathfield
 |  |`- Re: 2 foxes in 5 (adjacent) holesRichard Harnden
 |  `- Re: 2 foxes in 5 (adjacent) holesEdward Murphy
 `* Re: 2 foxes in 5 (adjacent) holesPhil Carmody
  `- Re: 2 foxes in 5 (adjacent) holesMike Terry

1
2 foxes in 5 (adjacent) holes

<e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=146&group=rec.puzzles#146

 copy link   Newsgroups: rec.puzzles
X-Received: by 2002:ac8:4e4d:0:b0:304:febe:5b2 with SMTP id e13-20020ac84e4d000000b00304febe05b2mr3073282qtw.684.1654646783360;
Tue, 07 Jun 2022 17:06:23 -0700 (PDT)
X-Received: by 2002:a05:622a:14cf:b0:304:e935:6204 with SMTP id
u15-20020a05622a14cf00b00304e9356204mr13473793qtx.198.1654646783164; Tue, 07
Jun 2022 17:06:23 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: rec.puzzles
Date: Tue, 7 Jun 2022 17:06:22 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=2601:648:8601:3850:0:0:0:4335;
posting-account=YjTkGAoAAAA4_fbAISfvtIqrYbghMeBx
NNTP-Posting-Host: 2601:648:8601:3850:0:0:0:4335
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
Subject: 2 foxes in 5 (adjacent) holes
From: henha...@gmail.com (henh...@gmail.com)
Injection-Date: Wed, 08 Jun 2022 00:06:23 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1702
 by: henh...@gmail.com - Wed, 8 Jun 2022 00:06 UTC

(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

Re: 2 foxes in 5 (adjacent) holes

<t85mie$1rnk$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=147&group=rec.puzzles#147

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!aioe.org!SABVAYcHOklaNK/u1FQzwA.user.46.165.242.75.POSTED!not-for-mail
From: emurph...@zoho.com (Edward Murphy)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Sun, 12 Jun 2022 14:41:31 -0700
Organization: Aioe.org NNTP Server
Message-ID: <t85mie$1rnk$1@gioia.aioe.org>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="61172"; posting-host="SABVAYcHOklaNK/u1FQzwA.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.10.0
X-Notice: Filtered by postfilter v. 0.9.2
Content-Language: en-US
 by: Edward Murphy - Sun, 12 Jun 2022 21:41 UTC

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.

Re: 2 foxes in 5 (adjacent) holes

<311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=149&group=rec.puzzles#149

 copy link   Newsgroups: rec.puzzles
X-Received: by 2002:a05:622a:50d:b0:304:f438:c464 with SMTP id l13-20020a05622a050d00b00304f438c464mr27140065qtx.323.1655088106027;
Sun, 12 Jun 2022 19:41:46 -0700 (PDT)
X-Received: by 2002:a05:622a:1488:b0:304:f6e3:719e with SMTP id
t8-20020a05622a148800b00304f6e3719emr25214479qtx.64.1655088105892; Sun, 12
Jun 2022 19:41:45 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: rec.puzzles
Date: Sun, 12 Jun 2022 19:41:45 -0700 (PDT)
In-Reply-To: <t85mie$1rnk$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2601:648:8600:9ae0:0:0:0:2071;
posting-account=YjTkGAoAAAA4_fbAISfvtIqrYbghMeBx
NNTP-Posting-Host: 2601:648:8600:9ae0:0:0:0:2071
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com> <t85mie$1rnk$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
Subject: Re: 2 foxes in 5 (adjacent) holes
From: henha...@gmail.com (henh...@gmail.com)
Injection-Date: Mon, 13 Jun 2022 02:41:46 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2883
 by: henh...@gmail.com - Mon, 13 Jun 2022 02:41 UTC

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 ?

Re: 2 foxes in 5 (adjacent) holes

<877d5kfwi7.fsf@zotaspaz.fatphil.org>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=150&group=rec.puzzles#150

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED.85.253.101.128.cable.starman.ee!not-for-mail
From: pc+use...@asdf.org (Phil Carmody)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Mon, 13 Jun 2022 17:50:24 +0300
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <877d5kfwi7.fsf@zotaspaz.fatphil.org>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="85.253.101.128.cable.starman.ee:85.253.101.128";
logging-data="1592366"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
Cancel-Lock: sha1:Iw7eEPYbDfCf2zOXsmb0AUySMAo=
 by: Phil Carmody - Mon, 13 Jun 2022 14:50 UTC

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/

Re: 2 foxes in 5 (adjacent) holes

<QuidnfmIh75A-zr_nZ2dnUU7-QHNnZ2d@brightview.co.uk>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=151&group=rec.puzzles#151

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 13 Jun 2022 11:33:32 -0500
Subject: Re: 2 foxes in 5 (adjacent) holes
Newsgroups: rec.puzzles
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org> <877d5kfwi7.fsf@zotaspaz.fatphil.org>
From: news.dea...@darjeeling.plus.com (Mike Terry)
Date: Mon, 13 Jun 2022 17:33:34 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
MIME-Version: 1.0
In-Reply-To: <877d5kfwi7.fsf@zotaspaz.fatphil.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <QuidnfmIh75A-zr_nZ2dnUU7-QHNnZ2d@brightview.co.uk>
Lines: 93
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-KlLr1kzAGusHWZQ/aZK0q9lA8pXJf3XopSWQbfh5GRcvdhi8UJpX5QSWh0fpMgdQX2d2fkq3wnMZifR!Z86uKkzoZK2D6fZa2aecZAntUzUefljilgZxF5L/5s6u5yxrghRHX4eujT+88zn4HknyVwhZ6fiJ!mqMHnkJUbYvuTmBO6EprzJ3hA4A=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5264
 by: Mike Terry - Mon, 13 Jun 2022 16:33 UTC

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.

Re: 2 foxes in 5 (adjacent) holes

<t8o85j$dl4$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=180&group=rec.puzzles#180

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!aioe.org!SABVAYcHOklaNK/u1FQzwA.user.46.165.242.75.POSTED!not-for-mail
From: emurph...@zoho.com (Edward Murphy)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Sun, 19 Jun 2022 15:32:12 -0700
Organization: Aioe.org NNTP Server
Message-ID: <t8o85j$dl4$1@gioia.aioe.org>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org>
<311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="13988"; posting-host="SABVAYcHOklaNK/u1FQzwA.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.10.0
Content-Language: en-US
X-Notice: Filtered by postfilter v. 0.9.2
 by: Edward Murphy - Sun, 19 Jun 2022 22:32 UTC

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).

Re: 2 foxes in 5 (adjacent) holes

<7c585a30-f60c-40f8-8ff1-209ea105304an@googlegroups.com>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=192&group=rec.puzzles#192

 copy link   Newsgroups: rec.puzzles
X-Received: by 2002:a05:600c:501f:b0:39d:a3d:e919 with SMTP id n31-20020a05600c501f00b0039d0a3de919mr22344940wmr.132.1655692484737;
Sun, 19 Jun 2022 19:34:44 -0700 (PDT)
X-Received: by 2002:ac8:5fc1:0:b0:304:eaf1:52a with SMTP id
k1-20020ac85fc1000000b00304eaf1052amr17789650qta.656.1655692484271; Sun, 19
Jun 2022 19:34:44 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.87.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: rec.puzzles
Date: Sun, 19 Jun 2022 19:34:44 -0700 (PDT)
In-Reply-To: <t8o85j$dl4$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=108.51.169.131; posting-account=RY8SewoAAACVLxHkdczJqnZMQf-Svvk5
NNTP-Posting-Host: 108.51.169.131
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org> <311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
<t8o85j$dl4$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <7c585a30-f60c-40f8-8ff1-209ea105304an@googlegroups.com>
Subject: Re: 2 foxes in 5 (adjacent) holes
From: lefl...@hotmail.com (leflynn)
Injection-Date: Mon, 20 Jun 2022 02:34:44 +0000
Content-Type: text/plain; charset="UTF-8"
 by: leflynn - Mon, 20 Jun 2022 02:34 UTC

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

Re: 2 foxes in 5 (adjacent) holes

<c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=198&group=rec.puzzles#198

 copy link   Newsgroups: rec.puzzles
X-Received: by 2002:adf:e196:0:b0:219:f3c7:fd88 with SMTP id az22-20020adfe196000000b00219f3c7fd88mr24146222wrb.402.1655741036188;
Mon, 20 Jun 2022 09:03:56 -0700 (PDT)
X-Received: by 2002:ac8:7d05:0:b0:305:2a4b:d86b with SMTP id
g5-20020ac87d05000000b003052a4bd86bmr20182604qtb.234.1655741035726; Mon, 20
Jun 2022 09:03:55 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.87.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: rec.puzzles
Date: Mon, 20 Jun 2022 09:03:55 -0700 (PDT)
In-Reply-To: <t8o85j$dl4$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=108.51.169.131; posting-account=RY8SewoAAACVLxHkdczJqnZMQf-Svvk5
NNTP-Posting-Host: 108.51.169.131
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org> <311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
<t8o85j$dl4$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>
Subject: Re: 2 foxes in 5 (adjacent) holes
From: lefl...@hotmail.com (leflynn)
Injection-Date: Mon, 20 Jun 2022 16:03:56 +0000
Content-Type: text/plain; charset="UTF-8"
 by: leflynn - Mon, 20 Jun 2022 16:03 UTC

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

Re: 2 foxes in 5 (adjacent) holes

<t8slno$5gh$1@dont-email.me>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=202&group=rec.puzzles#202

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: rjh...@cpax.org.uk (Richard Heathfield)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Tue, 21 Jun 2022 15:48:24 +0100
Organization: Fix this later
Lines: 56
Message-ID: <t8slno$5gh$1@dont-email.me>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org>
<311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
<t8o85j$dl4$1@gioia.aioe.org>
<c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 21 Jun 2022 14:48:24 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="4349c8df9936e2e88ecbe1a81b32fbee";
logging-data="5649"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18A4BStq7zgx1tQf74FEgoIxkpHXsXZjHgwzoW905K8JA=="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.9.1
Cancel-Lock: sha1:7O/QpinnZ+irvz6AGUEVE4dzTsk=
In-Reply-To: <c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>
Content-Language: en-GB
 by: Richard Heathfield - Tue, 21 Jun 2022 14:48 UTC

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

Re: 2 foxes in 5 (adjacent) holes

<t94ig9$5jj$1@dont-email.me>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=213&group=rec.puzzles#213

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: richard....@gmail.com (Richard Harnden)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Fri, 24 Jun 2022 15:42:17 +0100
Organization: A noiseless patient Spider
Lines: 59
Message-ID: <t94ig9$5jj$1@dont-email.me>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org>
<311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
<t8o85j$dl4$1@gioia.aioe.org>
<c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>
<t8slno$5gh$1@dont-email.me>
Reply-To: nospam.harnden@gmail.com
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 24 Jun 2022 14:42:17 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="19d55d3735459e9cb3a7cd761fbbeb86";
logging-data="5747"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+up8L+SQJjGTZsuiuroU5HQjdeASYz8sw="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.10.0
Cancel-Lock: sha1:0w6ag1zHfRQA2ql22FWU2OoVXzI=
In-Reply-To: <t8slno$5gh$1@dont-email.me>
 by: Richard Harnden - Fri, 24 Jun 2022 14:42 UTC

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?

Re: 2 foxes in 5 (adjacent) holes

<t9aftb$1apn$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/interests/article-flat.php?id=218&group=rec.puzzles#218

 copy link   Newsgroups: rec.puzzles
Path: i2pn2.org!i2pn.org!aioe.org!SABVAYcHOklaNK/u1FQzwA.user.46.165.242.75.POSTED!not-for-mail
From: emurph...@zoho.com (Edward Murphy)
Newsgroups: rec.puzzles
Subject: Re: 2 foxes in 5 (adjacent) holes
Date: Sun, 26 Jun 2022 13:34:50 -0700
Organization: Aioe.org NNTP Server
Message-ID: <t9aftb$1apn$1@gioia.aioe.org>
References: <e8ce375c-3389-47e3-8c1a-2c2ff4f2f4b3n@googlegroups.com>
<t85mie$1rnk$1@gioia.aioe.org>
<311debd0-b903-4792-97b6-e427f4b0f8fen@googlegroups.com>
<t8o85j$dl4$1@gioia.aioe.org>
<c72d112a-fede-4e1e-8422-782cd8d871d9n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="43831"; posting-host="SABVAYcHOklaNK/u1FQzwA.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.10.0
Content-Language: en-US
X-Notice: Filtered by postfilter v. 0.9.2
 by: Edward Murphy - Sun, 26 Jun 2022 20:34 UTC

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.

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor