Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: A game strategy.



Ludwik Kowalski wrote:
....
The question "what makes this problem so counterintuitive" is
worth asking.

Partial answers include:

1) This illustrates (much more so than the arch/cantilever
question) Jack's point that you can get into all sorts of
trouble if the problem is underspecified.
-- Does Monty act robotically (always opening a door)?
-- Does Monty act cooperatively (opening only if it helps you)?
-- Does Monty act maliciously (opening only if it misguides you)?

2) Many people have only rudimentary notions of information
theory and probability. The notions of information gain and
conditional probability are quite unfamiliar to many people.

Here's a more advanced problem that exercises the
same part of the brain:

Riddle (classic):
You are given 12 coins which are superficially identical.
But only 11 are really identical; the 12th is slightly
heavier or lighter. You are also given an old-fashioned
two-pan balance, which reports whether the contents of
the left pan are heavier, lighter, or the same as the
right pan. Your task is to identify the odd coin, and
to say whether it is lighter or heavier than the others.
The challenge is to do it in the minimum number of
weighings. What is the smallest number of times you
can employ the scale, and what is the algorithm?

Extra credit (possibly jsd original):
Design an _unordered_ algorithm for doing this task.
That is, you are not allowed to use the results of
the previous weighings when deciding which coins to
put in which pan of the balance. You can request the
weighing of whatever groups of coins you desire, but
the results of the weighings will not be disclosed
until after all weighings are complete.

I call this an "unordered" algorithm because the
requested weighings can be done in any order. The
algorithm I have in mind doesn't fully qualify as
a "parallel" algorithm, because some coins need to
be weighed more than once, and you can't do that
simultaneously (in parallel) using the specified
equipment.