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 ?
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.)
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.
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.
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 ?
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 wrongBy the above, an optimal answer must be some permutation of all ten
because it was different from my answer. So now i'm wondering
how many answers are there ?
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.
Another way to visualise the transitions is in a graph like this:
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 wrongBy the above, an optimal answer must be some permutation of all ten
because it was different from my answer. So now i'm wondering
how many answers are there ?
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).
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, thereseems 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 wrongBy the above, an optimal answer must be some permutation of all ten
because it was different from my answer. So now i'm wondering
how many answers are there ?
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
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 isThat's a circular statement, but thinking about it some more, there
impossible.
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 wrongBy the above, an optimal answer must be some permutation of all ten
because it was different from my answer. So now i'm wondering
how many answers are there ?
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.
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
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 322 |
Nodes: | 16 (0 / 16) |
Uptime: | 149:06:16 |
Calls: | 7,072 |
Calls today: | 1 |
Files: | 12,494 |
Messages: | 5,499,346 |