Monster Media 1994 #1/monster.zip/monster/TEXT/PUZZLE4.ZIP/LOGIC

Text File | 1994-04-05 | 216KB | 5,391 lines

Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (logic), part 22 of 35
Message-ID: <puzzles/archive/logic/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:06:09 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 1393
Xref: senator-bedfellow.mit.edu rec.puzzles:25006 news.answers:11526 rec.answers:1926

Archive-name: puzzles/archive/logic/part1
Last-modified: 17 Aug 1993
Version: 4


==> logic/29.p <==
Three people check into a hotel.  They pay $30 to the manager and go
to their room.  The manager finds out that the room rate is $25 and
gives $5 to the bellboy to return.  On the way to the room the bellboy
reasons that $5 would be difficult to share among three people so
he pockets $2 and gives $1 to each person.

Now each person paid $10 and got back $1.  So they paid $9 each,
totalling $27.  The bellboy has $2, totalling $29.

Where is the remaining dollar?

==> logic/29.s <==
Each person paid $9, totalling $27.  The manager has $25 and the bellboy $2.
The bellboy's $2 should be added to the manager's $25 or subtracted from
the tenants' $27, not added to the tenants' $27.

==> logic/ages.p <==
1) Ten years from now Tim will be twice as old as Jane was when Mary was
   nine times as old as Tim.

2) Eight years ago, Mary was half as old as Jane will be when Jane is one year
   older than Tim will be at the time when Mary will be five times as old as
   Tim will be two years from now.

3) When Tim was one year old, Mary was three years older than Tim will be when
   Jane is three times as old as Mary was six years before the time when Jane
   was half as old as Tim will be when Mary will be ten years older than Mary
   was when Jane was one-third as old as Tim will be when Mary will be three
   times as old as she was when Jane was born.

                             HOW OLD ARE THEY NOW?

==> logic/ages.s <==
The solution: Tim is 3, Jane is 8, and Mary is 15.  A little grumbling
is in order here, as clue number 1 leads to the situation a year and a
half ago, when Tim was 1 1/2, Jane was 6 1/2, and Mary was 13 1/2.

This sort of problem is easy if you write down a set of equations.  Let
t be the year that Tim was born, j be the year that Jane was born, m be
the year that Mary was born, and y be the current year.  As indefinite
years come up, let y1, y2, ... be the indefinite years.  Then the
equations are


y + 10 - t = 2 (y1 - j)
y1 - m = 9 (y1 - t)

y - 8 - m = 1/2 (y2 - j)
y2 - j = 1 + y3 - t
y3 - m = 5 (y + 2 - t)

t + 1 - m = 3 + y4 - t
y4 - j = 3 (y5 - 6 - m)
y5 - j = 1/2 (y6 - t)
y6 - m = 10 + y7 - m
y7 - j = 1/3 (y8 - t)
y8 - m = 3 (j - m)

t = y - 3
j = y - 8
m = y - 15

==> logic/attribute.p <==
All the items in the first list share a particular attribute.  The second
list is of some items lacking the attribute.

Set#1
    with:  battery, key, yeast, bookmark
    w/out: stapler, match, Rubik's cube, pill bottle

Set#2
    with:  Rubik's cube, chess set, electrical wiring, compass needle
    w/out: clock, rope, tic-tac-toe, pencil sharpener

Set#3:
    with:  koosh, small intestine, Yorkshire Terrier, Christmas Tree
    w/out: toothbrush, oak chair, soccer ball, icicle

Points to realize:
1.
 There may be exceptions to any item on the list, for instance a particular
 clock may share the properties of the 'with' list of problem two, BUT MOST
 ORDINARY clocks do not.  All the properties apply the vast majority of the
 the items mentioned.  Extraordinary exceptions should be ignored.

2.
 Pay the most attention to the 'with' list.  The 'without' list is only
 present to eliminate various 'stupid' answers.

==> logic/attribute.s <==
The attribute puzzle format is a traditional format in math education.
It occurs in logic materials developed in the sixties by EDC in Boston,
with visual objects. Example:

these are gloops: A B C D E
these are not gloops: F G J L N
which of these are gloops? O P Q R S

Set#1
    with:  battery, key, yeast, bookmark
    w/out: stapler, match, Rubik's cube, pill bottle

Needs to be placed inside something else when used for its usual purpose.

Set#2
    with:  Rubik's cube, chess set, electrical wiring, compass needle
    w/out: clock, rope, tic-tac-toe, pencil sharpener

Uses color to distinguish between otherwise identical parts.

Set#3:
    with:  koosh, small intestine, Yorkshire Terrier, Christmas Tree
    w/out: toothbrush, oak chair, soccer ball, icicle

Villiform.

==> logic/bookworm.p <==
A bookworm eats from the first page of an encyclopedia to the last
page.  The bookworm eats in a straight line.  The encyclopedia consists
of ten 1000-page volumes and is sitting on a bookshelf in the usual
order.  Not counting covers, title pages, etc., how many pages does the
bookworm eat through?

==> logic/bookworm.s <==
On a book shelf the first page of the first volume is on the "inside"
  __                             __
B|  |                           |  |F
A|1 |...........................|10|R
C|  |                           |  |O
K|  |                           |  |N
 |  |                           |  |T
  ----------------------------------
so the bookworm eats only through the cover of the first volume, then 8 times
1000 pages of Volumes 2 - 9, then through the cover to the 1st page of Vol 10.
He eats 8,000 pages.

If the bookworm ate the first page and the last page, it ate 8,004 pages.

==> logic/boxes.p <==
Which Box Contains the Gold?

Two boxes are labeled "A" and "B".  A sign on box A says "The sign
on box B is true and the gold is in box A".  A sign on box B says
"The sign on box A is false and the gold is in box A".  Assuming there
is gold in one of the boxes, which box contains the gold?

==> logic/boxes.s <==
The problem cannot be solved with the information given.

The sign on box A says "The sign on box B is true and the gold is in box A".
The sign on box B says "The sign on box A is false and the gold is in box A".
The following argument can be made: If the statement on box A is true, then
the statement on box B is true, since that is what the statement on box A
says.  But the statement on box B states that the statement on box A is false,
which contradicts the original assumption.  Therefore, the statement on box A
must be false.  This implies that either the statement on box B is false or
that the gold is in box B.  If the statement on box B is false, then either
the statement on box A is true (which it cannot be) or the gold is in box B.
Either way, the gold is in box B.

However, there is a hidden assumption in this argument: namely, that
each statement must be either true or false.  This assumption leads to
paradoxes, for example, consider the statement: "This statement is
false."  If it is true, it is false; if it is false, it is true.  The
only way out of the paradox is to deny that the statement is either true
or false and label it meaningless instead.  Both of the statements on the
boxes are therefore meaningless and nothing can be concluded from them.

In general, statements about the truth of other statements lead to
contradictions.  Tarski invented metalanguages to avoid this problem.
To avoid paradox, a statement about the truth of a statement in a language
must be made in the metalanguage of the language.

Common sense dictates that this problem cannot be solved with the information
given.  After all, how can we deduce which box contains the gold simply by
reading statements written on the outside of the box?  Suppose we deduce that
the gold is in box B by whatever line of reasoning we choose.  What is to stop
us from simply putting the gold in box A, regardless of what we deduced?
(cf. Smullyan, "What Is the Name of This Book?", Prentice-Hall, 1978,    #70)

==> logic/camel.p <==
An Arab sheikh tells his two sons to race their camels to a distant
city to see who will inherit his fortune.  The one whose camel is
slower will win.  The brothers, after wandering aimlessly for days, ask
a wise man for advise.  After hearing the advice they jump on the
camels and race as fast as they can to the city.  What does the wise
man say?

==> logic/camel.s <==
The wiseman tells them to switch camels.

==> logic/centrifuge.p <==
You are a biochemist, working with a 12-slot centrifuge.  This is a gadget
that has 12 equally spaced slots around a central axis, in which you can
place chemical samples you want centrifuged.  When the machine is turned on,
the samples whirl around the central axis and do their thing.

To ensure that the samples are evenly mixed, they must be distributed in the
12 slots such that the centrifuge is balanced evenly.  For example, if you
wanted to mix 4 samples, you could place them in slots 12, 3, 6 and 9
(assuming the slots are numbered from 1 to 12 like a clock).

Problem:  Can you use the centrifuge to mix 5 samples?

==> logic/centrifuge.s <==
The superposition of any two solutions is yet another solution, so given
that the factors > 1 of 12 (2, 3, 4, 6, 12) are all solutions, the
only thing to check about, for example, the proposed solution 2+3 is
that not all ways of combining 2 & 3 would have centrifuge tubes
from one subsolution occupying the slot for one of the tubes in
another solution.  For the case 2+3, there is no problem:  Place 3
tubes, one in every 4th position, then place the 4th and 5th
diametrically opposed (each will end up in a slot adjacent to one of
the first 3 tubes).  The obvious generalization is, what are the
numbers of tubes that cannot be balanced?  Observing that there are
solutions for 2,3,4,5,6 tubes and that if X has a solution, 12-X has
also one (obtained by swapping tubes and holes), it is obvious that
1 and 11 are the only cases without solutions.

Here is how this problem is often solved in practice:  A dummy tube
is added to produce a total number of tubes that is easy to balance.
For example, if you had to centrifuge just one sample, you'd add a
second tube opposite it for balance.

==> logic/chain.p <==
What is the least number of links you can cut in a chain of 21 links to be able
to give someone all possible number of links up to 21?

==> logic/chain.s <==
Two.

    OOO C OOOOO C OOOOOOOOOOO
(where Os are chained unbroken links, and the Cs are the unchained broken links)

And equivalently:

    OOO C OOOOOO C OOOOOOOOOO

==> logic/children.p <==
A man walks into a bar, orders a drink, and starts chatting with the
bartender.  After a while, he learns that the bartender has three
children.  "How old are your children?" he asks.  "Well," replies the
bartender, "the product of their ages is 72."  The man thinks for a
moment and then says, "that's not enough information."  "All right,"
continues the bartender, "if you go outside and look at the building
number posted over the door to the bar, you'll see the sum of the
ages."  The man steps outside, and after a few moments he reenters and
declares, "Still not enough!"  The bartender smiles and says, "My
youngest just loves strawberry ice cream."

How old are the children?

A variant of the problem is for the sum of the ages to be 13 and the
product of the ages to be the number posted over the door.  In this
case, it is the oldest that loves ice cream.

Then how old are they?


==> logic/children.s <==
First, determine all the ways that three ages can multiply together to get 72:

72  1  1        (quite a feat for the bartender)
36  2  1
24  3  1
18  4  1
18  2  2
12  6  1
12  3  2
9  4  2
9  8  1
8  3  3
6  6  2
6  4  3

As the man says, that's not enough information; there are many possibilities.
So the bartender tells him where to find the sum of the ages--the man now knows
the sum even though we don't.  Yet he still insists that there isn't enough
info.  This must mean that there are two permutations with the same sum;
otherwise the man could have easily deduced the ages.

The only pair of permutations with the same sum are 8 3 3 and 6 6 2, which both
add up to 14 (the bar's address).  Now the bartender mentions his
"youngest"--telling us that there is one child who is younger than the other
two.  This is impossible with 8 3 3--there are two 3 year olds.  Therefore the
ages of the children are 6, 6, and 2.

Pedants have objected that the problem is insoluble because there could be
a youngest between two three year olds (even twins are not born exactly at
the same time).  However, the word "age" is frequently used to denote the
number of years since birth.  For example, I am the same age as my wife,
even though technically she is a few months older than I am.  And using the
word "youngest" to mean "of lesser age" is also in keeping with common parlance.
So I think the solution is fine as stated.

In the sum-13 variant, the possibilities are:

11  1  1
10  2  1
9  3  1
9  2  2
8  4  1
8  3  2
7  5  1
7  4  2
7  3  3
6  6  1
6  5  2
6  4  3

The two that remain are 9 2 2 and 6 6 1 (both products equal 36).  The
final bit of info (oldest child) indicates that there is only one
child with the highest age.  This cancels out the 6 6 1 combination, leaving
the childern with ages of 9, 2, and 2.

==> logic/condoms.p <==
How can a man have mutually safe sex with three women with only two condoms?
How can three men have mutually safe sex with one woman with two condoms?

==> logic/condoms.s <==
Use both condoms on the first woman.  Take off the outer condom (turning it
inside-out in the process) and set it aside.  Use the inner condom alone on
the second woman.  Put the outer condom back on.  Use it on the third woman.

First man uses both condoms.  Take off the outer condom (do NOT reverse
it) and have second man use it.  First man takes off the inner condom
(turning it inside-out).  Third man puts on this condom, followed by
second man's condom.

==> logic/dell.p <==
How can I solve logic puzzles (e.g., as published by Dell) automatically?

==> logic/dell.s <==
#include    <setjmp.h>

#define    EITHER        if (S[1] = S[0], ! setjmp((S++)->jb)) {
#define    OR        } else EITHER
#define    REJECT        longjmp((--S)->jb, 1)
#define    END_EITHER    } else REJECT;

/* values in tmat: */
#define    T_UNK    0
#define    T_YES    1
#define    T_NO    2

#define    Val(t1,t2)    (S->tmat[t1][t2])
#define    CLASS(x)        \
        (((x) / NUM_ITEM) * NUM_ITEM)
#define    EVERY_TOKEN(x)        \
        (x = 0; x < TOT_TOKEN; x++)
#define    EVERY_ITEM(x, class)    \
        (x = CLASS(class); x < CLASS(class) + NUM_ITEM; x++)

#define    BEGIN                        \
struct state {                        \
    char    tmat[TOT_TOKEN][TOT_TOKEN];        \
    jmp_buf jb;                    \
} States[100], *S = States;                \
                            \
main()                            \
{                            \
    int    token;                    \
                            \
    for EVERY_TOKEN(token)                \
        yes(token, token);            \
    EITHER

/* Here is the problem-specific data */
#define    NUM_ITEM    5
#define    NUM_CLASS    6
#define    TOT_TOKEN    (NUM_ITEM * NUM_CLASS)

#define    HOUSE_0        0
#define    HOUSE_1        1
#define    HOUSE_2        2
#define    HOUSE_3        3
#define    HOUSE_4        4

#define    ENGLISH        5
#define    SPANISH        6
#define    NORWEG        7
#define    UKRAIN        8
#define    JAPAN        9

#define    GREEN        10
#define    RED        11
#define    IVORY        12
#define    YELLOW        13
#define    BLUE        14

#define    COFFEE        15
#define    TEA        16
#define    MILK        17
#define    OJUICE        18
#define    WATER        19

#define    DOG        20
#define    SNAIL        21
#define    FOX        22
#define    HORSE        23
#define    ZEBRA        24

#define    OGOLD        25
#define    PLAYER        26
#define    CHESTER        27
#define    LSTRIKE        28
#define    PARLIA        29

char *names[] = {
    "HOUSE_0", "HOUSE_1", "HOUSE_2", "HOUSE_3", "HOUSE_4",
    "ENGLISH", "SPANISH", "NORWEG", "UKRAIN", "JAPAN",
    "GREEN", "RED", "IVORY", "YELLOW", "BLUE",
    "COFFEE", "TEA", "MILK", "OJUICE", "WATER",
    "DOG", "SNAIL", "FOX", "HORSE", "ZEBRA",
    "OGOLD", "PLAYER", "CHESTER", "LSTRIKE", "PARLIA",
};

    BEGIN

    yes(ENGLISH, RED);    /* Clue 1 */
    yes(SPANISH, DOG);    /* Clue 2 */
    yes(COFFEE, GREEN);    /* Clue 3 */
    yes(UKRAIN, TEA);    /* Clue 4 */

    EITHER            /* Clue 5 */
        yes(IVORY, HOUSE_0);
        yes(GREEN, HOUSE_1);
    OR
        yes(IVORY, HOUSE_1);
        yes(GREEN, HOUSE_2);
    OR
        yes(IVORY, HOUSE_2);
        yes(GREEN, HOUSE_3);
    OR
        yes(IVORY, HOUSE_3);
        yes(GREEN, HOUSE_4);
    END_EITHER

    yes(OGOLD, SNAIL);    /* Clue 6 */
    yes(PLAYER, YELLOW);    /* Clue 7 */
    yes(MILK, HOUSE_2);    /* Clue 8 */
    yes(NORWEG, HOUSE_0);    /* Clue 9 */

    EITHER            /* Clue 10 */
        yes(CHESTER, HOUSE_0);
        yes(FOX, HOUSE_1);
    OR
        yes(CHESTER, HOUSE_4);
        yes(FOX, HOUSE_3);
    OR
        yes(CHESTER, HOUSE_1);
        EITHER    yes(FOX, HOUSE_0);
        OR    yes(FOX, HOUSE_2);
        END_EITHER
    OR
        yes(CHESTER, HOUSE_2);
        EITHER    yes(FOX, HOUSE_1);
        OR    yes(FOX, HOUSE_3);
        END_EITHER
    OR
        yes(CHESTER, HOUSE_3);
        EITHER    yes(FOX, HOUSE_2);
        OR    yes(FOX, HOUSE_4);
        END_EITHER
    END_EITHER

    EITHER            /* Clue 11 */
        yes(PLAYER, HOUSE_0);
        yes(HORSE, HOUSE_1);
    OR
        yes(PLAYER, HOUSE_4);
        yes(HORSE, HOUSE_3);
    OR
        yes(PLAYER, HOUSE_1);
        EITHER    yes(HORSE, HOUSE_0);
        OR    yes(HORSE, HOUSE_2);
        END_EITHER
    OR
        yes(PLAYER, HOUSE_2);
        EITHER    yes(HORSE, HOUSE_1);
        OR    yes(HORSE, HOUSE_3);
        END_EITHER
    OR
        yes(PLAYER, HOUSE_3);
        EITHER    yes(HORSE, HOUSE_2);
        OR    yes(HORSE, HOUSE_4);
        END_EITHER
    END_EITHER

    yes(LSTRIKE, OJUICE);    /* Clue 12 */
    yes(JAPAN, PARLIA);    /* Clue 13 */

    EITHER            /* Clue 14 */
        yes(NORWEG, HOUSE_0);
        yes(BLUE, HOUSE_1);
    OR
        yes(NORWEG, HOUSE_4);
        yes(BLUE, HOUSE_3);
    OR
        yes(NORWEG, HOUSE_1);
        EITHER    yes(BLUE, HOUSE_0);
        OR    yes(BLUE, HOUSE_2);
        END_EITHER
    OR
        yes(NORWEG, HOUSE_2);
        EITHER    yes(BLUE, HOUSE_1);
        OR    yes(BLUE, HOUSE_3);
        END_EITHER
    OR
        yes(NORWEG, HOUSE_3);
        EITHER    yes(BLUE, HOUSE_2);
        OR    yes(BLUE, HOUSE_4);
        END_EITHER
    END_EITHER

/* End of problem-specific data */

        solveit();
    OR
        printf("All solutions found\n");
        exit(0);
    END_EITHER
}

no(a1, a2)
{
    int    non1, non2, token;

    if (Val(a1, a2) == T_YES)
        REJECT;
    else if (Val(a1, a2) == T_UNK) {
        Val(a1, a2) = T_NO;
        no(a2, a1);
        non1 = non2 = -1;

        for EVERY_ITEM(token, a1)
            if (Val(token, a2) != T_NO)
                if (non1 == -1)
                    non1 = token;
                else
                    break;
        if (non1 == -1)
            REJECT;
        else if (token == CLASS(a1) + NUM_ITEM)
            yes(non1, a2);

        for EVERY_TOKEN(token)
            if (Val(token, a1) == T_YES)
                no(a2, token);
    }
}

yes(a1, a2)
{
    int    token;

    if (Val(a1, a2) == T_NO)
        REJECT;
    else if (Val(a1, a2) == T_UNK) {
        Val(a1, a2) = T_YES;
        yes(a2, a1);
        for EVERY_ITEM(token, a1)
            if (token != a1)
                no(token, a2);
        for EVERY_TOKEN(token)
            if (Val(token, a1) == T_YES)
                yes(a2, token);
            else if (Val(token, a1) == T_NO)
                no(a2, token);
    }
}

solveit()
{
    int    token, tok2;

    for EVERY_TOKEN(token)
        for (tok2 = token; tok2 < TOT_TOKEN; tok2++)
            if (Val(token, tok2) == T_UNK) {
                EITHER
                    yes(token, tok2);
                OR
                    no(token, tok2);
                END_EITHER;
                return solveit();
            }
    printf("Solution:\n");
    for EVERY_ITEM(token, 0) {
        for (tok2 = NUM_ITEM; tok2 < TOT_TOKEN; tok2++)
            if (Val(token, tok2) == T_YES)
                printf("\t%s %s\n",names[token],names[tok2]);
        printf("\n");
    }
    REJECT;
}

---
[e-mail] (James Allen)

==> logic/elimination.p <==
97 baseball teams participate in an annual state tournament.
The way the champion is chosen for this tournament is by the same old
elimination schedule. That is, the 97 teams are to be divided into
pairs, and the two teams of each pair play against each other.
After a team is eliminated from each pair, the winners would
be again divided into pairs, etc.  How many games must be played
to determine a champion?

==> logic/elimination.s <==
In order to determine a winner all but one team must lose.
Therefore there must be at least 96 games.

==> logic/flip.p <==
How can a toss be called over the phone (without requiring trust)?

==> logic/flip.s <==
A flips a coin.  If the result is heads, A multiplies 2 prime numbers
containing about 90 digits; if the result is tails, A multiplies 3
prime numbers containing about 60 digits.  A tells B the result of the
multiplication.  B now calls either heads or tails and tells A.  A then
supplies B with the original numbers to verify the flip.

Consider what is involved in multiplying 90 digit numbers.  Using the method
of long multiplication that we all learned in grade school, you have maybe
90 or so strings of 90 characters (or "digits") each.  That's no problem for
a computer to deal with.  The magnitude of the number represented isn't
much of a factor; we're only manipulating the string of digits.

Consider what is involved in factoring 90 digit numbers.  There are of course,
little tricks for determining factorability by small integers which we all
learned in grade school.  (Is the last digit even?  Is the sum of all the
digits divisible by 9?  And so on.)  But these are of little use in factoring
large numbers with large factors.  In fact, there is no essentially better
method than checking every number smaller that the number to be factored and
seeing if it one divides the other evenly.  We means we could be checking some
100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
nummbers.  This is very hard to do, even for a supercomputer.  Here, the
number of digits this number has is of little consequence.  It is the
magnitude of the number that we have to worry about, and there just isn't
enough time in the world to do this properly.

Where does A find a list of 60- and 90- digit prime numbers?  Well, that's not
to hard to come by.  The simplest method to find a few prime numbers is simply
to choose a 90-digit number (or 60-digit number, as the case warrants)
randomly, and check to see if it is prime.  You won't have to wait too long
before you stumble across a prime number.

"But wait!" you cry.  "I thought you just said it was incredibly difficult
to factor large numbers.  If that's the case, then how are you going to know
if the number you randomly choose is prime?"  A good question.  Here we enter
into the strange an wacky world of number theory.  It turns out (and I won't
explain how unless someone asks) there are "probabalistic" algorithms,
which depend on us choosing numbers at random.  There are probablistic
algorithms that when given a prime number, will quickly tell us that it is
a prime number, and when given a composite number, will either tell us that
it is a composite number (with very, very high probability) or will tell us
that it is a prime number (with very, very low probability.)  What's the use
of an algorithm that only returns the right answer "with very, very high
probability?"  Well, we can make this probability as high as we want, just by
running the algorithm longer.  In fact, it is within our technological
abilities to quickly run this algorithm for 90-digit numbers so that the
probability of it giving a wrong answer is less than the probability of a
cosmic ray striking a vital part of the computer at some vital time and causing
the computer to spit out the wrong answer anyway.  That's what I mean by "very,
very high."

==> logic/flowers.p <==
How many flowers do I have if all of them are roses except two, all of
them are tulips except two, and all of them are daisies except two?

==> logic/flowers.s <==
There are two solutions:

Three flowers: rose, tulip, daisy
Two flowers:   carnation, geranium

==> logic/friends.p <==
Any group of 6 or more contains either 3 mutual friends or 3 mutual strangers.
Prove it.

==> logic/friends.s <==
Take a person X.  Of the five other people, there must either be at least three
acquaintances of X or at least three strangers of X.  Assume wlog that X has
three strangers A,B,C.  Unless A,B,C is the required triad of acquaintances,
they must include a pair of strangers, wlog A,B.  Then X,A,B is the required
triad of strangers, QED.

==> logic/hofstadter.p <==
In first-order logic, find a predicate P(x) which means "x is a power of 10."

==> logic/hofstadter.s <==
Well, one summer, I decided to tackle the problem. Not having any great
knowledge of number theory, I used a more brute force approach. Note
that for greater comprehensibility, I have broken the resulting formula
up into several stages, but it would not be difficult to put it
back together into one vast formula:

{e is prime:}
PRIME(e) :=
   ~Eb:Ec:((b+2)*(c+2) = e)

{if e is a prime, true iff a is a power of e:}
PPOWER(a,e) :=
   Ab:Ac:((b*c = a) -> ((b = 1) or (Ed: (e*d) = b)))

{if e is a prime, and a is a power of e, true iff d is the
 (log_e a)th digit (counting from the right, starting with 0)
 in the base-e expansion of n:}
DIG(a,e,d,n) :=
   (d < e) & Eb:Ec:((c < a) & (n = (b*e*a) + (d*a) + c))

{if e is prime, and a is a power of e, true iff n has exactly
 (log_e a) digits in its base-e expansion (0 is counted as having 0
 digits:}
LENGTH(e,a,n):=
   (n < a) & Ab:((PPOWER(b,e) & (b < a)) -> (b <= n))

POWER_OF_TEN(x):=
   Ee:(PRIME(e) & (e > x) &
       En:Ea:(LENGTH(e,a,n) &
              DIG(1,e,1,n) &
              Ai:Aj:Au:(  (PPOWER(u,e) & ((e*u) < a)
               & DIG(u,e,i,n) & DIG(e*u,e,j,n))
                          -> j = (10 * i)  ) &
              Eu:(PPOWER(u,e) & (e*u = a) & DIG(u,e,x,n))
       )     )

The basic idea is that you are asserting that for some prime e greater
than x, we can find a number n which, when expressed in base-e notation,
will have 1 in its units place, 10 in its e's place, 100 in its (e^2)'s
place, and in general have the "digit" in each place be 10 times
greater than the one to its right, such that the leftmost digit is our x.

To translate into Hofstadter's notation, of course, we must use horse-shoes
instead of ->'s, big carets instead of &'s, letters a through e (followed
by however many ''s) exclusively, and so forth. (We must also replace <'s
and <= with appropriate expansions, and substitute in for our capitalized
formula abbreviations.) This is left as an exercise to the reader.

Kevin Wald
[e-mail]

==> logic/hundred.p <==
A sheet of paper has statements numbered from 1 to 100.  Statement n says
"exactly n of the statements on this sheet are false."  Which statements are
true and which are false?  What if we replace "exactly" by "at least"?

==> logic/hundred.s <==
From _Litton's Problematical Recreations_

It is tempting to argue as follows:

At most one statement can be true (they are mutually contradictory).
If they are all false, statement 100 would be true, which is no good.
So 99 are false, and statement 99 is true.

If replaced by "at least", and the "real" number of false statements is
x, then statements x+1 to 100 will be false (since they falsely claim
that there are more false statements than there actually are). So, 100-x are
false, ie.  x=100-x, so x=50. The first 50 statements are true, and statements
51 to 100 are false.

However, there is a hidden and incorrect assumption in this argument.
To see this, suppose that there is one statement on the sheet and it
says "One statement is false"  or "At least one statement is false,"
either way it implies "this statement is false," which is a familiar
paradoxical statement.  We have learned that this paradox arises because
of the false assumption that all statements are either true or false.
This is the hidden assumption in the above reasoning.

If it is acknowledged that some of the statements on the page may be
neither true nor false (i.e., meaningless), then nothing whatsoever can
be concluded about which statements are true or false.

This problem has been carefully contrived to appear to be solvable (like
the vacuous statement "this statement is true").  By changing the
numbers in some statements and changing "true" to "false," various
circular forms of the liar's paradox can be constructed.  A much
more complicated version of the same problem is:

 1) At least one of the last two statements in this list is true.

 2) This is either the first true or the first false statement in the
    list.

 3) There exist three consecutive false statements.

 4) The difference beween the numbers of the last true statement and
    the first true statement is a factor of the unknown number.

 5) The sum of the numbers of the true statements is the unknown
    number.

 6) This is not the last true statement.

 7) Each true statement's number is a factor of the unknown number.

 8) The unknown number equals the percentage of these statements which
   are true.

 9) The number of different factors which the unknown number has
   (excluding 1 and itself) is more than the sum of the numbers of the
   true statements.

10) There are no three cosecutive true statements.

What is the number?

The incorrect but plausible solution is:

By 2, either way 1 must be false, and then so must both 9 and 10.

6, if false, says "This is the last true statement", which gives
a paradox, thus 6 must be true, and so must 7 and/or 8.

7 and 8 cannot both be true, as the number had to be a multiple
of 6,7,8 , that is a multiple of 168 (by 7), and less than 100 (by 8)

If 8 is false, then 3 is true (8,9,10 is false), if 8 is true, then
3 is false (3 cannot be true when both 6 and 8 are true, then there
are no three consecutive statements left).

So we have either

A) F X F X X T F T F F
or
B) F X T X X T T F F F

In A), 4 and 5 must be true (by false 10), and 2 may be true or false.
So by 5 the number shall be either 27 (2+3+4+5+6+7) or 25 (3+4+5+6+7).
None of these can fullfill 8, though, so A) is out leaving us with B)

Now, (by 7) 3,6 and 7 are factors, the number must be a multiple of
42, as 2+3+4+5+6+7=27, 5 must be false.

By false 10, 2 and 4 must be true, that is 5 shall be a multiple
of the number. Now the number must be a multiple of 2,3,4,5,6 and 7,
that is a multiple of 3*4*5*7=420. 420 has 22 different factors
(2,3,4,5,6,7,10,12,14,15,20,21,28,30,35,42,60,70,84,105,140,210)
and the sum 2+3+4+6+7 = 22, so the only multiple of 420 that
fulfills false 9 is 420.

==> logic/inverter.p <==
Can a digital logic circuit with two inverters invert N independent inputs?
The circuit may contain any number of AND or OR gates.

==> logic/inverter.s <==
It can be shown that N inverters can invert 2^N-1 independent inputs,
given an unlimited supply of AND and OR gates. The classic version of
this puzzle is to invert 3 independent inputs using AND gates, OR
gates, and only 2 inverters.

This is solved by:
        n1 = not(i1 and i2 or i1 and i3 or i2 and i3);
        n2 = not((i1 or i2 or i3) and n1  or  i1 and i2 and i3);
        o1 = (i2 or i3 or n2) and n1  or  i2 and i3 and n2;
        o2 = (i1 or i3 or n2) and n1  or  i1 and i3 and n2;
        o3 = (i1 or i2 or n2) and n1  or  i1 and i2 and n2;

i1, i2, and i3 are the inputs, n1 and n2 are the inverted signals, and
o1, o2, and o3 are the outputs.  "and" has higher precedence than "or".

So, start with N inverters.  Replace 3 of them with 2.
Keep doing that until you're down to 2 inverters.

I was skeptical at first, because such a design requires so much feedback
that I was sure the system would oscillate when switching between two
particular states.  But after writing a program to test every possible state
change (32^2), it appears that this system settles after a maximum of
3 feedback logic iterations. I did not include gate delays in the simulation,
however, which could increase the number of iterations before the system
settles.

In any case, it appears that the world needs only 2 inverters! :-)

==> logic/josephine.p <==
The recent expedition to the lost city of Atlantis discovered scrolls
attributted to the great poet, scholar, philosopher Josephine. They
number eight in all, and here is the first.

THE KINGDOM OF MAMAJORCA, WAS RULED BY QUEEN HENRIETTA I. IN MAMAJORCA
WOMEN HAVE TO PASS AN EXTENSIVE LOGIC EXAM BEFORE THEY ARE ALLOWED TO
GET MARRIED. QUEENS DO NOT HAVE TO TAKE THIS EXAM. ALL THE WOMEN IN
MAMAJORCA ARE LOYAL TO THEIR QUEEN AND DO WHATEVER SHE TELLS THEM TO.
THE QUEENS OF MAMAJORCA ARE TRUTHFUL. ALL SHOTS FIRED IN MAMAJORCA CAN
BE HEARD IN EVERY HOUSE. ALL ABOVE FACTS ARE KNOWN TO BE COMMON
KNOWLEDGE.

HENRIETTA WAS WORRIED ABOUT THE INFIDELITY OF THE MARRIED MEN IN
MAMAJORCA.  SHE SUMMONED ALL THE WIVES TO THE TOWN SQUARE, AND MADE
THE FOLLOWING ANNOUNCEMENT. "THERE IS AT LEAST ONE UNFAITHFUL HUSBAND
IN MAMAJORCA. ALL WIVES KNOW WHICH HUSBANDS ARE UNFAITHFUL, BUT HAVE
NO KNOWLEDGE ABOUT THE FIDELITY OF THEIR OWN HUSBAND. YOU ARE
FORBIDDEN TO DISCUSS YOUR HUSBAND'S FAITHFULNESS WITH ANY OTHER WOMAN.
IF YOU DISCOVER THAT YOUR HUSBAND IS UNFAITHFUL, YOU MUST SHOOT HIM AT
PRECISELY MIDNIGHT OF THE DAY YOU FIND THAT OUT."

THIRTY-NINE SILENT NIGHTS FOLLOWED THE QUEEN'S ANNOUNCEMENT. ON THE
FORTIETH NIGHT, SHOTS WERE HEARD. QUEEN HENRIETTA I IS REVERED IN
MAMAJORCAN HISTORY.

As with all philosophers Josephine doesn't provide the question, but leaves
it implicit in his document. So figure out the questions - there are two -
and answer them.

Here is Josephine's second scroll.

QUEEN HENRIETTA I WAS SUCCEEDED BY DAUGHTER QUEEN HENRIETTA II. AFTER
A WHILE HENRIETTA LIKE HER FAMOUS MOTHER BECAME WORRIED ABOUT THE
INFIDELITY PROBLEM. SHE DECIDED TO ACT, AND SENT A LETTER TO HER
SUBJECTS (WIVES) THAT CONTAINED THE EXACT WORDS OF HENRIETTA I'S
FAMOUS SPEECH.  SHE ADDED THAT THE LETTERS WERE GUARENTEED TO REACH
ALL WIVES EVENTUALLY.

QUEEN HENRIETTA II IS REMEMBERED AS A FOOLISH AND UNJUST QUEEN.

What is the question and answer implied by this scroll?

==> logic/josephine.s <==
The two questions for scroll #1 were:

1. How many husbands were shot on that fateful night?
2. Why is Queen Henrietta I revered in Mamajorca?

The answers are:

If there are n unfaithful husbands (UHs), every wife of an UH knows of
n-1 UH's while every wife of a faithful husband knows of n UHs.  [this
because everyone has perfect information about everything except the
fidelity of their own husband].  Now we do a simple induction: Assume
that there is only one UH.  Then all the wives but one know that there
is just one UH, but the wife of the UH thinks that everyone is
faithful.  Upon hearing that "there is at least one UH", the wife
realizes that the only husband it can be is her own, and so shoots
him.  Now, imagine that there are just two UH's.  Each wife of an UH
assumes that the situation is "only one UH in town" and so waits to
hear the other wife (she knows who it is, of course) shoot her husband
on the first night.  When no one is shot, that can only be because her
OWN husband was a second UH.  The wife of the second UH makes the same
deduction when no shot is fired the first night (she was waiting, and
expecting the other to shoot, too).  So they both figure it out after
the first night, and shoot their husbands the second night.  It is
easy to tidy up the induction to show that the n UHs will all be shot
just on the n'th midnight.

The question for scroll #2 is:

3. Why is Queen Henrietta II not?

The answer is:

The problem now is that QHII didn't realize that it is *critical* that
all of the wives, of faithful and UH's alike, to
*BEGIN*AT*THE*SAME*MOMENT*.  The uncertainty of having a particular
wife's notice come a day or two late makes the whole logic path fall
apart.  That's why she's foolish.  She is unjust, because some wives,
honed and crack logicians all, remember, will *incorrectly* shoot
faithful husbands.  Let us imagine the situation with just a SINGLE UH
in the whole country.  And, wouldn't you know it, the notice to the
wife of the UH just happens to be held up a day, whereas everyone
else's arrived the first day.  Now, all of the wives that got the
notice the first day know that there is just one UH in the country.
And they know that the wife of that UH will think that everyone is
faithful, and so they'll expect her to figure it out and shoot her
husband the first night.  BUT SHE DIDN"T GET THE NOTICE THE FIRST
NIGHT....  BUT THE OTHER WIVES HAVE NO WAY OF KNOWING THAT.  So, the
wife of the UH doesn't know that anything is going on and so (of
course) doesn't do anything the first night.  The next day she gets
the notice, figures it all out, and her husband will be history come
that midnight.  BUT... *every* other wife thought that there should
have been a shooting the first night, and since there wasn't there
must have been an additional UH, and it can only have been _her_
husband.  So on the second night **ALL** of the husbands are shot.
Things are much more complicated if the mix of who gets the notice
when is less simple than the one I mentioned above, but it is always
wrong and/or tragic.

NOTE: if the wives *know* that the country courier service (or however
these things get delivered) is flaky, then they can avoid the
massacre, but unless the wives exchange notes no one will ever be shot
(since there is always a chance that rather than _your_ husband being
an UH, you could reason that it might be that the wife of one of the
UH's that you know about just hasn't gotten her copy of the scroll
yet).  I guess you could call this case "unjust", too, since the UH's
evade punishment, despite the perfect logic of the wives.

==> logic/locks.and.boxes.p <==
You want to send a valuable object to a friend.  You have a box which
is more than large enough to contain the object.  You have several
locks with keys.  The box has a locking ring which is more than large enough
to have a lock attached.  But your friend does not have the key to any
lock that you have.  How do you do it?  Note that you cannot send a key
in an unlocked box, since it might be copied.


==> logic/locks.and.boxes.s <==
Attach a lock to the ring.  Send it to her.  She attaches her own lock
and sends it back.  You remove your lock and send it back to her.  She
removes her lock.

==> logic/min.max.p <==
In a rectangular array of people, which will be taller, the tallest of the
shortest people in each column, or the shortest of the tallest people in each row?

==> logic/min.max.s <==
Let T denote shortest of tall
Let S denote tallest of short

-------------------------------
|                             |
|                             |
|                S            |
|                             |
|                             |
|    T           X            |
|                             |
|                             |
|                             |
|                             |
-------------------------------

So T >= X >= S.


==> logic/mixing.p <==
Start with a half cup of tea and a half cup of coffee. Take one tablespoon
of the tea and mix it in with the coffee. Take one tablespoon of this mixture
and mix it back in with the tea. Which of the two cups contains more of its
original contents?

==> logic/mixing.s <==
Mixing Liquids

The two cups end up with the same volume of liquid they started with. The same
amount of tea was moved to the coffee cup as coffee to the teacup. Therefore
each cup contains the same amount of its original contents.

==> logic/monty.52.p <==
Monty and Waldo play a game with N closed boxes.  Monty hides a
dollar in one box; the others are empty.  Monty opens the empty boxes
one by one.  When there are only two boxes left Waldo opens either box;
he wins if it contains the dollar.  Prior to each of the N-2 box
openings Waldo chooses one box and locks it, preventing Monty from opening
it next.  That box is then unlocked and cannot be so locked twice in a row.

What are the optimal strategies for Monty and Waldo and what is the
fair price for Waldo to pay to play the game?

==> logic/monty.52.s <==
The fair price for large N is $0.6321205588285576784; I will offer
a proof along with optimal strategies.

Denote the game as G_N().  After (N-M) rounds of play, the game will have
the same form as G_M().  Depending on the strategies each of the M boxes
will have a probability p_i of containing the dollar.  Let Waldo lock
the M'th box (renumbering the boxes if necessary).  Denote the game and
Waldo's expected winnings in the game by
        G_M(p_1, p_2, ..., p_M)
where
        p_1 + p_2 + ... + p_M = 1

When
        p_2 = p_3 = p_4 = ... = p_M
we adopt the abbreviation
        G_M(b) = G_M(1 + b - Mb, b, b, b, b, ..., b)
and note that since probabilities are never negative:
        1 + b - Mb >= 0, or
        0 <= b <= 1 / (M-1)

Various G_M(p_1, p_2, ..., p_M) have difficult solutions but we are asked
only to solve G_M(1/M) and it turns out we can accomplish this by
considering only the games
        G_M(b)  where    1/M  <=  b  <=  1/(M-1)        [1]
Games of this form will be said to satisfy constraint [1].

Induction is used for one of the theorems, so we'd better solve G_2 and G_3
for our basis.
        G_2(p_1, p_2) = max (p_1, p_2)
        G_3(p_1, p_2, p_3) = max (p_1 + p_2, p_3)
since after Monty opens box #1, box #2 will have probability (p_1 + p_2)
and vice versa.  When the probabilities satisfy constraint [1]:
        G_2(b) = G_2(1-b, b) = b
        G_3(b) = G_3(1-2b, b, b) = 1 - b

The proof of Theorem 1 is based on the probability p_i that box #i
contains the dollar.  (Of course this is Waldo's perceived probability:
Monty's probability would be 0 or 1.)  It may seem wrong for Waldo to
"forget" the game history and remember only the computed p_i.  For
example he may have previously locked some but not all of the boxes
and this fact is ignored except in the calculation of p_i.  Or Monty may
have some higher level "plan" which mightn't seem to translate directly
into probabilities.  But probability algebra obeys some simplifying
linearity rules and, if Monty keeps a "poker face", the probability model
is the only thing Waldo has to act on.

Especially paradoxical is the derivation of Waldo's p_i in his trivial
strategy below: he can adopt inferior but "correct" p_i to simplify the
analysis.

Theorem 1)
    If   b >= 1/M   then
    G_M(b) = G_[M-1]( (1-b) / (M-2) )

Proof)
    We will show that Monty and Waldo each have a strategy in G_M(b) to
    reduce the game to G_[M-1](b, q, q, ..., q) where q = (1-b) / (M-2)
    and where the boxes have been renumbered so that box #1 was box #M
    (the one Waldo locked) from the prior round and the new box #(M-1)
    is the one Waldo locks next.  Note that if Monty indeed arranges
    the probability mixture G_[M-1](b, q, q, q, q, ..., q) it won't
    matter which box Waldo locks (Box #1 has the only non-equal
    probability but Waldo cannot lock the same box twice in a row);
    this is a typical property of "saddlepoint" strategy.

    We will derive the necessary and sufficient condition for Monty to
    reduce any game G_M(p_1, p_2, p_3, ..., p_M) to a single game with
    the form G_[M-1](b, q, q, ..., q).  Using the numbering of G_M()
    let R(i,j) be the joint probability that Box #i contains the dollar
    and Box #j is opened by Monty in G_M().  We need consider only
        M >= 3
    Clearly,
        R(i, j) >= 0
        R(i, i) = 0
        R(i, M) = 0, i < M
        sum_over_j R(i,j) = p_i
    and to achieve q_2 = q_3 = ... = q_[M-1] in G_[M-1],
        R(1, j) = R(k, j)
            for 1 < j,k < M and j != k
        R(2, 1) = R(k, 1)
            for 2 < k < M
    and to make G_[M-1] be independent of Monty's play
        R(M, j)/R(1, j) = R(M, 2)/R(1, 2)
            for 2 < j < M
        R(M, 2)/R(1, 2) = R(M, 1)/R(2, 1)

    The above have a simple unique solution:
        R(i, j) = (1 - p_M) / (M - 2)  - p_j        [2]
            for i,j < M and i != j
        R(M, j) = p_M - p_j * p_M / (1 - p_M)        [3]
            for j < M
        p_j * (M-2) + p_M <= 1                [4]

    For the theorem we are given that G_M(b) satisfies constraint [1]
        1 / M  <=  b  <=  1 / (M - 1)
    which implies the weaker inequality
        (M - 3) / (M^2 - 3M + 1)  <=  b  <=  1 / (M - 1)
    and since for the constraint-[1] compliant G_M()
        p_j = b   or   p_j = (1+b-Mb)   for all j
    the inequality [4] follows directly.

    Hence Monty can transpose G_M(b) into G_[M-1]( (1-b) / (M-2) )
    whenever b >= 1/M and M >= 3.  (This G_[M-1] also happens to
    satisfy constraint [1] as needed for the next theorem.)

    It should be easy to argue that this strategy is optimal for Monty,
    but we want to derive Waldo's best strategy anyway and if it
    guarantees the same value we know we're at the "saddlepoint".
    If Waldo knows Monty has a non-optimal strategy he can take
    advantage of it, but we will just derive a strategy good enough
    to achieve the saddle-point value.

    Monty must transform G_M(b) into some
        G_[M-1](b, q_2, q_3, ..., q_[M-1])
    where Waldo has the choice of locking any of boxes #2 through #(M-1).
    If Waldo locks each of the (M-2) available boxes with probability
    1/(M-2) it is easily seen that the average probability that he
    locks the box with the dollar is (1-b) / (M-2) and the probabilities
    q_2, q_3, ..., q_[M-2] will also have the average value (1-b)/(M-2).
    If Waldo pretends to "forget" which box he picked before, he can
    take q_2 = q_3 = ... = (1-b)/(M-2) thereby constructing the same
    game Monty constructed with his saddlepoint strategy!

    In the above Waldo in effect "degraded" the accuracy of his
    probability estimates with the substitutions
        q_2' = (q_2 + q_3 + ... + q_[M-1]) / (M - 2)
        q_3' = (q_2 + q_3 + ... + q_[M-1]) / (M - 2)
          et cetera
    If Waldo "knows" more than this, he can pretend he doesn't!
    For example he can ask Monty to secretly shuffle the boxes.

    Thus either player can reduce
        G_M(b), b >= 1/M
    to
        G_[M-1]((1-b)/(M-2))
    so this must be the saddlepoint.
    Q.E.D.

Theorem 2)
    If   b >= 1/M   then
    G_M(b) = 1 - 1/2! + 1/3! - ... - (1-b)(-1)^M/(M-2)!
        = - sum (-1)^i/i! - (1-b)(-1)^M/(M-2)!
    where the sum is over i = 1, 2, 3, ..., M-3

Proof)
    The proof is by induction.  We know the theorem holds for M = 3
    and we will assume it holds for (M-1).  Set
        c = (1-b) / (M-2)
    We noted earlier that b <= 1/(M-1): otherwise p_1 = (1 + b - Mb)
    is negative; hence we obtain
        c = (1-b)/(M-2) >= (1 - 1/(M-1)) / (M-2)
    or simply
        c >= 1/(M-1)
    Thus the condition of the inductive hypothesis is satisfied and
        G_[M-1](c) = 1 - 1/2! + 1/3! - ... + (1-c)(-1)^M/(M-3)!
    But from Theorem 1
        G_M(b) = G_[M-1](c)
    and from the definition of c,
        c/(M-3)! = (1-b)/(M-2)!
    which establishes the theorem.

Theorem 3)
    G_M(1/M) = G_M(1/M, ..., 1/M) = 1 - 1/2! + 1/3! - ... -(-1)^M/M!

Proof)
    This follows directly from Theorem 2 and the observation that
        (1/M)/(M-2)! = 1/(M-1)! - 1/M!

For large M, G_M(1/M) approaches (1 - 1/e).  It will be a little bigger
when M is odd and a little smaller when M is even.  I've appended the
numeric values below.

% dc
[[Solution for M =]Plb1+pdsb]sy
65k1sa1sblyx2sc[la1lc/-dsaplclyx*scla1lc/+dsaplclyx*sclzx]dszx
Solution for M =2
0.50000000000000000000000000000000000000000000000000000000000000000
Solution for M =3
0.66666666666666666666666666666666666666666666666666666666666666666
Solution for M =4
0.62500000000000000000000000000000000000000000000000000000000000000
Solution for M =5
0.63333333333333333333333333333333333333333333333333333333333333333
Solution for M =6
0.63194444444444444444444444444444444444444444444444444444444444445
Solution for M =7
0.63214285714285714285714285714285714285714285714285714285714285714
Solution for M =8
0.63211805555555555555555555555555555555555555555555555555555555556
Solution for M =9
0.63212081128747795414462081128747795414462081128747795414462081129
Solution for M =10
0.63212053571428571428571428571428571428571428571428571428571428572
    . . .
Solution for M =52
0.63212055882855767840447622983853913255418886896823216549216319831

P. S. There are related unsolved problems:
(a) what about G_M(p_1, p_2, ..., p_M) that do not fit the pattern used
in the above solution?
(b) what if two boxes contain dollars?  (first, what should the rules be?)

-- [e-mail] (James Allen)

==> logic/number.p <==
Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce
any truth from any set of axioms.  Two integers (not necessarily unique) are
somehow chosen such that each is within some specified range.  Mr. S.
is given the sum of these two integers; Mr. P. is given the product of these
two integers.  After receiving these numbers, the two logicians do not
have any communication at all except the following dialogue:
<<1>>   Mr. P.:  I do not know the two numbers.
<<2>>   Mr. S.:  I knew that you didn't know the two numbers.
<<3>>   Mr. P.:  Now I know the two numbers.
<<4>>   Mr. S.:  Now I know the two numbers.

Given that the above statements are absolutely truthful, what are the two
numbers?

==> logic/number.s <==
The answer depends upon the ranges from which the numbers are chosen.

The unique solution for the ranges [2,62] through [2,500+] is:

  SUM   PRODUCT   X   Y
   17      52     4  13

The unique solution for the ranges [3,94] through [3,500+] is:

  SUM   PRODUCT   X   Y
   29     208    13  16

There are no unique solutions for the ranges starting with 1,
and there are no solutions for ranges starting with numbers above 3.

A program to compute the possible pairs is included below.

#include <stdio.h>

/*

BEGINNING OF PROBLEM STATEMENT:
Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce
any truth from any set of axioms.  Two integers (not necessarily unique) are
somehow chosen such that each is within some specified range.  Mr. S.
is given the sum of these two integers; Mr. P. is given the product of these
two integers.  After receiving these numbers, the two logicians do not
have any communication at all except the following dialogue:
<<1>>   Mr. P.:  I do not know the two numbers.
<<2>>   Mr. S.:  I knew that you didn't know the two numbers.
<<3>>   Mr. P.:  Now I know the two numbers.
<<4>>   Mr. S.:  Now I know the two numbers.

Given that the above statements are absolutely truthful, what are the two
numbers?

END OF PROBLEM STATEMENT

 */

#define SMALLEST_MIN    1
#define LARGEST_MIN    10
#define SMALLEST_MAX    50
#define LARGEST_MAX    500

long P[(LARGEST_MAX + 1) * (LARGEST_MAX + 1)];        /* products */
long S[(LARGEST_MAX + 1) + (LARGEST_MAX + 1)];        /*   sums   */

find(long min, long max)
{
    long i, j;
    /*
     *    count factorizations in P[]
     *    all P[n] > 1 satisfy <<1>>.
     */
    for(i = 0; i <= max * max; ++i)
        P[i] = 0;

    for(i = min; i <= max; ++i)
        for(j = i; j <= max; ++j)
            ++P[i * j];

    /*
     *    decompose possible SUMs and check factorizations
     *        all S[n] == min - 1 satisfy <<2>>.
     */
    for(i = min + min; i <= max + max; ++i) {

        for(j = i / 2; j >= min; --j)
            if(P[j * (i - j)] < 2)
                break;

        S[i] = j;
    }

    /*
     *    decompose SUMs which satisfy <<2>> and see which products
     *    they produce.  All (P[n] / 1000 == 1) satisfy <<3>>.
     */
    for(i = min + min; i <= max + max; ++i)
        if(S[i] == min - 1)
            for(j = i / 2; j >= min; --j)
                if(P[j * (i - j)] > 1)
                    P[j * (i - j)] += 1000;
    /*
     *    decompose SUMs which satisfy <<2>> again and see which products
     *    satisfy <<3>>.  Any (S[n] == 999 + min) satisfies <<4>>
     */
    for(i = min + min; i <= max + max; ++i)
        if(S[i] == min - 1)
            for(j = i / 2; j >= min; --j)
                if(P[j * (i - j)] / 1000 == 1)
                    S[i] += 1000;
    /*
     *    find the answer(s) and print them
     */
    printf("[%d,%d]\n",min,max);
    for(i = min + min; i <= max + max; ++i)
        if(S[i] == 999 + min)
            for(j = i / 2; j >= min; --j)
                if(P[j * (i - j)] / 1000 == 1)
                    printf("{ %d %d }: S = %d, P = %d\n",
                        i - j, j, i, (i - j)  * j);
}

main()
{
    long min, max;

    for (min = SMALLEST_MIN; min <= LARGEST_MIN; min ++)
        for (max = SMALLEST_MAX; max <= LARGEST_MAX; max++)
        find(min,max);
}

-------------------------------------------------------------------------
=            Jeff Kenton    [phone]            =
=                [e-mail]            =
-------------------------------------------------------------------------
Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!sdd.hp.com!swrinde!cs.utexas.edu!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (logic), part 23 of 35
Message-ID: <puzzles/archive/logic/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:06:12 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 929
Xref: senator-bedfellow.mit.edu rec.puzzles:25018 news.answers:11538 rec.answers:1938

Archive-name: puzzles/archive/logic/part2
Last-modified: 17 Aug 1993
Version: 4


==> logic/riddle.p <==
Who makes it, has no need of it.  Who buys it, has no use for it.  Who
uses it can neither see nor feel it.


Tell me what a dozen rubber trees with thirty boughs on each might be?


As I went over London Bridge
I met my sister Jenny
I broke her neck and drank her blood
And left her standing empty


It is said among my people that some things are improved by death.
Tell me, what stinks while living, but in death, smells good?


All right.  Riddle me this:  what goes through the door without
pinching itself?  What sits on the stove without burning itself?  What
sits on the table and is not ashamed?


What work is it that the faster you work, the longer it is before
you're done, and the slower you work, the sooner you're finished?


Whilst I was engaged in sitting I spied the dead carrying the living.


I know a word of letters three.  Add two, and fewer there will be.


I give you a group of three.  One is sitting down, and will never get
up.  The second eats as much as is given to him, yet is always hungry.
The third goes away and never returns.


Whoever makes it, tells it not.  Whoever takes it, knows it not.  And
whoever knows it wants it not.


Two words, my answer is only two words.
To keep me, you must give me.


Sir, I bear a rhyme excelling
In mystic force and magic spelling
Celestial sprites elucidate
All my own striving can't relate


There is not wind enough to twirl
That one red leaf, nearest of its clan,
Which dances as often as dance it can.


Half-way up the hill, I see thee at last
Lying beneath me with thy sounds and sights --
A city in the twilight, dim and vast,
With smoking roofs, soft bells, and gleaming lights.


I am, in truth, a yellow fork
From tables in the sky
By inadvertent fingers dropped
The awful cutlery.
Of mansions never quite disclosed
And never quite concealed
The apparatus of the dark
To ignorance revealed.


Many-maned scud-thumper,
Maker of worn wood,
Shrub-ruster,
Sky-mocker,
Rave!


Make me thy lyre, even as the forests are.
What if my leaves fell like its own --
The tumult of thy mighty harmonies
Will take from both a deep autumnal tone.


This darksome burn, horseback brown,
His rollock highroad roaring down,
In coop and in comb the fleece of his foam
Flutes and low to the body falls home.


I've measured it from side to side,
'Tis three feet long and two feet wide.
It is of compass small, and bare
To thirsty suns and parching air.


My love, when I gaze on thy beautiful face,
Careering along, yet always in place --
The thought has often come into my mind
If I ever shall see thy glorious behind.


Then all thy feculent majesty recalls
The nauseous mustiness of forsaken bowers,
The leprous nudity of deserted halls --
The positive nastiness of sullied flowers.
And I mark the colours, yellow and black,
That fresco thy lithe, dictatorial thighs.


When young, I am sweet in the sun.
When middle-aged, I make you gay.
When old, I am valued more than ever.


I am always hungry,
I must always be fed,
The finger I lick
Will soon turn red.


All about, but cannot be seen,
Can be captured, cannot be held,
No throat, but can be heard.


I am only useful
When I am full,
Yet I am always
Full of holes.


If you break me
I do not stop working,
If you touch me
I may be snared,
If you lose me
Nothing will matter.


If a man carried my burden
He would break his back.
I am not rich,
But leave silver in my track.


Until I am measured
I am not known,
Yet how you miss me
When I have flown.


I drive men mad
For love of me,
Easily beaten,
Never free.


When set loose
I fly away,
Never so cursed
As when I go astray.


I go around in circles
But always straight ahead,
Never complain
No matter where I am led.


Lighter than what
I am made of,
More of me is hidden
Than is seen.


I turn around once,
What is out will not get in.
I turn around again,
What is in will not get out.


Each morning I appear
To lie at your feet,
All day I will follow
No matter how fast you run,
Yet I nearly perish
In the midday sun.


Weight in my belly,
Trees on my back,
Nails in my ribs,
Feet I do lack.


Bright as diamonds,
Loud as thunder,
Never still,
A thing of wonder.


My life can be measured in hours,
I serve by being devoured.
Thin, I am quick
Fat, I am slow
Wind is my foe.


To unravel me
You need a simple key,
No key that was made
By locksmith's hand,
But a key that only I
Will understand.


I am seen in the water
If seen in the sky,
I am in the rainbow,
A jay's feather,
And lapis lazuli.


Glittering points
That downward thrust,
Sparkling spears
That never rust.


You heard me before,
Yet you hear me again,
Then I die,
'Till you call me again.


Three lives have I.
Gentle enough to soothe the skin,
Light enough to caress the sky,
Hard enough to crack rocks.


You can see nothing else
When you look in my face,
I will look you in the eye
And I will never lie.


Lovely and round,
I shine with pale light,
grown in the darkness,
A lady's delight.


At the sound of me, men may dream
Or stamp their feet
At the sound of me, women may laugh
Or sometimes weep


When I am filled
I can point the way,
When I am empty
Nothing moves me,
I have two skins
One without and one within.


My tines be long,
My tines be short
My tines end ere
My first report.
What am I?


With thieves I consort,
With the vilest, in short,
  I'm quite at ease in depravity;
Yet all divines use me,
And savants can't lose me,
  For I am the center of gravity.


As a whole, I am both safe and secure.
Behead me, and I become a place of meeting.
Behead me again, and I am the partner of ready.
Restore me, and I become the domain of beasts.
What am I?


I sought my first in starry skies
  Where shines the April sun;
My second came before my eyes,
  And warned me to be done.

'Tis very hard to lose one's sight;
  I'm blind as bat or mole;
Once hills and fields were my delight,
  Now I'm no more my whole.


My first is high,
  My second damp,
My whole a tie,
  A writer's cramp.


A hundred and one
  by fifty divide,
And if a cipher
  is rightly applied,
The answer is one from nine.


What does man love more than life
Fear more than death or mortal strife
What the poor have, the rich require,
and what contented men desire,
What the miser spends and the spendthrift saves
And all men carry to their graves?


I build up castles.
I tear down mountains.
I make some men blind,
I help others to see.
    What am I?


Ripped from my mother's womb,
Beaten and burned,
I become a blood-thirsty slayer
    What am I?


Five hundred begins it, five hundred ends it,
Five in the middle is seen;
First of all figures, the first of all letters,
Take up their stations between.
Join all together, and then you will bring
Before you the name of an eminent king.

==> logic/riddle.s <==
Who makes it, has no need of it.  Who buys it, has no use for it.  Who
uses it can neither see nor feel it.

coffin

Tell me what a dozen rubber trees with thirty boughs on each might be?

months of the year

As I went over London Bridge
I met my sister Jenny
I broke her neck and drank her blood
And left her standing empty

gin

It is said among my people that some things are improved by death.
Tell me, what stinks while living, but in death, smells good?

pig

All right.  Riddle me this:  what goes through the door without
pinching itself?  What sits on the stove without burning itself?  What
sits on the table and is not ashamed?

the sun

What work is it that the faster you work, the longer it is before
you're done, and the slower you work, the sooner you're finished?

roasting meat on a spit

Whilst I was engaged in sitting I spied the dead carrying the living.

a ship

I know a word of letters three.  Add two, and fewer there will be.

'few'

I give you a group of three.  One is sitting down, and will never get
up.  The second eats as much as is given to him, yet is always hungry.
The third goes away and never returns.

stove, fire, and smoke

Whoever makes it, tells it not.  Whoever takes it, knows it not.  And
whoever knows it wants it not.

counterfeit money

Two words, my answer is only two words.
To keep me, you must give me.

your word

Sir, I bear a rhyme excelling
In mystic force and magic spelling
Celestial sprites elucidate
All my own striving can't relate

Pi (digits given by length of words)

There is not wind enough to twirl
That one red leaf, nearest of its clan,
Which dances as often as dance it can.

the sun, Samuel Taylor Coleridge

Half-way up the hill, I see thee at last
Lying beneath me with thy sounds and sights --
A city in the twilight, dim and vast,
With smoking roofs, soft bells, and gleaming lights.

the past, Longfellow

I am, in truth, a yellow fork
From tables in the sky
By inadvertent fingers dropped
The awful cutlery.
Of mansions never quite disclosed
And never quite concealed
The apparatus of the dark
To ignorance revealed.

lightning, Emily Dickinson

Many-maned scud-thumper,
Maker of worn wood,
Shrub-ruster,
Sky-mocker,
Rave!
Portly pusher,
Wind-slave.

the ocean, John Updike

Make me thy lyre, even as the forests are.
What if my leaves fell like its own --
The tumult of thy mighty harmonies
Will take from both a deep autumnal tone.

the west wind, Percy Bysshe Shelley

This darksome burn, horseback brown,
His rollock highroad roaring down,
In coop and in comb the fleece of his foam
Flutes and low to the body falls home.

river, Gerard Manley Hopkins

I've measured it from side to side,
'Tis three feet long and two feet wide.
It is of compass small, and bare
To thirsty suns and parching air.

the grave of a child, Wordsworth

My love, when I gaze on thy beautiful face,
Careering along, yet always in place --
The thought has often come into my mind
If I ever shall see thy glorious behind.

the moon, Sir Edmund Gosse

Then all thy feculent majesty recalls
The nauseous mustiness of forsaken bowers,
The leprous nudity of deserted halls --
The positive nastiness of sullied flowers.
And I mark the colours, yellow and black,
That fresco thy lithe, dictatorial thighs.

spider, Francis Saltus Saltus

When young, I am sweet in the sun.
When middle-aged, I make you gay.
When old, I am valued more than ever.

wine

I am always hungry,
I must always be fed,
The finger I lick
Will soon turn red.

fire

All about, but cannot be seen,
Can be captured, cannot be held,
No throat, but can be heard.

wind

I am only useful
When I am full,
Yet I am always
Full of holes.

sieve (or sponge)

If you break me
I do not stop working,
If you touch me
I may be snared,
If you lose me
Nothing will matter.

heart

If a man carried my burden
He would break his back.
I am not rich,
But leave silver in my track.

snail

Until I am measured
I am not known,
Yet how you miss me
When I have flown.

time

I drive men mad
For love of me,
Easily beaten,
Never free.

gold

When set loose
I fly away,
Never so cursed
As when I go astray.

a fart

I go around in circles
But always straight ahead,
Never complain
No matter where I am led.

wagon wheel

Lighter than what
I am made of,
More of me is hidden
Than is seen.

iceberg

I turn around once,
What is out will not get in.
I turn around again,
What is in will not get out.

stopcock

Each morning I appear
To lie at your feet,
All day I will follow
No matter how fast you run,
Yet I nearly perish
In the midday sun.

shadow

Weight in my belly,
Trees on my back,
Nails in my ribs,
Feet I do lack.

ship

Bright as diamonds,
Loud as thunder,
Never still,
A thing of wonder.

waterfall? (fireworks?)

My life can be measured in hours,
I serve by being devoured.
Thin, I am quick
Fat, I am slow
Wind is my foe.

candle

To unravel me
You need a simple key,
No key that was made
By locksmith's hand,
But a key that only I
Will understand.

cipher

I am seen in the water
If seen in the sky,
I am in the rainbow,
A jay's feather,
And lapis lazuli.

blue

Glittering points
That downward thrust,
Sparkling spears
That never rust.

icicle

You heard me before,
Yet you hear me again,
Then I die,
'Till you call me again.

echo

Three lives have I.
Gentle enough to soothe the skin,
Light enough to caress the sky,
Hard enough to crack rocks.

water

You can see nothing else
When you look in my face,
I will look you in the eye
And I will never lie.

your reflection

Lovely and round,
I shine with pale light,
grown in the darkness,
A lady's delight.

pearl

At the sound of me, men may dream
Or stamp their feet
At the sound of me, women may laugh
Or sometimes weep

music

When I am filled
I can point the way,
When I am empty
Nothing moves me,
I have two skins
One without and one within.

glove

My tines be long,
My tines be short
My tines end ere
My first report.
What am I?

lightning

With thieves I consort,
With the vilest, in short,
  I'm quite at ease in depravity;
Yet all divines use me,
And savants can't lose me,
  For I am the center of gravity.

The letter 'v'.

As a whole, I am both safe and secure.
Behead me, and I become a place of meeting.
Behead me again, and I am the partner of ready.
Restore me, and I become the domain of beasts.
What am I?

stable

I sought my first in starry skies
  Where shines the April sun;
My second came before my eyes,
  And warned me to be done.

'Tis very hard to lose one's sight;
  I'm blind as bat or mole;
Once hills and fields were my delight,
  Now I'm no more my whole.

?

My first is high,
  My second damp,
My whole a tie,
  A writer's cramp.

?

A hundred and one
  by fifty divide,
And if a cipher
  is rightly applied,
The answer is one from nine.

?

What does man love more than life
Fear more than death or mortal strife
What the poor have, the rich require,
and what contented men desire,
What the miser spends and the spendthrift saves
And all men carry to their graves?

nothing

I build up castles.
I tear down mountains.
I make some men blind,
I help others to see.
    What am I?

sand

Ripped from my mother's womb,
Beaten and burned,
I become a blood-thirsty slayer
    What am I?

?

Five hundred begins it, five hundred ends it,
Five in the middle is seen;
First of all figures, the first of all letters,
Take up their stations between.
Join all together, and then you will bring
Before you the name of an eminent king.

DAVID (Roman numerals)

==> logic/river.crossing.p <==
Three humans, one big monkey and two small monkeys are to cross a river:
     a) Only humans and the big monkey can row the boat.
     b) At all times, the number of human on either side of the
        river must be GREATER OR EQUAL to the number of monkeys
        on THAT side. ( Or else the humans will be eaten by the monkeys!)

==> logic/river.crossing.s <==
The three columns represent the left bank, the boat, and the right bank
respectively. The < or > indicates the direction of motion of the boat.

HHHMmm    .    .
HHHm    Mm>    .
HHHm    <M    m
HHH    Mm>    m
HHH    <M    mm
HM    HH>    mm
HM    <Hm    Hm
Hm    HM>    Hm
Hm    <Hm    HM
mm    HH>    HM
mm    <M    HHH
m    Mm>    HHH
m    <M    HHHm
.    Mm>    HHHm
.    .    HHHMmm

==> logic/ropes.p <==
Two fifty foot ropes are suspended from a forty foot ceiling, about
twenty feet apart.  Armed with only a knife, how much of the rope can
you steal?

==> logic/ropes.s <==
Almost all of it.  Tie the ropes together.  Climb up one of them.  Tie
a loop in it as close as possible to the ceiling.  Cut it below the
loop.  Run the rope through the loop and tie it to your waist.  Climb
the other rope (this may involve some swinging action).  Pull the rope
going through the loop tight and cut the other rope as close as
possible to the ceiling.  You will swing down on the rope through the
loop.  Lower yourself to the ground by letting out rope.  Pull the
rope through the loop.  You will have nearly all the rope.

==> logic/same.street.p <==
Sally and Sue have a strong desire to date Sam.  They all live on the
same street yet neither Sally or Sue know where Sam lives.  The houses
on this street are numbered 1 to 99.

Sally asks Sam "Is your house number a perfect square?".  He answers.
Then Sally asks "Is is greater than 50?".  He answers again.

Sally thinks she now knows the address of Sam's house and decides to
visit.

When she gets there, she finds out she is wrong.  This is not
surprising, considering Sam answered only the second question
truthfully.

Sue, unaware of Sally's conversation, asks Sam two questions.
Sue asks "Is your house number a perfect cube?".  He answers.
She then asks "Is it greater than 25?".  He answers again.

Sue thinks she knows where Sam lives and decides to pay him a visit.
She too is mistaken as Sam once again answered only the second
question truthfully.

If I tell you that Sam's number is less than Sue's or Sally's,
and that the sum of their numbers is a perfect square multiplied
by two, you should be able to figure out where all three of them
live.

==> logic/same.street.s <==
Sally asks Sam "Is your house number a perfect square?".  He answers.
Then Sally asks "Is is greater than 50?".  He answers again.

Sally thinks she now knows the address of Sam's house and decides to
visit.

    Since Sally thinks that she has enough information, I deduce
    that Sam answered that his house number was a perfect square
    greater than 50.  There are two of these {64,81} and Sally must
    live in one of them in order to have decided she knew where Sam
    lives.

When she gets there, she finds out she is wrong.  This is not
surprising, considering Sam answered only the second question
truthfully.

    So Sam's house number is greater than 50, but not a perfect
    square.

Sue, unaware of Sally's conversation, asks Sam two questions.
Sue asks "Is your house number a perfect cube?".  He answers.
She then asks "Is it greater than 25?".  He answers again.

    Observation: perfect cubes greater than 25 are {27, 64}, less
    than 25 are {1,8}.

Sue thinks she knows where Sam lives and decides to pay him a visit.
She too is mistaken as Sam once again answered only the second
question truthfully.

    Since Sam's house number is greater than 50, he told Sue that
    it was greater than 25 as well.  Since Sue thought she knew
    which house was his, she must live in either of {27,64}.

If I tell you that Sam's number is less than Sue's or Sally's,

    Since Sam's number is greater than 50, and Sue's is even
    bigger, she must live in 64.  Assuming Sue and Sally are not
    roommates (although awkward social situations of this kind are
    not without precedent), Sally lives in 81.

and that the sum of their numbers is a perfect square multiplied
by two, you should be able to figure out where all three of them
live.

    Sue + Sally + Sam = 2 p^2        for p an integer
    64  + 81    + Sam = 2 p^2

    Applying the constraint 50 < Sam < 64, looks like Sam = 55 (p = 10).

    In summary,
        Sam = 55
        Sue = 64
        Sally = 81

    -- Tom Smith <[e-mail]>

==> logic/self.ref.p <==
Find a number ABCDEFGHIJ such that A is the count of how many 0's are in the
number, B is the number of 1's, and so on.

==> logic/self.ref.s <==
6210001000

For other numbers of digits:

n=1:    no sequence possible
n=2:    no sequence possible
n=3:    no sequence possible
n=4:    1210, 2020
n=5:    21200
n=6:    no sequence possible
n=7:    3211000
n=8:    42101000
n=9:    521001000
n=10:    6210001000
n>10:    (n-4), 2, 1, 0 * (n-7), 1, 0, 0, 0

No 1, 2, or 3 digit numbers are possible.  Letting x_i be the ith
digit, starting with 0, we see that (1) x_0 + ... + x_n = n+1 and
(2) 0*x_0 + ... + n*x_n = n+1, where n+1 is the number of digits.

I'll first prove that x_0 > n-3 if n>4.  Assume not, then this
implies that at least four of the x_i with i>0 are non-zero.  But
then we would have \sum_i i*x_i >= 10 by (2), impossible unless n=9,
but it isn't possible in this case (51111100000 isn't valid).

Now I'll prove that x_0 < n-1.  x_0 clearly can't equal n; assume
x_0 = n-1 ==> x_{n-1} = 1 by (2) if n>3.  Now only one of the
remaining x_i may be non-zero, and we must have that x_0 + ... + x_n
= n+1, but since x_0 + x_{n-1} = n ==> the remaining x_i = 1 ==> by
(2) that x_2 = 1.  But this can't be, since x_{n-1} = 1 ==> x_1>0.
Now assuming x_0 = n-2 we conclude that x_{n-2} = 1 by (2) if n>5
==> x_1 + ... + x_{n-3} + x_{n-1} + x_n = 2 and 1*x_1 + ... +
(n-3)*x_{n-3} + (n-1)*x_{n-1} + n*x_n = 3 ==> x_1=1 and x_2=1,
contradiction.

Case n>5:

We have that x_0 = n-3 and if n>=7 ==> x_{n-3}=1 ==> x_1=2 and
x_2=1 by (1) and (2).  For the case n=6 we see that x_{n-3}=2
leads to an easy contradiction, and we get the same result.  The
cases n=4,5 are easy enough to handle, and lead to the two solutions
above.
--
    -- [e-mail] (Chris Long)
Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (logic), part 24 of 35
Message-ID: <puzzles/archive/logic/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:06:15 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 480
Xref: senator-bedfellow.mit.edu rec.puzzles:25007 news.answers:11527 rec.answers:1927

Archive-name: puzzles/archive/logic/part3
Last-modified: 17 Aug 1993
Version: 4


==> logic/situation.puzzles.p <==
                      Jed's List of Situation Puzzles



   "A man lies dead in a room with fifty-three bicycles in front of him.
What happened?"

   This is a list of what I refer to (for lack of a better name) as situation
puzzles.  In the game of situation puzzles, a situation like the one above is
presented to a group of players, who must then try to find out more about the
situation by asking further questions.  The person who initially presented
the situation can only answer "yes" or "no" to questions (or occasionally
"irrelevant" or "doesn't matter").

   My list has been divided into two sections.  Section 1 consists of
situation puzzles which are set in a realistic world; the situations could
all actually occur.  Section 2 consists of puzzles which involve double
meanings for one or more words and those which could not possibly take place
in reality as we know it, plus a few miscellaneous others.

   See the end of the list for more notes and comments.

   The answers to these puzzles are available in a separate file.



Section 1: "Realistic" situation puzzles.

1.1.  In the middle of the ocean is a yacht.  Several corpses are floating in
the water nearby.  (SJ)

1.2.  A man is lying dead in a room.  There is a large pile of gold and
jewels on the floor, a chandelier attached to the ceiling, and a large open
window.  (DVS; partial JM wording)

1.3.  A woman came home with a bag of groceries, got the mail, and walked
into the house.  On the way to the kitchen, she went through the living room
and looked at her husband, who had blown his brains out.  She then continued
to the kitchen, put away the groceries, and made dinner.  (partial JM
wording)

1.4.  A body is discovered in a park in Chicago in the middle of summer.  It
has a fractured skull and many other broken bones, but the cause of death was
hypothermia.  (MI, from _Hill Street Blues_)

1.5.  A man lives on the twelfth floor of an apartment building.  Every
morning he takes the elevator down to the lobby and leaves the building.  In
the evening, he gets into the elevator, and, if there is someone else in the
elevator -- or if it was raining that day -- he goes back to his floor
directly.  However, if there is nobody else in the elevator and it hasn't
rained, he goes to the 10th floor and walks up two flights of stairs to his
room.  (MH)

1.6.  A woman has incontrovertible proof in court that her husband was
murdered by her sister.  The judge declares, "This is the strangest case I've
ever seen.  Though it's a cut-and-dried case, this woman cannot be punished."
(This is different from #1.43.)  (MH)

1.7.  A man walks into a bar and asks for a drink.  The bartender pulls out a
gun and points it at him.  The man says, "Thank you," and walks out.  (DVS)

1.8.  A man is returning from Switzerland by train.  If he had been in a
non-smoking car he would have died.  (DVS; MC wording)

1.9.  A man goes into a restaurant, orders abalone, eats one bite, and kills
himself.  (TM and JM wording)

1.10.  A man is found hanging in a locked room with a puddle of water under
his feet.  (This is different from #1.11.)

1.11.  A man is dead in a puddle of blood and water on the floor of a locked
room.  (This is different from #1.10.)

1.12.  A man is lying, dead, face down in the desert wearing a backpack.
(This is different from #1.13, #2.11, and #2.12.)

1.13.  A man is lying face down, dead, in the desert, with a match near his
outstretched hand.  (This is different from #1.12, #2.11, and #2.12.)  (JH;
partial JM wording)

1.14.  A man is driving his car.  He turns on the radio, listens for five
minutes, turns around, goes home, and shoots his wife.  (This is different
from #1.15.)

1.15.  A man driving his car turns on the radio.  He then pulls over to the
side of the road and shoots himself.  (This is different from #1.14.)

1.16.  Music stops and a woman dies.  (DVS)

1.17.  A man is dead in a room with a small pile of pieces of wood and
sawdust in one corner.  (from "Coroner's Inquest," by Marc Connelly)

1.18.  A flash of light, a man dies.  (ST original)

1.19.  A rope breaks.  A bell rings.  A man dies.  (KH)

1.20.  A woman buys a new pair of shoes, goes to work, and dies.  (DM)

1.21.  A man is riding a subway.  He meets a one-armed man, who pulls out a
gun and shoots him.  (SJ)

1.22.  Two women are talking.  One goes into the bathroom, comes out five
minutes later, and kills the other.

1.23.  A man is sitting in bed.  He makes a phone call, saying nothing, and
then goes to sleep.  (SJ)

1.24.  A man kills his wife, then goes inside his house and kills himself.
(DH original, from "Nightmare in Yellow," by Fredric Brown)

1.25.  Abel walks out of the ocean.  Cain asks him who he is, and Abel
answers.  Cain kills Abel.  (MWD original)

1.26.  Two men enter a bar.  They both order identical drinks.  One lives;
the other dies.  (CR; partial JM wording)

1.27.  Joe leaves his house, wearing a mask and carrying an empty sack.  An
hour later he returns.  The sack is now full.  He goes into a room and turns
out the lights.  (AL)

1.28.  A man takes a two-week cruise to Mexico from the U.S.  Shortly after
he gets back, he takes a three-day cruise which doesn't stop at any other
ports.  He stays in his cabin all the time on both cruises.  As a result, he
makes $250,000.  (MI, from "The Wager")

1.29.  Hans and Fritz are German spies during World War II.  They try to
enter America, posing as returning tourists.  Hans is immediately arrested.
(JM)

1.30.  Tim and Greg were talking.  Tim said "The terror of flight."  Greg
said "The gloom of the grave."  Greg was arrested.  (MPW original, from "No
Refuge Could Save," by Isaac Asimov)

1.31.  A man is found dead in his parked car.  Tire tracks lead up to the car
and away.  (SD)

1.32.  A man dies in his own home.  (ME original)

1.33.  A woman in France in 1959 is waiting in her room, with all the doors
locked from the inside, for her husband to come home.  When he arrives, the
house has burned to the ground and she's dead.  (JM, from _How Come --
Again?_)

1.34.  A man gets onto an elevator.  When the elevator stops, he knows his
wife is dead.  (LA; partial KH wording)

1.35.  Three men die.  On the pavement are pieces of ice and broken glass.
(JJ)

1.36.  She lost her job when she invited them to dinner.  (DS original)

1.37.  A man is running along a corridor with a piece of paper in his hand.
The lights flicker and the man drops to his knees and cries out, "Oh no!"
(MP)

1.38.  A car without a driver moves; a man dies.  (EMS)

1.39.  As I drive to work on my motorcycle, there is one corner which I go
around at a certain speed whether it's rainy or sunny.  If it's cloudy but
not raining, however, I usually go faster.  (SW original)

1.40.  A woman throws something out a window and dies.  (JM)

1.41.  An avid birdwatcher sees an unexpected bird.  Soon he's dead.  (RSB
original)

1.42.  There are a carrot, a pile of pebbles, and a pipe lying together in
the middle of a field.  (PRO; partial JM wording)

1.43.  Two brothers are involved in a murder.  Though it's clear that one of
them actually committed the crime, neither can be punished.  (This is
different from #1.6.)  (from "Unreasonable Doubt," by Stanley Ellin)

1.44.  An ordinary American citizen, with no passport, visits over thirty
foreign countries in one day.  He is welcomed in each country, and leaves
each one of his own accord.  (PRO)

1.45.  If he'd turned on the light, he'd have lived.  (JM)

1.46.  A man is found dead on the floor in the living room.  (ME original)

1.47.  A man is found dead outside a large building with a hole in him.  (JM,
modified from PRO)

1.48.  A man is found dead in an alley lying in a red pool with two sticks
crossed near his head.  (PRO)

1.49.  A man lies dead next to a feather.  (PRO)

1.50.  There is blood on the ceiling of my bedroom.  (MI original)

1.51.  A man wakes up one night to get some water.  He turns off the light
and goes back to bed.  The next morning he looks out the window, screams, and
kills himself.  (CR; KK wording)

1.52.  She grabbed his ring, pulled on it, and dropped it.  (JM, from _Math
for Girls_)

1.53.  A man sitting on a park bench reads a newspaper article headlined
"Death at Sea" and knows a murder has been committed.

1.54.  A man tries the new cologne his wife gave him for his birthday.  He
goes out to get some food, and is killed.  (RW original)

1.55.  A man in uniform stands on the beach of a tropical island.  He takes
out a cigarette, lights it, and begins smoking.  He takes out a letter and
begins reading it.  The cigarette burns down between his fingers, but he
doesn't throw it away.  He cries.  (RW)

1.56.  A man went into a restaurant, had a large meal, and paid nothing for
it.  (JM original)

1.57.  A married couple goes to a movie.  During the movie the husband
strangles the wife.  He is able to get her body home without attracting
attention.  (from _Beyond the Easy Answer_)

1.58.  A man ran into a fire, and lived.  A man stayed where there was no
fire, and died.  (Eric Wang original)

1.59.  A writer with an audience of millions insisted that he was never to be
interrupted while writing.  After the day when he actually was interrupted,
he never wrote again.  (JM, from _How Come?_)

1.60.  Beulah died in the Appalachians, while Craig died at sea.  Everyone
was much happier with Craig's death.  (JM, from _How Come?_)

1.61.  Mr. Browning is glad the car ran out of gas.  (JM, from _Home Come?_)

1.62.  A man is sitting suspended over two pressurized containers.  Suddenly,
he dies.  (NK original)

1.63.  A man leaves a motel room, goes to his car, and honks the horn.  (AS
original)

1.64.  Two dead people sit in their cars on a street.  (AG)

1.65.  A woman lies dead in the street near a car.  (AG)

1.66.  A riverboat filled with passengers suddenly capsized, drowning most of
those aboard.  (from _How Come -- Again?_)



Section 2: Double meanings, fictional settings, and miscellaneous others.

2.1.  A man shoots himself, and dies.  (HL) (This is different from #2.2.)

2.2.  A man walks into a room, shoots, and kills himself.  (HL) (This is
different from #2.1.)

2.3.  Adults are holding children, waiting their turn.  The children are
handed (one at a time, usually) to a man, who holds them while a woman shoots
them.  If the child is crying, the man tries to stop the crying before the
child is shot.  (ML)

2.4.  Hiking in the mountains, you walk past a large field and camp a few
miles farther on, at a stream.  It snows in the night, and the next day you
find a cabin in the field with two dead bodies inside.  (KL; KD and partial
JM wording)

2.5.  A man marries twenty women in his village but isn't charged with
polygamy.

2.6.  A man is alone on an island with no food and no water, yet he does not
fear for his life.  (MN)

2.7.  Joe wants to go home, but he can't go home because the man in the mask
is waiting for him.  (AL wording)

2.8.  A man is doing his job when his suit tears.  Fifteen minutes later,
he's dead.  (RM)

2.9.  A dead man lies near a pile of bricks and a beetle on top of a book.
(MN)

2.10.  At the bottom of the sea there lies a ship worth millions of dollars
that will never be recovered.  (TF original)

2.11.  A man is found dead in the arctic with a pack on his back.  (This is
different from #1.12, #1.13, and #2.12.)  (PRO)

2.12.  There is a dead man lying in the desert next to a rock.  (This is
different from #1.12, #1.13, and #2.11.)  (GH)

2.13.  As a man jumps out of a window, he hears the telephone ring and
regrets having jumped.  (from "Some Days are Like That," by Bruce J.
Balfour; partial JM wording)

2.14.  Two people are playing cards.  One looks around and realizes he's
going to die.  (JM original)

2.15.  A man lies dead in a room with fifty-three bicycles in front of him.

2.16.  A horse jumps over a tower and lands on a man, who disappears.  (ES
original)

2.17.  A train pulls into a station, but none of the waiting passengers move.
(MN)

2.18.  A man pushes a car up to a hotel and tells the owner he's bankrupt.
(DVS; partial AL and JM wording)

2.19.  Three large people try to crowd under one small umbrella, but nobody
gets wet.  (CC)

2.20.  A black man dressed all in black, wearing a black mask, stands at a
crossroads in a totally black-painted town.  All of the streetlights in town
are broken.  There is no moon.  A black-painted car without headlights drives
straight toward him, but turns in time and doesn't hit him.  (AL and RM
wording)

2.21.  Bob and Carol and Ted and Alice all live in the same house.  Bob and
Carol go out to a movie, and when they return, Alice is lying dead on the
floor in a puddle of water and glass.  It is obvious that Ted killed her but
Ted is not prosecuted or severely punished.

2.22.  A man rides into town on Friday.  He stays one night and leaves on
Friday.  (KK)

2.23.  Bruce wins the race, but he gets no trophy.  (EMS)

2.24.  A woman opens an envelope and dyes.  (AL)

2.25.  A man was brought before a tribal chief, who asked him a question.  If
he had known the answer, he probably would have died.  He didn't, and lived.
(MWD original)

2.26.  Two men are found dead outside of an igloo.  (SK original)

2.27.  A man is born in 1972 and dies in 1952 at the age of 25.  (DM)



Attributions key:

   When I know who first told me the current version of a puzzle, I've put
initials in parentheses after the puzzle statement; this is the key to those
acknowledgments.  The word "original" following an attribution means that, to
the best of my knowledge, the cited person invented that puzzle.  If a given
puzzle isn't marked "original" but is attributed, that just means that's the
first person I heard it from.  I would appreciate it if attributions for
originals were not removed; however, this list is hereby entered into the
public domain, so do with it what you wish.

LA == Laura Almasy               RSB == Ranjit S. Bhatnagar
CC == Chris Cole                 MC == Matt Crawford
MWD == Matthew William Daly      KD == Ken Duisenberg
SD == Sylvia Dutcher             ME == Marguerite Eisenstein
TF == Thomas Freeman             AG == Andreas Gammel
JH == Joaquin Hartman            MH == Marcy Hartman
KH == Karl Heuer                 GH == Geoff Hopcraft
DH == David Huddleston           MI == Mark Isaak
SJ == Steve Jacquot              JJ == J|rgen Jensen
KK == Karen Karp                 NK == Nev King
SK == Shelby Kilmer              KL == Ken Largman
AL == Andy Latto                 HL == Howard Lazoff
ML == Merlyn LeRoy               DM == Dan Murray
RM == "Reaper Man" (real name unknown)
TM == Ted McCabe                 JM == Jim Moskowitz
DM == Damian Mulvena             MN == Jan Mark Noworolski
PRO == Peter R. Olpe (from his list)
MP == Martin Pitwood             CR == Charles Renert
EMS == Ellen M. Sentovich (from her list)
AS == Annie Senghas              ES == Eric Stephan
DS == Diana Stiefbold            ST == Simon Travaglia
DVS == David Van Stone           RW == Randy Whitaker
MPW == Matthew P Wiener          SW == Steve Wilson (not sure of name)

Special thanks to Jim Moskowitz, Karl Heuer, and Mark Brader, for a lot of
discussion of small but important details and wording.



Notes and comments:

   My outtakes list (items removed from this list for various reasons, most
of which came down to the fact that I didn't like them) is now available from
the rec.puzzles archive server.

   There are many possible wordings for most of the puzzles in this list.
Most of them have what I consider the best wording of the variants I've
heard; if you think there's a better way of putting one or more of them, or
if you don't like my categorization of any of them, or if you have any other
comments or suggestions, please drop me a note.  If you know others not on
this list, please send them to me.
   Of course, in telling a group of players one of these situations, you can
add or remove details, either to make getting the answer harder or easier, or
simply to throw in red herrings.  I've made a few specific suggestions along
these lines in the answer list, available in a separate file.  Also in the
answer list are variant problem statements and variant answers.



Bibliography:

   The game of situation puzzles is also known by a variety of other names:
mystery questions, story riddles, lateral thinking puzzles, mini-mysteries,
minute mysteries, missing links, how come?, situational puzzles, law school
puzzles, quistels (in the Netherlands and other parts of Europe), mystery
puzzles, and so on.  I prefer the term 'situation puzzles,' but I change my
mind every few years when a new term that I like more comes along.  At any
rate, here are some sources for these puzzles, under a variety of names.
Unfortunately, almost all of these books are out of print and extremely
difficult to find.  Try inter-library loan, and be prepared to wait.  I don't
know of any such books outside of the US (though at least the Sloane book is
also printed in Canada, Europe, and Australia), but I'd be happy to include
references to such in future editions if anyone sends me bibliographical
info.
   On this edition of my list, I have included a few puzzles from these books
which I didn't previously have.  I've paraphrased them and cited the sources,
which I hope should be good enough to avoid copyright infringement; however,
I hope to contact the various copyright holders soon and get explicit
permission to include more of their puzzles.  If I fail to get that
permission, a few of the items on this list may go away in the next edition.

   _Games_ magazine (bibliographical data currently unavailable).  They ran a
situation-puzzle contest recently, but I have yet to see any of the results.

   _Math for Girls_ (bibliographical data unavailable).

   Rogers, Agnes, _How Come?_ (1953: Doubleday & Company, Inc., New York).
Library of Congress catalog number 53-5756.  OCLC #1612919.  The author may
also be listed as Agnes Rogers Allen.  With its sequel (see below), the
classic volume on the subject; is probably the original source for quite a
few standard situation puzzles, though Rogers says she does not know who
invented the form.  Nor does she know the source of most of those she
includes -- like all good folklore, situation puzzles are difficult to trace
to their origins.  Unfortunately, both these books are long out of print.
Besides their historical value, these two come furnished with delightful
illustrations of various wrong approaches to some of the puzzles.  These
versions were definitely intended to be read from the book, though; the
puzzle statements are much more long-winded than the versions in my list.

   Rogers, Agnes, and Sheehan, Richard G., _How Come -- Again?_ (1960:
Doubleday & Company, Inc., New York).  Library of Congress catalog number
60-13745.  OCLC #2580602.

   Sloane, Paul, _Lateral Thinking Puzzlers_ (1992: Sterling Publishing Co.,
Inc., 387 Park Avenue South, New York, 10016).  ISBN 0-8069-8227-6.  There's
a lot of overlap here with the rec.puzzles archives, including a lot of
puzzles that I wouldn't even consider doing as situation puzzles (such as the
infamous "12 balls" problem).  Still, it does have one or two nice situation
puzzles in it.  Warning: these are not lateral thinking puzzles in the sense
in which I like to use that phrase -- each puzzle has a definite correct
answer, and creativity and sideways leaps of logic aren't rewarded unless
they result in that answer.  Cover price $US 4.95; should be available (or
orderable) in most chain bookstores in the US.

   _Stories With Holes_ (bibliographical data unavailable).

   Weintraub, Richard, and Krieger, Richard, _Beyond the Easy Answer:
exploring new perspectives through creative problem-solving games_ (1979:
Zenger Publications, Inc., Gateway Station 802, Culver City, CA 90230).  ISBN
0-934508-00-3.  Contains a variety of puzzles and games, most of which aren't
really situation puzzles (and many of which are in the rec.puzzles archives),
plus some creativity games.  Out of print.



History of List:

   original compilation            11/28/87
   major revision                  08/09/89
   further additions               08/23/89 - 10/21/90
   variants added to answer list   07/04/90
   editing and renumbering         07/25/90 - 11/11/90
   items removed; title changed    09/20/90 - 11/11/90
   editing and additions           02/26/92 - 09/17/92
   more additions (incl. biblio.)  03/31/93 - 05/03/93



--Jed Hartman
[e-mail] (as of 5/93)
Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (logic), part 25 of 35
Message-ID: <puzzles/archive/logic/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:06:22 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 1161
Xref: senator-bedfellow.mit.edu rec.puzzles:25023 news.answers:11543 rec.answers:1943

Archive-name: puzzles/archive/logic/part4
Last-modified: 17 Aug 1993
Version: 4


==> logic/situation.puzzles.s <==
                      Jed's List of Situation Puzzles
                               (with answers)



   "A man lies dead in a room with fifty-three bicycles in front of him.
What happened?"

   This is a list of what I refer to (for lack of a better name) as situation
puzzles.  In the game of situation puzzles, a situation like the one above is
presented to a group of players, who must then try to find out more about the
situation by asking further questions.  The person who initially presented
the situation can only answer "yes" or "no" to questions (or occasionally
"irrelevant" or "doesn't matter").

   My list has been divided into two sections.  Section 1 consists of
situation puzzles which are set in a realistic world; the situations could
all actually occur.  Section 2 consists of puzzles which involve double
meanings for one or more words and those which could not possibly take place
in reality as we know it, plus a few miscellaneous others.

   See the end of the list for more notes and comments.

   This version of the list contains answers to the puzzles, as well as
variants.



Section 1: "Realistic" situation puzzles.

1.1.  In the middle of the ocean is a yacht.  Several corpses are floating in
the water nearby.  (SJ)
1.1.  A bunch of people are on an ocean voyage in a yacht.  One afternoon,
they all decide to go swimming, so they put on swimsuits and dive off the
side into the water.  Unfortunately, they forget to set up a ladder on the
side of the boat, so there's no way for them to climb back in, and they
drown.
1.1a.  Variant answer: The same situation, except that they set out a ladder
which is just barely long enough.  When they all dive into the water, the
boat, without their weight, rises in the water until the ladder is just
barely out of reach.  (also from Steve Jacquot)

1.2.  A man is lying dead in a room.  There is a large pile of gold and
jewels on the floor, a chandelier attached to the ceiling, and a large open
window.  (DVS; partial JM wording)
1.2.  The room is the ballroom of an ocean liner which sank some time ago.
The man ran out of air while diving in the wreck.
1.2a.  Variant which puts this in section 2: same statement, ending with "a
large window through which rays are coming."  Answer: the rays are manta rays
(this version tends to make people assume vampires are involved, unless they
notice the awkwardness of the phrase involving rays).

1.3.  A woman came home with a bag of groceries, got the mail, and walked
into the house.  On the way to the kitchen, she went through the living room
and looked at her husband, who had blown his brains out.  She then continued
to the kitchen, put away the groceries, and made dinner.  (partial JM
wording)
1.3.  The husband killed himself a while ago; it's his ashes in an urn on the
mantelpiece that the wife looks at.  It's debatable whether this belongs in
section 2 for double meanings.

1.4.  A body is discovered in a park in Chicago in the middle of summer.  It
has a fractured skull and many other broken bones, but the cause of death was
hypothermia.  (MI, from _Hill Street Blues_)
1.4.  A poor peasant from somewhere in Europe wants desperately to get to the
U.S.  Not having money for airfare, he stows away in the landing gear
compartment of a jet.  He dies of hypothermia in mid-flight, and falls out
when the landing gear compartment opens as the plane makes its final
approach.
1.4a.  Variant: A man is lying drowned in a dead forest.  Answer: He's scuba
diving when a firefighting plane lands nearby and fills its tanks with water,
sucking him in with the water.  He runs out of air while the plane is in
flight; the plane then dumps its load of water, with him in it, onto a
burning forest.  (from Jim Moskowitz)

1.5.  A man lives on the twelfth floor of an apartment building.  Every
morning he takes the elevator down to the lobby and leaves the building.  In
the evening, he gets into the elevator, and, if there is someone else in the
elevator -- or if it was raining that day -- he goes back to his floor
directly.  However, if there is nobody else in the elevator and it hasn't
rained, he goes to the 10th floor and walks up two flights of stairs to his
room.  (MH)
1.5.  The man is a midget.  He can't reach the upper elevator buttons, but he
can ask people to push them for him.  He can also push them with his
umbrella.  I've usually heard this stated with more details: "Every morning
he wakes up, gets dressed, eats, goes to the elevator..."  Ron Carter
suggests a nice red herring: the man lives on the 13th floor of the building.

1.6.  A woman has incontrovertible proof in court that her husband was
murdered by her sister.  The judge declares, "This is the strangest case I've
ever seen.  Though it's a cut-and-dried case, this woman cannot be punished."
(This is different from #1.43.)  (MH)
1.6.  The sisters are Siamese twins.
1.6a.  Variant: A man and his brother are in a bar drinking.  They begin to
argue (as always) and the brother won't get out of the man's face, shouting
and cursing.  The man, finally fed up, pulls out a pistol and blows his
brother's brains out.  He sits down to die.  Answer: They are Siamese twins.
In the original story, the argument started when one complained about the
other's bad hygiene and bad breath.  The shooter bled to death (from his
brother's wounds) by the time the police arrived.  (from Randy Whitaker,
based on a 1987 _Weekly World News_ story)

1.7.  A man walks into a bar and asks for a drink.  The bartender pulls out a
gun and points it at him.  The man says, "Thank you," and walks out.  (DVS)
1.7.  The man has hiccups; the bartender scares them away by pulling a gun.

1.8.  A man is returning from Switzerland by train.  If he had been in a
non-smoking car he would have died.  (DVS; MC wording)
1.8.  The man used to be blind; he's now returning from an eye operation
which restored his sight.  He's spent all his money on the operation, so when
the train (which has no internal lighting) goes through a tunnel he at first
thinks he's gone blind again and almost decides to kill himself.
Fortunately, the light of the cigarettes people are smoking convinces him
that he can still see.
1.8a.  Variant: A man dies on a train he does not ordinarily catch.  Answer:
The man (a successful artist) has had an accident in which he injured his
eyes.  His head is bandaged and he has been warned not to remove the bandages
under any circumstances lest the condition be irreversibly aggravated.  He
catches the train home from the hospital and cannot resist peeking.  Seeing
nothing at all (the same train-in-tunnel situation as above obtains, but
without the glowing cigarettes this time), he assumes he is blinded and kills
himself in grief.  I like this version a lot, except that it makes much less
sense that he'd be traveling alone.  (from Bernd Wechner)

1.9.  A man goes into a restaurant, orders abalone, eats one bite, and kills
himself.  (TM and JM wording)
1.9.  The man was in a ship that was wrecked on a desert island.  When there
was no food left, another passenger brought what he said was abalone but was
really part of the man's wife (who had died in the wreck).  The man suspects
something fishy, so when they finally return to civilization, he orders
abalone, realizes that what he ate before was his wife, and kills himself.
1.9a.  Variant: same problem statement but with albatross instead of abalone.
Answer: In this version, the man was in a lifeboat, with his wife, who died.
He hallucinated an albatross landing in the boat which he caught and killed
and ate; he thought that his wife had been washed overboard.  When he
actually eats albatross, he discovers that he had actually eaten his wife.
1.9b.  Variant answer to 1.9a, with a slightly different problem statement:
the man already knew that he had been eating human flesh.  He asks the waiter
in the restaurant what kind of soup is available, and the waiter responds,
"Albatross soup."  Thinking that "albatross soup" means "human soup," and
sickened by the thought of such a society (place in a foreign country if
necessary), he kills himself.  (from Mike Neergaard)

1.10.  A man is found hanging in a locked room with a puddle of water under
his feet.  (This is different from #1.11.)
1.10.  He stood on a block of ice to hang himself.  The fact that there's no
furniture in the room can be added to the statement, but if it's mentioned in
conjunction with the puddle of water the answer tends to be guessed more
easily.

1.11.  A man is dead in a puddle of blood and water on the floor of a locked
room.  (This is different from #1.10.)
1.11.  He stabbed himself with an icicle.

1.12.  A man is lying, dead, face down in the desert wearing a backpack.
(This is different from #1.13, #2.11, and #2.12.)
1.12.  He jumped out of an airplane, but his parachute failed to open.  Minor
variant wording (from Joe Kincaid): he's on a mountain trail instead of in a
desert.  Minor variant wording (from Mike Reymond): he's got a ring in his
hand (it came off of the ripcord).
1.12a.  Silly variant: same problem statement, with the addition that one of
the man's shoelaces is untied.  Answer: He pulled his shoelace instead of the
ripcord.
1.12b.  Variant answer: The man was let loose in the desert with a pack full
of poisoned food.  He knows it's poisoned, and doesn't eat it -- he dies of
hunger.  (from Mike Neergaard)

1.13.  A man is lying face down, dead, in the desert, with a match near his
outstretched hand.  (This is different from #1.12, #2.11, and #2.12.)  (JH;
partial JM wording)
1.13.  He was with several others in a hot air balloon crossing the desert.
The balloon was punctured and they began to lose altitude.  They tossed all
their non-essentials overboard, then their clothing and food, but were still
going to crash in the middle of the desert.  Finally, they drew matches to
see who would jump over the side and save the others; this man lost.  Minor
variant wording: add that the man is nude.

1.14.  A man is driving his car.  He turns on the radio, listens for five
minutes, turns around, goes home, and shoots his wife.  (This is different
from #1.15.)
1.14.  The radio program is one of the call-up-somebody-and-ask-them-a-
question contest shows; the announcer gives the phone number of the man's
bedroom phone as the number he's calling, and a male voice answers.  It's
been suggested that such shows don't usually give the phone number being
called; so instead the wife's name could be given as who's being called, and
there could be appropriate background sounds when the other man answers the
phone.

1.15.  A man driving his car turns on the radio.  He then pulls over to the
side of the road and shoots himself.  (This is different from #1.14.)
1.15.  He worked as a DJ at a radio station.  He decided to kill his wife,
and so he put on a long record and quickly drove home and killed her,
figuring he had a perfect alibi: he'd been at work.  On the way back he turns
on his show, only to discover that the record is skipping.
1.15a.  Variant: The music stops and the man dies.  Answer: The same, except
it's a tape breaking instead of a record skipping.  (from Michael Killianey)
(See also #1.16, #1.19e, and #1.34a.)

1.16.  Music stops and a woman dies.  (DVS)
1.16.  The woman is a tightrope walker in a circus.  Her act consists of
walking the rope blindfolded, accompanied by music, without a net.  The
musician (organist, or calliopist, or pianist, or whatever) is supposed to
stop playing when she reaches the end of the rope, telling her that it's safe
to step off onto the platform.  For unknown reasons (but with murderous
intent), he stops the music early, and she steps off the rope to her death.
1.16a.  Variant answer: The woman is a character in an opera, who "dies" at
the end of her song.
1.16b.  Variant answer: The "woman" is the dancing figure atop a music box,
who "dies" when the box runs down.  (Both of the above variants would
probably require placing this puzzle in section 2 of the list.)
1.16c.  Variant: Charlie died when the music stopped.  Answer: Charlie was an
insect sitting on a chair; the music playing was for the game Musical Chairs.
(from Bob Philhower)
(See also #1.15a, #1.19e, and #1.34a.)

1.17.  A man is dead in a room with a small pile of pieces of wood and
sawdust in one corner.  (from "Coroner's Inquest," by Marc Connelly)
1.17.  The man is a blind midget, the shortest one in the circus.  Another
midget, jealous because he's not as short, has been sawing small pieces off
of the first one's cane every night, so that every day he thinks he's taller.
Since his only income is from being a circus midget, he decides to kill
himself when he gets too tall.
1.17a.  Slightly variant answer: Instead of sawing pieces off of the midget's
cane, someone has sawed the legs off of his bed.  He wakes up, stands up, and
thinks he's grown during the night.
1.17b.  Variant: A pile of sawdust, no net, a man dies.  Answer: A midget is
jealous of the clown who walks on stilts.  He saws partway through the
stilts; the clown walks along and falls and dies when they break.  (from
Peter R. Olpe)

1.18.  A flash of light, a man dies.  (ST original)
1.18.  The man is a lion-tamer, posing for a photo with his lions.  The lions
react badly to the flash of the camera, and the man can't see properly, so he
gets mauled.
1.18a.  Variant: He couldn't find a chair, so he died.  Answer: He was a
lion-tamer.  This one is kind of silly, but I like it, and it sounds possible
to me (though I'm told a whip is more important than a chair to a
lion-tamer).  (from "Reaper Man," with Karl Heuer wording)

1.19.  A rope breaks.  A bell rings.  A man dies.  (KH)
1.19.  A blind man enjoys walking near a cliff, and uses the sound of a buoy
to gauge his distance from the edge.  One day the buoy's anchor rope breaks,
allowing the buoy to drift away from the shore, and the man walks over the
edge of the cliff.
1.19a.  Variant: A bell rings.  A man dies.  A bell rings.  Answer: A blind
swimmer sets an alarm clock to tell him when and what direction to go to
shore.  The first bell is a buoy, which he mistakenly swims to, getting tired
and drowning.  Then the alarm clock goes off.  In other variations, the first
bell is a ship's bell, and/or the second bell is a hand-bell rung by a friend
on shore at a pre-arranged time.
1.19b.  Variant answer to 1.19a: The man falls off a belltower, pulling the
bell-cord (perhaps he was climbing a steeple while hanging onto the rope),
and dies.  The second bell is one rung at his funeral.  Could also be a
variant on 1.19 (as suggested by Mike Neergaard): the bell-cord breaks when
he falls (and there's no second bell involved).
1.19c.  Variant answer to 1.19a: The man is a boxer.  The first bell signals
the start of a round; the second is either the end of the round or a funeral
bell after he dies during the match.  Could also be a variant on 1.19 (as
suggested by Mike Neergaard): a boxing match in which the top rope breaks,
tumbling a boxer to the floor (and he dies of a concussion).
1.19d.  Variant: The wind stopped blowing and the man died.  Answer: The sole
survivor of a shipwreck reached a desert isle.  Unfortunately, he was blind.
Luckily, there was a freshwater spring on the island, and he rigged the
ship's bell (which had drifted to the island also) at the spring's location.
The bell rang in the wind, directing him to water.  When he was becalmed for
a week, he could not find water again, and so he died of thirst.  (from Peter
R. Olpe)
1.19e.  Variant: The music stopped and the man died.  Answer: Same as 1.19a,
but the blind swimmer kept a portable transistor radio on the beach instead
of a bell.  When the batteries gave out, he got lost and drowned.  (from Joe
Kincaid) (See also #1.15a, #1.16, and #1.34a.)

1.20.  A woman buys a new pair of shoes, goes to work, and dies.  (DM)
1.20.  The woman is the assistant to a (circus or sideshow) knife-thrower.
The new shoes have higher heels than she normally wears, so that the thrower
misjudges his aim and one of his knives kills her during the show.
1.20a.  Variant: A woman sees her husband entering a certain place of
business and insists on dissolving their partnership.  Answer: The husband is
a knife-thrower; the woman is his assistant as well as his wife.  She sees
him going into an optometrist's office and decides that if he's having
trouble with his eyes she doesn't want him throwing knives at her.  (from
_How Come -- Again?_)

1.21.  A man is riding a subway.  He meets a one-armed man, who pulls out a
gun and shoots him.  (SJ)
1.21.  Several men were shipwrecked together.  They agreed to survive by
eating each other a piece at a time.  Each of them in turn gave up an arm,
but before they got to the last man, they were rescued.  They all demanded
that the last man live up to his end of the deal.  Instead, he killed a bum
and sent the bum's arm to the others in a box to "prove" that he had
fulfilled the bargain.  Later, one of them sees him on the subway, holding
onto an overhead ring with the arm he supposedly cut off; the other realizes
that the last man cheated, and kills him.
1.21a.  Variant wording: A man sends a package to someone in Europe and gets
a note back saying "Thank you.  I received it."  Answer: This is just a
simpler version; the shipwreck situation is the same, and the man actually
did send his own arm.
1.21b.  Variant wording: Two men throw a box off of a cliff.  Answer: Exactly
the same situation as in 1.21a (one slight variation has a hand in the box
instead of a whole arm), with the two men being two of the fellow passengers
who had already lost their arms.
1.21c.  Variant wording: A man in a Sherlock Holmes-style cape walks into a
room, places a box on the table and leaves.  Answer: In this one he's wearing
the cape either to disguise the fact that he hasn't really cut off his
arm/hand as required, or else simply in order to hide his now-missing limb.
(from Joe Kincaid)

1.22.  Two women are talking.  One goes into the bathroom, comes out five
minutes later, and kills the other.
1.22.  Both women are white; the one whose house this takes place in is
single.  A black friend of the other woman, the one who goes into the
bathroom, was recently killed, reportedly by the KKK.  The woman who goes
into the bathroom discovers a bloodstained KKK robe in the other's laundry
hamper, picks up a nail file from the medicine cabinet (or some other
impromptu weapon), and goes out and kills the other.
1.22a.  Variant: A man goes to hang his coat and realizes he will die that
day.  Answer: The man (who is black) has car trouble and is in need of a
telephone.  He asks at the nearest house and on being invited in goes to hang
his coat, whereupon he notices the white robes of the Ku Klux Klan in the
closet.  (from Bernd Wechner)

1.23.  A man is sitting in bed.  He makes a phone call, saying nothing, and
then goes to sleep.  (SJ)
1.23.  He is in a hotel, and is unable to sleep because the man in the
adjacent room is snoring.  He calls the room next door (from his own room
number he can easily figure out his neighbor's, and from the room number, the
telephone number).  The snorer wakes up, answers the phone.  The first man
hangs up without saying anything and goes to sleep before the snorer gets
back to sleep and starts snoring again.
1.23a.  Slightly variant answer: It's a next-door neighbor in an apartment
building who's snoring, rather than in a hotel.  The caller thus knows his
neighbor and the phone number.

1.24.  A man kills his wife, then goes inside his house and kills himself.
(DH original, from "Nightmare in Yellow," by Fredric Brown)
1.24.  It's the man's fiftieth birthday, and in celebration of this he plans
to kill his wife, then take the money he's embezzled and move on to a new
life in another state.  His wife takes him out to dinner; afterward, on their
front step, he kills her.  He opens the door, dragging her body in with him,
and all the lights suddenly turn on and a group of his friends shout
"Surprise!"  He kills himself.  (Note that the whole first part, including
the motive, isn't really necessary; it was just part of the original story.)

1.25.  Abel walks out of the ocean.  Cain asks him who he is, and Abel
answers.  Cain kills Abel.  (MWD original)
1.25.  Abel is a prince of the island nation that he landed on.  A cruel and
warlike prince, he waged many land and naval battles along with his father
the king.  In one naval encounter, their ship sank, the king died, and the
prince swam to a deserted island where he spent several months building a
raft or small boat.  In the meantime, a regent was appointed to the island
nation, and he brought peace and prosperity.  When Prince Abel returned to
his kingdom, Cain (a native fisherman) realized that the peace of the land
would only be maintained if Abel did not reascend to his throne, and killed
the prince (with a piece of driftwood or some other impromptu weapon).

1.26.  Two men enter a bar.  They both order identical drinks.  One lives;
the other dies.  (CR; partial JM wording)
1.26.  The drinks contain poisoned ice cubes; one man drinks slowly, giving
them time to melt, while the other drinks quickly and thus doesn't get much
of the poison.  The fact that they drink at different speeds could be added
to the statement, possibly along with red herrings such as saying that one of
the men is big and burly and the other short and thin.

1.27.  Joe leaves his house, wearing a mask and carrying an empty sack.  An
hour later he returns.  The sack is now full.  He goes into a room and turns
out the lights.  (AL)
1.27.  Joe is a kid who goes trick-or-treating for Halloween.

1.28.  A man takes a two-week cruise to Mexico from the U.S.  Shortly after
he gets back, he takes a three-day cruise which doesn't stop at any other
ports.  He stays in his cabin all the time on both cruises.  As a result, he
makes $250,000.  (MI, from "The Wager")
1.28.  He's a smuggler.  On the first cruise, someone brings the contraband
to his cabin, and he hides it in an air conditioning duct.  Returning to the
U.S., he leaves without the contraband, and so passes through customs with no
trouble.  On the second trip, he has the same cabin on the same ship.
Because it doesn't stop anywhere, he doesn't have to go through customs when
he returns, so he gets the contraband off safely.

1.29.  Hans and Fritz are German spies during World War II.  They try to
enter America, posing as returning tourists.  Hans is immediately arrested.
(JM)
1.29.  Hans and Fritz do everything right up until they're filling out a
personal-information form and have to write down their birthdays.  Fritz'
birthday is, say, July 7, so he writes down 7/7/15.  Hans, however, was born
on, say, June 20, so he writes down 20/6/18 instead of what an American would
write, 6/20/18.  Note that this is only a problem because they *claim* to be
returning Americans; as has been pointed out to me, there are lots of other
nations which use the same date ordering.

1.30.  Tim and Greg were talking.  Tim said "The terror of flight."  Greg
said "The gloom of the grave."  Greg was arrested.  (MPW original, from "No
Refuge Could Save," by Isaac Asimov)
1.30.  Another WWII story.  Greg is a German spy.  His "friend" Tim is
suspicious, so he plays a word-association game with him.  When Tim says "The
land of the free," Greg responds with "The home of the brave."  Then Tim says
"The terror of flight," and Greg says "The gloom of the grave."  Any U.S.
citizen knows the first verse of the national anthem, but only a spy would
have memorized the third verse.  (Why Tim knew the third verse is left as an
exercise to the reader.)

1.31.  A man is found dead in his parked car.  Tire tracks lead up to the car
and away.  (SD)
1.31.  The dead man was the driver in a hit-and-run accident which paralyzed
its victim.  The victim did manage to get the license plate number of the
car; now in a wheelchair, he eventually tracked down the driver and shot and
killed him.

1.32.  A man dies in his own home.  (ME original)
1.32.  His home is a houseboat and he has run out of water while on an
extended cruise.
1.32a.  Variant wording: A man dies of thirst in his own home.  This version
goes more quickly because it gives more information; but it may be less
likely to annoy people who think the original statement is too vague.

1.33.  A woman in France in 1959 is waiting in her room, with all the doors
locked from the inside, for her husband to come home.  When he arrives, the
house has burned to the ground and she's dead.  (JM, from _How Come --
Again?_)
1.33.  This is apparently a true story.  The hot sun reflected from the
woman's large mirror (which I speculate may have been imperfectly flat and
therefore focused the sunlight, but I don't know for sure) and heated the
lingerie she was wearing to the burning point.  She was absorbed in a book at
the time and didn't notice the heat until her clothing was afire.  Nobody
could get to her to help because her doors were locked from the inside.
Please disregard the version of this answer from previous editions of this
list; it's not true.

1.34.  A man gets onto an elevator.  When the elevator stops, he knows his
wife is dead.  (LA; partial KH wording)
1.34.  He's leaving a hospital after visiting his wife, who's on heavy
life-support.  When the power goes out, he knows she can't live without the
life-support systems (he assumes that if the emergency backup generator were
working, the elevator wouldn't lose power; this aspect isn't entirely
satisfactory, so in a variant, the scene is at home rather than in a
hospital).
1.34a.  Variant: The music stops and a woman dies.  Answer: The woman is
confined in an iron lung, and the music is playing on her radio or stereo.
The power goes out.  (from Randy Whitaker) (See also #1.15a, #1.16, and
#1.19e.)

1.35.  Three men die.  On the pavement are pieces of ice and broken glass.
(JJ)
1.35.  A large man comes home to the penthouse apartment he shares with his
beautiful young wife, taking the elevator up from the ground floor.  He sees
signs of lovemaking in the bedroom, and assumes that his wife is having an
affair; her beau has presumably escaped down the stairs.  The husband looks
out the French windows and sees a good-looking man just leaving the main
entrance of the building.  The husband pushes the refrigerator out through
the window onto the young man below.  The husband dies of a heart attack from
overexertion; the young man below dies from having a refrigerator fall on
him; and the wife's boyfriend, who was hiding inside the refrigerator, also
dies from the fall.

1.36.  She lost her job when she invited them to dinner.  (DS original)
1.36.  Let's say "she" is named Suzy, and "they" are named Harry and Jane.
Harry is an elderly archaeologist who has found a very old skeleton, which
he's dubbed "Jane" (a la "Lucy").  Suzy is a buyer for a museum; she's
supposed to make some sort of purchase from Harry, so she invites him to have
a business dinner with her (at a restaurant).  When she calls to invite him,
he keeps talking about "Jane," so Suzy assumes that Jane is his wife and says
to bring her along.  Harry, offended, calls Suzy's boss and complains; since
Suzy should've known who Jane was, she gets fired.

1.37.  A man is running along a corridor with a piece of paper in his hand.
The lights flicker and the man drops to his knees and cries out, "Oh no!"
(MP)
1.37.  The man is delivering a pardon, and the flicker of the lights
indicates that the person to be pardoned has just been electrocuted.

1.38.  A car without a driver moves; a man dies.  (EMS)
1.38.  The murderer sets the car on a slope above the hot dog stand where the
victim works.  He then wedges an ice block in the car to keep the brake pedal
down, and puts the car in neutral, after which he flies to another city to
avoid suspicion.  It's a warm day; when the ice melts, the car rolls down the
hill and strikes the hot dog man at his roadside stand, killing him.

1.39.  As I drive to work on my motorcycle, there is one corner which I go
around at a certain speed whether it's rainy or sunny.  If it's cloudy but
not raining, however, I usually go faster.  (SW original)
1.39.  There's a car wash on that corner.  On rainy days, the rain reduces
traction.  On sunny days, water from the car wash has the same effect.  If
rain is threatening, though, the car wash gets little business and thus
doesn't make the road wet, so I can take the corner faster.

1.40.  A woman throws something out a window and dies.  (JM)
1.40.  The object she throws is a boomerang.  It flies out, loops around, and
comes back and hits her in the head, killing her.  Boomerangs do not often
return so close to the point from which they were thrown, but I believe it's
possible for this to happen.
1.40a.  Silly variant answer: She's in a submarine or spacecraft and throws a
heavy object at the window, which breaks.

1.41.  An avid birdwatcher sees an unexpected bird.  Soon he's dead.  (RSB
original)
1.41.  He is a passenger in an airplane and sees the bird get sucked into an
engine at 20,000 feet.

1.42.  There are a carrot, a pile of pebbles, and a pipe lying together in
the middle of a field.  (PRO; partial JM wording)
1.42.  They're the remains of a melted snowman.

1.43.  Two brothers are involved in a murder.  Though it's clear that one of
them actually committed the crime, neither can be punished.  (This is
different from #1.6.)  (from "Unreasonable Doubt," by Stanley Ellin)
1.43.  One of the brothers (A) confesses to the murder.  At his trial, his
brother (B) is called as the only defense witness; B immediately confesses,
in graphic detail, to having committed the crime.  The defense lawyer refuses
to have the trial stopped, and A is acquitted under the "reasonable doubt"
clause.  Immediately afterward, B goes on trial for the murder; A is called
as the only defense witness and HE confesses.  B is declared innocent; and
though everyone knows that ONE of them did it, how can they tell who?
Further, neither can be convicted of perjury until it's decided which of them
did it...  I don't know if that would actually work under the US legal
system, but someone else who heard the story said that his father was on the
jury for a VERY similar case in New York some years ago.  Mark Brader points
out that the brothers might be convicted of conspiracy to commit perjury or
to obstruct justice, or something of that kind.

1.44.  An ordinary American citizen, with no passport, visits over thirty
foreign countries in one day.  He is welcomed in each country, and leaves
each one of his own accord.  (PRO)
1.44.  He is a mail courier who delivers packages to the different foreign
embassies in the United States.  The land of an embassy belongs to the
country of the embassy, not to the United States.

1.45.  If he'd turned on the light, he'd have lived.  (JM)
1.45.  A man was shot during a robbery in his store one night.  He staggered
into the back room, where the telephone was, and called home, dialing by feel
since he hadn't turned on the light.  Once the call went through he gasped,
"I'm at the store.  I've been shot.  Help!" or words to that effect.  He set
the phone down to await help, but none came; he'd treated the telephone
pushbuttons like cash register numbers, when the arrangements of the numbers
are upside down reflections of each other.  The stranger he'd dialed had no
way to know where "the store" was.

1.46.  A man is found dead on the floor in the living room.  (ME original)
1.46.  The dead man was playing Santa Claus, for whatever reason; he slipped
while coming down the chimney and broke his neck.
1.46a.  Variant answer: The dead man WAS Santa Claus.  This moves the puzzle
to section 2 as far as I'm concerned.

1.47.  A man is found dead outside a large building with a hole in him.  (JM,
modified from PRO)
1.47.  The man was struck by an object thrown from the roof of the Empire
State Building.  Originally I had the object being a penny, but several
people suggested that a penny probably wouldn't be enough to penetrate
someone's skull.  Something aerodynamic and heavier, like a dart, was
suggested, but I don't know how much mass would be required.
1.47a.  Variant: A man is found dead outside a large marble building with
three holes in him.  Answer: The man was a paleontologist working with the
Archaeological Research Institute.  He was reviving a triceratops frozen in
the ice age when it came to life and killed him.  This couldn't possibly
happen because triceratops didn't exist during the ice age.  (from Peter R.
Olpe)

1.48.  A man is found dead in an alley lying in a red pool with two sticks
crossed near his head.  (PRO)
1.48.  The man died from eating a poisoned popsicle.

1.49.  A man lies dead next to a feather.  (PRO)
1.49.  The man was a sword swallower in a carnival side-show.  While he was
practicing, someone tickled his throat with the feather, causing him to gag.

1.50.  There is blood on the ceiling of my bedroom.  (MI original)
1.50.  A mosquito bit me, and I swatted it when it later landed on my ceiling
(so the blood is my own as well as the mosquito's).

1.51.  A man wakes up one night to get some water.  He turns off the light
and goes back to bed.  The next morning he looks out the window, screams, and
kills himself.  (CR; KK wording)
1.51.  The man is a lighthouse keeper.  He turns off the light in the
lighthouse and during the night a ship crashes on the rocks.  Seeing this the
next morning, the man realizes what he's done and commits suicide.
1.51a.  Variant, similar to #1.15: The light goes out and a man dies.
Answer: The lighthouse keeper uses his job as an alibi while he's elsewhere
committing a crime, but the light goes out and a ship crashes, thereby
disproving the alibi.  The lighthouse keeper kills himself when he realizes
his alibi is no good.  (From Eric Wang)
1.51b.  Variant answer to 1.51a: Someone else's alibi is disproven.  (A man
commits a heinous crime, claiming as his alibi that he was onboard a certain
ship.  When he learns that it was wrecked without reaching port safely, he
realizes that his alibi is disproven and commits suicide to avoid being sent
to prison.)  (From Eric Wang)

1.52.  She grabbed his ring, pulled on it, and dropped it.  (JM, from _Math
for Girls_)
1.52.  They were skydiving.  He broke his arm as he jumped from the plane by
hitting it on the plane door; he couldn't reach his ripcord with his other
arm.  She pulled the ripcord for him.
1.52a.  Sketch of variant answer: The ring was attached to the pin of a
grenade that he was holding.  Develop a situation from there.

1.53.  A man sitting on a park bench reads a newspaper article headlined
"Death at Sea" and knows a murder has been committed.
1.53.  The man is a travel agent.  He had sold someone two tickets for an
ocean voyage, one round-trip and one one-way.  The last name of the man who
bought the tickets is the same as the last name of the woman who "fell"
overboard and drowned on the same voyage, which is the subject of the article
he's reading.

1.54.  A man tries the new cologne his wife gave him for his birthday.  He
goes out to get some food, and is killed.  (RW original)
1.54.  The man is a beekeeper, and the bees attack en masse because they
don't recognize his fragrance.  Randy adds that this is based on something
that actually happened to his grandfather, a beekeeper who was severely
attacked by his bees when he used a new aftershave for the first time in 10
or 20 years.

1.55.  A man in uniform stands on the beach of a tropical island.  He takes
out a cigarette, lights it, and begins smoking.  He takes out a letter and
begins reading it.  The cigarette burns down between his fingers, but he
doesn't throw it away.  He cries.  (RW)
1.55.  He is a guard / attendant in a leper colony.  The letter (to him)
tells him that he has contracted the disease.  The key is the cigarette
burning down between his fingers -- leprosy is fairly unique in killing off
sensory nerves without destroying motor ability.

1.56.  A man went into a restaurant, had a large meal, and paid nothing for
it.  (JM original)
1.56.  The man was a famous artist.  A woman who collected autographs saw him
dining; after he left the restaurant, she purchased the check that he used to
pay for the meal from the restaurant manager.  The check was therefore never
cashed, so the artist never paid for the meal.

1.57.  A married couple goes to a movie.  During the movie the husband
strangles the wife.  He is able to get her body home without attracting
attention.  (from _Beyond the Easy Answer_)
1.57.  The movie is at a drive-in theatre.

1.58.  A man ran into a fire, and lived.  A man stayed where there was no
fire, and died.  (Eric Wang original)
1.58.  The two men were working in a small room protected by a carbon dioxide
gas fire extinguisher system, when a fire broke out in an adjoining room.
One of the men ran through the fire and escaped with only minor burns.  The
other one stayed in the room until the fire extinguishers kicked in, and died
of oxygen starvation.  (This originally involved a halon gas extinguisher,
but those don't work that way; fortunately, Gisle Hannemyr pointed out that
CO2 extinguishers do work that way.  Gisle says a CO2 extinguisher on a
Norwegian ship a few years ago did go off accidentally when there was no
fire, killing everyone in the engine room.)

1.59.  A writer with an audience of millions insisted that he was never to be
interrupted while writing.  After the day when he actually was interrupted,
he never wrote again.  (JM, from _How Come?_)
1.59.  He was a skywriter whose plane crashed into another plane.

1.60.  Beulah died in the Appalachians, while Craig died at sea.  Everyone
was much happier with Craig's death.  (JM, from _How Come?_)
1.60.  Beulah and Craig were hurricanes.

1.61.  Mr. Browning is glad the car ran out of gas.  (JM, from _Home Come?_)
1.61.  Mr. and Mrs. Browning had just gotten married.  Mrs. Browing was
subject to fits of depression.  They had their first fight soon after they
were married; Mr. Browning stormed out of the house, and Mrs.  Browning went
into the garage and started up the car, intending to kill herself by filling
the garage with car exhaust.  But the car ran out of gas quickly, and Mr.
Browning, returning home to apologize, found Mrs. Browning in time to summon
help and restore her to health.

1.62.  A man is sitting suspended over two pressurized containers.  Suddenly,
he dies.  (NK original)
1.62.  He's riding a bicycle or motorcycle, and he crashes and dies.

1.63.  A man leaves a motel room, goes to his car, and honks the horn.  (AS
original)
1.63.  It's the middle of the night.  The man goes outside to get something
from his car, but as the parking lot is set apart from the building, he
forgets which room he was in.  His wife is deaf, so he honks the car horn
loudly, waking up everyone else in the motel.  The other residents all get up
and turn on their room lights; the man then returns to the one dark room.

1.64.  Two dead people sit in their cars on a street.  (AG)
1.64.  Because there was a heavy fog, two people driving in opposite
directions on the same road both stuck their heads out of their windows to
better see the road's center line.  Their heads hit each other at high speed,
killing them both.  Andreas says this is based on an actual accident.

1.65.  A woman lies dead in the street near a car.  (AG)
1.65.  She was on a motorcycle, and her long hair got caught on the car's
antenna.  It ripped out part of her scalp and she bled to death.  Andreas
says this is also based on an actual accident.

1.66.  A riverboat filled with passengers suddenly capsized, drowning most of
those aboard.  (from _How Come -- Again?_)
1.66.  The boat was moving along a river in India when a large snake dropped
onto the deck.  The passengers all rushed to the other side of the boat,
thereby overturning it.  This is apparently based on a true incident reported
in the _World Almanac_.



Section 2: Double meanings, fictional settings, and miscellaneous others.

2.1.  A man shoots himself, and dies.  (HL) (This is different from #2.2.)
2.1.  The man is a heroin addict, and has contracted AIDS by using an
infected needle.  In despair, he shoots himself up with an overdose, thereby
committing suicide.

2.2.  A man walks into a room, shoots, and kills himself.  (HL) (This is
different from #2.1.)
2.2.  The man walks into a casino and goes to the craps table.  He bets all
the money he owns, and shoots craps.  Since he is now broke, he becomes
despondent and commits suicide.

2.3.  Adults are holding children, waiting their turn.  The children are
handed (one at a time, usually) to a man, who holds them while a woman shoots
them.  If the child is crying, the man tries to stop the crying before the
child is shot.  (ML)
2.3.  Kids getting their pictures taken with Santa.  I see #2.1, #2.2, and
#2.3 as different enough from each other to merit separate numbers, although
they all rely on the same basic gimmick of alternate meanings of the word
"shoot."

2.4.  Hiking in the mountains, you walk past a large field and camp a few
miles farther on, at a stream.  It snows in the night, and the next day you
find a cabin in the field with two dead bodies inside.  (KL; KD and partial
JM wording)
2.4.  It's the cabin of an airplane that crashed there because of the
snowstorm.
2.4a.  Variant wording: A cabin, on the side of a mountain, locked from the
inside, is opened, and 30 people are found dead inside.  They had plenty of
food and water.  (from Ron Carter)

2.5.  A man marries twenty women in his village but isn't charged with
polygamy.
2.5.  He's a priest; he is marrying them to other people, not to himself.

2.6.  A man is alone on an island with no food and no water, yet he does not
fear for his life.  (MN)
2.6.  The "island" is a traffic island.

2.7.  Joe wants to go home, but he can't go home because the man in the mask
is waiting for him.  (AL wording)
2.7.  A baseball game is going on.  The base-runner sees the catcher waiting
at home plate with the ball, and so decides to stay at third base to avoid
being tagged out.
2.7a.  Variant: Two men are in a field.  One is wearing a mask.  The other
man is running towards him to avoid him.  Answer: the same, but the catcher
isn't right at home plate; the runner is trying to get home before the
catcher can.  (from Hal Lowery, by way of Chris Riley)  This phrasing would
allow the puzzle to migrate to section 1, but I don't like it as much.

2.8.  A man is doing his job when his suit tears.  Fifteen minutes later,
he's dead.  (RM)
2.8.  The man is an astronaut out on a space walk.

2.9.  A dead man lies near a pile of bricks and a beetle on top of a book.
(MN)
2.9.  The man was an amateur mechanic, the book is a Volkswagen service
manual, the beetle is a car, and the pile of bricks is what the car fell off
of.

2.10.  At the bottom of the sea there lies a ship worth millions of dollars
that will never be recovered.  (TF original)
2.10.  The Eagle landed in the Sea of Tranquility and will likely remain
there for the foreseeable future.

2.11.  A man is found dead in the arctic with a pack on his back.  (This is
different from #1.12, #1.13, and #2.12.)  (PRO)
2.11.  It's a wolf pack; they've killed and eaten (most of) the man.

2.12.  There is a dead man lying in the desert next to a rock.  (This is
different from #1.12, #1.13, and #2.11.)  (GH)
2.12.  The dead man is Superman; the rock is Green Kryptonite.  Invent a
reasonable scenario from there.

2.13.  As a man jumps out of a window, he hears the telephone ring and
regrets having jumped.  (from "Some Days are Like That," by Bruce J.
Balfour; partial JM wording)
2.13.  This is a post-holocaust scenario of some kind; for whatever reason,
the man believes himself to be the last human on earth.  He doesn't want to
live by himself, so he jumps, just before the telephone rings...  (of course,
it could be a computer calling, but he has no way of knowing).

2.14.  Two people are playing cards.  One looks around and realizes he's
going to die.  (JM original)
2.14.  The one who looks around sees his own reflection in the window (it's
dark outside), but not his companion's.  Thus, he realizes the other is a
vampire, and that he's going to be killed by him.

2.15.  A man lies dead in a room with fifty-three bicycles in front of him.
2.15.  The "bicycles" are Bicycle playing cards; the man was cheating at
cards, and when the extra card was found, he was killed by the other players.
2.15a.  Variant: There are 53 bees instead of 53 bicycles.  Answer: The same
(Bee is another brand of playing cards).
2.15b.  Variant: There are 51 instead of 53.  Answer: Someone saw the guy
conceal a card, and proved the deck was defective by turning it up and
pointing out the missing ace.  Or, the game was bridge, and the others
noticed the cheating when the deal didn't come out even.  The man had palmed
an ace during the shuffle and meant to put it in his own hand during the
deal, but muffed it.  (both answers from Mark Brader)

2.16.  A horse jumps over a tower and lands on a man, who disappears.  (ES
original)
2.16.  A chess game; knight takes pawn.
2.16a.  Variant: It's the year 860 A.D., at Camelot.  Two priests are sitting
in the castle's chapel.  The queen attacks the king.  The two priests rise,
shake hands, and leave the room.  Answer: The two priests are playing chess;
one of them just mated by moving his queen.  (from Ellen M. Sentovich)
2.16b.  Variant: A black leader dies in Africa.  Answer: The black leader is
a chess king, and the game was played in Africa.  (from Erick Brethenoux)

2.17.  A train pulls into a station, but none of the waiting passengers move.
(MN)
2.17.  It's a model train set.
2.17a.  Variant: The Orient Express is derailed and a kitten plays nearby.
Answer: The Orient Express is a model train which has been left running
unattended.  The kitten has playfully derailed it.  (from Bernd Wechner)

2.18.  A man pushes a car up to a hotel and tells the owner he's bankrupt.
(DVS; partial AL and JM wording)
2.18.  It's a game of Monopoly.
2.18a.  Variant: The car came out of the blue and the man came into some
money.  Answer: The same; in this case the car token passes Go and the player
collects $200.  (from "Mo," whose full name I missed)

2.19.  Three large people try to crowd under one small umbrella, but nobody
gets wet.  (CC)
2.19.  The sun is shining; there's no rain.

2.20.  A black man dressed all in black, wearing a black mask, stands at a
crossroads in a totally black-painted town.  All of the streetlights in town
are broken.  There is no moon.  A black-painted car without headlights drives
straight toward him, but turns in time and doesn't hit him.  (AL and RM
wording)
2.20.  It's daytime; the sun is out.

2.21.  Bob and Carol and Ted and Alice all live in the same house.  Bob and
Carol go out to a movie, and when they return, Alice is lying dead on the
floor in a puddle of water and glass.  It is obvious that Ted killed her but
Ted is not prosecuted or severely punished.
2.21.  Alice is a goldfish; Ted is a cat.
2.21a.  A very common variant uses the names Romeo and Juliet instead, to
further mislead audiences.  For example: Romeo is looking down on Juliet's
dead body, which is on the floor surrounded by water and broken glass.  (from
Adam Carlson)
2.21b.  Minor variant: Tom and Jean lay dead in a puddle of water with broken
pieces of glass and a baseball nearby.  Answer: Tom and Jean are both fish;
it was a baseball, rather than a cat, that broke their tank.  (from Mike
Reymond)

2.22.  A man rides into town on Friday.  He stays one night and leaves on
Friday.  (KK)
2.22.  Friday is a horse.
2.22a.  Variant with the same basic gimmick: A woman comes home, sees
Spaghetti on the wall and kills her husband.  Answer: Spaghetti was the name
of her pet dog.  Her husband had it stuffed and mounted after it made a mess
on his rug.  (Simon Travaglia original)

2.23.  Bruce wins the race, but he gets no trophy.  (EMS)
2.23.  Bruce is a horse.

2.24.  A woman opens an envelope and dyes.  (AL)
2.24.  Should be done orally; the envelope is an envelope of dye, and she's
dying some cloth, but it sounds like "opens an envelope and dies" if said out
loud.

2.25.  A man was brought before a tribal chief, who asked him a question.  If
he had known the answer, he probably would have died.  He didn't, and lived.
(MWD original)
2.25.  The native chief asked him, "What is the third baseman's name in the
Abbot and Costello routine 'Who's on First'?"  The man, who had no idea, said
"I don't know," the correct answer.  However, he was a major smartass, so if
he had known the answer he would have pointed out that What was the SECOND
baseman's name.  The chief, being quite humorless, would have executed him on
the spot.  This is fairly silly, but I like it too much to remove it from the
list.

2.26.  Two men are found dead outside of an igloo.  (SK original)
2.26.  The men have gone spelunking and have taken an Igloo cooler with them
so they can have a picnic down in the caves.  They cleverly used dry ice to
keep their beer cold, not realizing that as the dry ice sublimed (went from
solid state to vapor state) it would push the lighter oxygen out of the cave
and they would suffocate.

2.27.  A man is born in 1972 and dies in 1952 at the age of 25.  (DM)
2.27.  He's born in room number 1972 of a hospital and dies in room number
1952.  The numbers can of course vary; it was originally set up with those
numbers reversed (born in 1952, died in 1972), but I like it better this way.



Attributions key:

   When I know who first told me the current version of a puzzle, I've put
initials in parentheses after the puzzle statement; this is the key to those
acknowledgments.  The word "original" following an attribution means that, to
the best of my knowledge, the cited person invented that puzzle.  If a given
puzzle isn't marked "original" but is attributed, that just means that's the
first person I heard it from.  I would appreciate it if attributions for
originals were not removed; however, this list is hereby entered into the
public domain, so do with it what you wish.

LA == Laura Almasy               RSB == Ranjit S. Bhatnagar
CC == Chris Cole                 MC == Matt Crawford
MWD == Matthew William Daly      KD == Ken Duisenberg
SD == Sylvia Dutcher             ME == Marguerite Eisenstein
TF == Thomas Freeman             AG == Andreas Gammel
JH == Joaquin Hartman            MH == Marcy Hartman
KH == Karl Heuer                 GH == Geoff Hopcraft
DH == David Huddleston           MI == Mark Isaak
SJ == Steve Jacquot              JJ == J|rgen Jensen
KK == Karen Karp                 NK == Nev King
SK == Shelby Kilmer              KL == Ken Largman
AL == Andy Latto                 HL == Howard Lazoff
ML == Merlyn LeRoy               DM == Dan Murray
RM == "Reaper Man" (real name unknown)
TM == Ted McCabe                 JM == Jim Moskowitz
DM == Damian Mulvena             MN == Jan Mark Noworolski
PRO == Peter R. Olpe (from his list)
MP == Martin Pitwood             CR == Charles Renert
EMS == Ellen M. Sentovich (from her list)
AS == Annie Senghas              ES == Eric Stephan
DS == Diana Stiefbold            ST == Simon Travaglia
DVS == David Van Stone           RW == Randy Whitaker
MPW == Matthew P Wiener          SW == Steve Wilson (not sure of name)

Special thanks to Jim Moskowitz, Karl Heuer, and Mark Brader, for a lot of
discussion of small but important details and wording.



Notes and comments:

   My outtakes list (items removed from this list for various reasons, most
of which came down to the fact that I didn't like them) is now available from
the rec.puzzles archive server.

   There are many possible wordings for most of the puzzles in this list.
Most of them have what I consider the best wording of the variants I've
heard; if you think there's a better way of putting one or more of them, or
if you don't like my categorization of any of them, or if you have any other
comments or suggestions, please drop me a note.  If you know others not on
this list, please send them to me.
   Of course, in telling a group of players one of these situations, you can
add or remove details, either to make getting the answer harder or easier, or
simply to throw in red herrings.  I've made a few specific suggestions along
these lines in the answer list, available in a separate file.  Also in the
answer list are variant problem statements and variant answers.



Bibliography:

   The game of situation puzzles is also known by a variety of other names:
mystery questions, story riddles, lateral thinking puzzles, mini-mysteries,
minute mysteries, missing links, how come?, situational puzzles, law school
puzzles, quistels (in the Netherlands and other parts of Europe), mystery
puzzles, and so on.  I prefer the term 'situation puzzles,' but I change my
mind every few years when a new term that I like more comes along.  At any
rate, here are some sources for these puzzles, under a variety of names.
Unfortunately, almost all of these books are out of print and extremely
difficult to find.  Try inter-library loan, and be prepared to wait.  I don't
know of any such books outside of the US (though at least the Sloane book is
also printed in Canada, Europe, and Australia), but I'd be happy to include
references to such in future editions if anyone sends me bibliographical
info.
   On this edition of my list, I have included a few puzzles from these books
which I didn't previously have.  I've paraphrased them and cited the sources,
which I hope should be good enough to avoid copyright infringement; however,
I hope to contact the various copyright holders soon and get explicit
permission to include more of their puzzles.  If I fail to get that
permission, a few of the items on this list may go away in the next edition.

   _Games_ magazine (bibliographical data currently unavailable).  They ran a
situation-puzzle contest recently, but I have yet to see any of the results.

   _Math for Girls_ (bibliographical data unavailable).

   Rogers, Agnes, _How Come?_ (1953: Doubleday & Company, Inc., New York).
Library of Congress catalog number 53-5756.  OCLC #1612919.  The author may
also be listed as Agnes Rogers Allen.  With its sequel (see below), the
classic volume on the subject; is probably the original source for quite a
few standard situation puzzles, though Rogers says she does not know who
invented the form.  Nor does she know the source of most of those she
includes -- like all good folklore, situation puzzles are difficult to trace
to their origins.  Unfortunately, both these books are long out of print.
Besides their historical value, these two come furnished with delightful
illustrations of various wrong approaches to some of the puzzles.  These
versions were definitely intended to be read from the book, though; the
puzzle statements are much more long-winded than the versions in my list.

   Rogers, Agnes, and Sheehan, Richard G., _How Come -- Again?_ (1960:
Doubleday & Company, Inc., New York).  Library of Congress catalog number
60-13745.  OCLC #2580602.

   Sloane, Paul, _Lateral Thinking Puzzlers_ (1992: Sterling Publishing Co.,
Inc., 387 Park Avenue South, New York, 10016).  ISBN 0-8069-8227-6.  There's
a lot of overlap here with the rec.puzzles archives, including a lot of
puzzles that I wouldn't even consider doing as situation puzzles (such as the
infamous "12 balls" problem).  Still, it does have one or two nice situation
puzzles in it.  Warning: these are not lateral thinking puzzles in the sense
in which I like to use that phrase -- each puzzle has a definite correct
answer, and creativity and sideways leaps of logic aren't rewarded unless
they result in that answer.  Cover price $US 4.95; should be available (or
orderable) in most chain bookstores in the US.

   _Stories With Holes_ (bibliographical data unavailable).

   Weintraub, Richard, and Krieger, Richard, _Beyond the Easy Answer:
exploring new perspectives through creative problem-solving games_ (1979:
Zenger Publications, Inc., Gateway Station 802, Culver City, CA 90230).  ISBN
0-934508-00-3.  Contains a variety of puzzles and games, most of which aren't
really situation puzzles (and many of which are in the rec.puzzles archives),
plus some creativity games.  Out of print.



History of List:

   original compilation            11/28/87
   major revision                  08/09/89
   further additions               08/23/89 - 10/21/90
   variants added to answer list   07/04/90
   editing and renumbering         07/25/90 - 11/11/90
   items removed; title changed    09/20/90 - 11/11/90
   editing and additions           02/26/92 - 09/17/92
   more additions (incl. biblio.)  03/31/93 - 05/03/93



--Jed Hartman
[e-mail] (as of 5/93)

==> logic/smullyan/black.hat.p <==
Three logicians, A, B, and C, are wearing hats, which they know are either
black or white but not all white. A can see the hats of B and C; B can see
the hats of A and C; C is blind.  Each is asked in turn if they know the color
of their own hat.  The answers are:
    A: "No."
    B: "No."
    C: "Yes."
What color is C's hat and how does she know?

==> logic/smullyan/black.hat.s <==
A must see at least one black hat, or she would know that her hat is black
since they are not all white.  B also must see at least one black hat, and
further, that hat had to be on C, otherwise she would know that her
hat was black (since she knows A saw at least one black hat).  So C knows
that her hat is black, without even seeing the others' hats.

==> logic/smullyan/fork.three.men.p <==
Three men stand at a fork in the road.  One fork leads to Someplaceorother;
the other fork leads to Nowheresville.  One of these people always answers
the truth to any yes/no question which is asked of him.  The other always
lies when asked any yes/no question.  The third person randomly lies and
tells the truth.  Each man is known to the others, but not to you.
What is the least number of yes/no questions you can ask of these men and
pick the road to Someplaceorother?  Does the answer change if the third
man randomly answers?

==> logic/smullyan/fork.three.men.s <==
One question, and you only need one man of any type:
"If I were to ask you whether the left fork leads to Someplaceorother,
and you chose to answer that question with the same degree of truth as
you answer this question, would you then answer 'yes'?"

The truthteller will say "yes" if the left fork leads to Someplaceorother,
and "no" otherwise.  The liar will answer the same, since he will lie about
where the left fork leads, and he will lie about lying.  The randomizer
may either lie or tell the truth about this one question, but either way
he is behaving like either the truthteller or the liar and thus must
correctly report the road to Someplaceorother.

If however the third person randomly answers yes or no it is clear that
you must ask at least two questions, since you might be asking the
first one of the randomizer and there is nothing you can tell from his
answers.

Start by asking A "Is B more likely to tell the truth than C?"

If he answers "yes", then:
   If A is truthteller, B is randomizer, C is liar.
   If A is liar, B is randomizer, C is truthteller.
   If A is randomizer, C is truthteller or liar.

If he answers "no", then:
   If A is truthteller, B is liar, C is randomizer.
   If A is liar, B is truthteller, C is randomizer.
   If A is randomizer, B is truthteller or liar.

In either case, we now know somebody (C or B, respectively) who is
either a truthteller or liar.  Now, use the technique for finding
information from a truthteller/liar, viz., you ask him the following
question:  "If I were to ask you if the left fork leads to
Someplaceorother, would you say 'yes'?"

If the answer is "yes", take the left fork, if "no" take the right fork.

==> logic/smullyan/fork.two.men.p <==
Two men stand at a fork in the road.  One fork leads to Someplaceorother; the
other fork leads to Nowheresville.  One of these people always answers the
truth to any yes/no question which is asked of him.  The other always lies
when asked any yes/no question.  By asking one yes/no question, can you
determine the road to Someplaceorother?

==> logic/smullyan/fork.two.men.s <==
The fact that there are two is a red herring - you only need one of
either type.  You ask him the following question: "If I were to ask
you if the left fork leads to Someplaceorother, would you say 'yes'?"

If the person asked is a truthteller, he will answer "yes" if the left
fork leads to Someplaceorother, and "no" otherwise.  But so will the
liar.  So, either way, go left is the answer is "yes", and right otherwise.

It is possible, of course, that the liars are malicious, and they will tell
the truth if they figure out that you are trying to trick them.


==> logic/smullyan/integers.p <==
Two logicians place cards on their foreheads so that what is written on the
card is visible only to the other logician.  Consecutive positive integers
have been written on the cards.  The following conversation ensues:
    A: "I don't know my number."
    B: "I don't know my number."
    A: "I don't know my number."
    B: "I don't know my number."
    ... n statements of ignorance later ...
    A or B: "I know my number."
What is on the card and how does the logician know it?

==> logic/smullyan/integers.s <==
If A saw 1, she would know that she had 2, and would say so.  Therefore,
A did not see 1.  A says "I don't know my number."
If B saw 2, she would know that she had 3, since she knows that A did not see
1, so B did not see 1 or 2.  B says "I don't know my number."
If A saw 3, she would know that she had 4, since she knows that B did not
see 1 or 2, so A did not see 1, 2 or 3.  A says "I don't know my number."
If B saw 4, she would know that she had 5, since she knows that A did not
see 1, 2 or 3, so B did not see 1, 2, 3 or 4.  B says "I don't know my number."
... n statements of ignorance later ...
If X saw n, she would know that she had n + 1, since she knows that ~X did not
see 1 ... n - 1, so X did see n.  X says "I know my number."

And the number in n + 1.

==> logic/smullyan/painted.heads.p <==
While three logicians were sleeping under a tree, a malicious child painted
their heads red.  Upon waking, each logician spies the child's handiwork as
it applied to the heads of the other two.  Naturally they start laughing.
Suddenly one falls silent.  Why?

==> logic/smullyan/painted.heads.s <==
The one who fell silent, presumably the quickest of the three, reasoned
that his head must be painted also.  The argument goes as follows.
Let's call the quick one Q, and the other two D and S.  Let's assume
Q's head is untouched.  Then D is laughing because S's head is painted,
and vice versa.  But eventually, D and S will realize that their head
must be painted, because the other is laughing.  So they will quit
laughing as soon as they realize this.  So, Q waits what he thinks is
a reasonable amount of time for them to figure this out, and when they
don't stop laughing, his worst fears are confirmed.  He concludes that
his assumption is invalid and he must be crowned in crimson too.

Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (logic), part 26 of 35
Message-ID: <puzzles/archive/logic/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:06:26 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 1322
Xref: senator-bedfellow.mit.edu rec.puzzles:25010 news.answers:11530 rec.answers:1930

Archive-name: puzzles/archive/logic/part5
Last-modified: 17 Aug 1993
Version: 4


==> logic/smullyan/priest.p <==
In a small town there are N married couples in which one of the pair
has committed adultery.  Each adulterer has succeeded in keeping their
dalliance a secret from their spouse.  Since it is a small town,
everyone knows about everyone else's infidelity.  In other words, each
spouse of an adulterer thinks there are N - 1 adulterers, but everyone
else thinks there are N adulterers.

People of this town have a tradition of denouncing their spouse in
church if they are guilty of adultery.  So far, of course, no one has
been denounced.  In addition, people of this town are all amateur
logicians of sorts, and can be expected to figure out the implications
of anything they know.

A priest has heard the confession of all the people in the town, and is
troubled by the state of moral turpitude.  He cannot break the
confessional, but knowing of his flock's logical turn of mind, he hits
upon a plan to do God's work.  He announces in Mass one Sunday that
there is adultery in the town.

Is the priest correct?  Will this result in every adulterer being denounced?

==> logic/smullyan/priest.s <==
Yes.  Let's start with the simple case that N = 1.  The offended spouse
reasons as follows: the priest knows there is at least one adulterer,
but I don't know who this person is, and I would if it were anyone
other than me, so it must be me.  What happens if N = 2?  On the first
Sunday, the two offended spouses each calmly wait for the other to get
up and condemn their spouses.  When the other doesn't stand, they
think:  They do not think that they are a victim.  But if they do not
think they are victims, then they must think there are no adulterers,
contrary to what the priest said.  But everyone knows the priest speaks
with the authority of God, so it is unthinkable that he is mistaken.
The only remaining possibility is that they think there WAS another
adulterer, and the only possibility is: MY SPOUSE!  So, they know that
they too must be victims.  So on the next Sunday, they will get up.
What if N = 3?  On the first Sunday, each victim believes that the other
two will not get up because they did not know about the other person
(in other words, they believe that each of the two other victims thought
there was only one adulterer).  However, each victim reasons, the two
will now realize that there must be two victims, for the reasons given
under the N = 2 case above.  So they will get up next Sunday.  This
excuse lasts until the next Sunday, when still no one gets up, and now
each victim realizes that either the priest was mistaken (unthinkable!)
or there are really three victims, and I am ONE!  So, on the third
Sunday, all three get up.  This reasoning can be repeated inductively
to show that no one will do anything (except use up N - 1 excuses as to
why no one got up) until the Nth Sunday, when all N victims will arise
in unison.

The induction can also be run "top down" on the priest's statement.  What
must everyone believe about what everyone else believes?
N victims of adultery believe there are N - 1 victims, and that all of these
 N - 1 victims believe that there are N - 2 victims, and that all of these
  N - 2 victims believe that there are N - 3 victims, and that all of these
  ...
   2 victims believe that there is 1 victim, and that this
    1 victim believes there are no victims.
Suppose the priest says, "There are N adulterers in this town."  Then
all the adulterers will know immediately that their spouses have been
unfaithful, and will denounce them the next Sunday.  Now, suppose the
priest says, "There are at least N - 1 adulterers in this town."  On
the first Sunday, the offended spouses all wait for each other to stand
up.  When none do, they all know that they have all been horribly
mistaken, and they stand up on the following Sunday.  But what if the
priest says, "There are at least N - 2 adulterers in this town."  On
the first Sunday, the victims reason, those N - 1 victims are going to
be surprised when no one stands up, and they'll stand up next Sunday.
On the second Sunday, the victims reason, wait a minute, since they
didn't stand up, I must be one of the deluded victims.  And everyone
stands up on the third Sunday.  This resoning applies inductively,
adding one Sunday at each step, until the priest's original statement
is reached, which takes N Sundays for everyone to unravel.

By the way, the rest of the town, which thinks there are N adulterers,
is about to conclude that their perfectly innocent spouses have been
unfaithful too.  This includes the adulterous spouses, who are about to
conclude that the door swings both ways.  So the priest is playing a
dangerous game.  A movie plot in there somewhere?

This problem is an analogue of the "dirty children" problem discussed in
the seminal paper on common knowledge by Halpern and Moses (JACM 1990).

If the information of each victim is less than perfect, the problem is
related to the "frame" problem of AI, cf. J. M. McCarthy & P. J. Hayes,
"Some philosophical problems from the standpoint of artificial intelligence"
(1968) in _Readings in Artificial Intelligence_ (pp. 431-450),
Tioga Publishing Co., Palo Alto, CA (1981).

==> logic/smullyan/stamps.p <==
The moderator takes a set of 8 stamps, 4 red and 4 green, known to the
logicians, and loosely affixes two to the forehead of each logician so that
each logician can see all the other stamps except those 2 in the moderator's
pocket and the two on her own head.  He asks them in turn
if they know the colors of their own stamps:
  A: "No"
  B: "No"
  C: "No"
  A: "No
  B: "Yes"
  What are the colors of her stamps, and what is the situation?

==> logic/smullyan/stamps.s <==
B says: "Suppose I have red-red. A would have said on her
second turn: 'I see that B has red-red. If I also have red-red, then all
four reds would be used, and C would have realized that she had green-green.
But C didn't, so I don't have red-red.  Suppose I have green-green. In that
case, C would have realized that if she had red-red, I would have seen
four reds and I would have answered that I had green-green on my first
turn.  On the other hand, if she also has green-green [we assume that
A can see C; this line is only for completeness], then B would have seen
four greens and she would have answered that she had two reds.  So C would
have realized that, if I have green-green and B has red-red, and if
neither of us answered on our first turn, then she must have green-red.
  "'But she didn't. So I can't have green-green either, and if I can't have
green-green or red-red, then I must have green-red.'
  So B continues: "But she (A) didn't say that she had green-red, so
the supposition that I have red-red must be wrong.  And as my logic applies
to green-green as well, then I must have green-red."
  So B had green-red, and we don't know the distribution of the others
certainly.
  (Actually, it is possible to take the last step first, and deduce
that the person who answered YES must have a solution which would work
if the greens and reds were switched -- red-green.)

==> logic/supertasks.p <==
You have an empty urn, and an infinite number of labeled balls.  Each
has a number written on it corresponding to when it will go in.  At a
minute to the hour, you take the first ten balls and put them in the
urn, and remove the last ball.  At the next half interval, you put in
the next ten balls, and remove ball number 20.  At the next half
interval, you put in ten more balls and remove ball 30.  This continues
for the whole minute.... how many balls are in the urn at this point?
(infinite)

You have the same urn, and the same set of balls.  This time, you put
in 10 balls and remove ball number 1.  Then you put in another ten
balls and remove ball number 2.  Then you put in another ten balls and
remove ball number 3.  After the minute is over, how many balls are
left in the urn now? (zero)

Are the above answers correct, and why or why not?

==> logic/supertasks.s <==
Almost all people will intuitively feel that the first experiment
(where only balls labeled with multiples of 10 are removed) results in
an urn with an infinite number of balls.

The real excitement starts with the experiment where balls are removed
in increasing order, but 10 times slower than they are added.  Some
feel that the urn will not get empty, due to the slowness of removing.
Some others feel that the urn does get empty, since each ball is
removed at some time during the experiment.  The remaining people claim
that the experiment is not well defined, that it is not possible to do
something an infinite number of times, or something similar,
effectively dismissing the experiment.

Just to put a bit of doubt in some peoples mind, I will add a third experment:

  Let us suppose that at 1 minute to 12 p.m. balls nummbered 1 through 9
  are placed in the urn, and instead of withdrawing a ball we add a zero
  to the label of ball number 1 so that its label becomes 10. At 1/2 minute
  to 12 p.m., balls numbered 11 through 19 are placed in the urn, and we
  add a zero to the label of ball number 2 so that it becomes ball number 20.
  At 1/4 minute to 12 p.m., balls numbered 21 through 29 are placed in the
  urn and ball number 3 becomes ball number 30, and so on.
  At each instant, instead of withdrawing the ball with the smallest label
  we add a zero to its label so that its number is multiplied by 10.
  How many balls are in the urn at 12 p.m. and what are their labels?

If we look at this experiment, at any point in time the inside of the
urn looks exactly like the inside during the execution of the original
paradoxical experiment. However, since no balls leave the urn, it is
now impossible to conclude that the urn will be empty at 12 p.m.
Still, there is no natural number that is the label of any ball in the
urn.  Instead, each ball in the urn will have as its lable a natural
number followed by an infinite number of zero's.

A possible question is now: does this support that the outcome of the
original experiment where balls are removed in increasing order is that
there are an infinite number of balls in the urn? Possibly also with
'infinite natural numbers' as their labels, or are these experiments so
different that the answer is still a clear 'zero'?

I now come to the main points.
1. Our normal mathematical models do not cater for the COMPLETION of infinite
   tasks (called super tasks by Thomson in 1954).
2. Since we intuitively feel that for many of these experiments there
   are obvious outcomes, we would like to enhance our model to describe the
   outcomes of these experiments.
3. In the enhancement of the model continuity should play an important role.

We include statement 3, since a model in which the conclusion of all
these experiments is that, at 12 p.m. the urn contains "exactly 7
balls, all red" is not desirable, nor useful.

It can be easily shown that general continuity is unattainable. For
instance the sentence "it is before midnight" is true during the
experiment, but is suddenly false after the experiment.

The people claiming that in the second experiment the urn will contain
an infinite number of balls, base this on the fact that the number of
balls in the urn during the experiment, is 9n at (1/2)^(n-1) minute
before 12. They thus assume that this statement is continuous. This
remains to be seen, however.

We have not come to a clear set of criteria which decide whether a
given statement is continuous with respect to performing supertasks. We
did define a "kinematical principle of continuity", which is roughly
formalised as:

    If at some moment before 12 p.m. a ball comes to rest at a particular
    position, which it does not leave till 12 p.m., then it is still at
    that position at 12 p.m.

If we look at the three experiments mentioned, then we can see that in
each case we can come to a conclusion on the contents of the urn.

1. In the first experiment, with the 10-folds being removed, each ball
   which number is a multiple of 10 comes to rest outside the urn (just
   after being removed) and thus is outside the urn at 12 p.m. All other
   balls come to rest inside the urn (just after being placed there), and
   thus are inside the urn at 12 p.m.  Therefore the urn contains an infinite
   number of balls at 12 p.m.

2. In the second experiment, with the balls being removed in increasing order,
   each balls comes to rest outside the urn. Thus all balls involved are not
   in the urn. Thus the urn is empty.

3. In the third experiment, all balls come to rest inside the urn and thus the
   urn contains an infinite number of balls. The labels of these balls are
   naturall number followed by an infinite number of zero's (since each of the
   numbers is not changed, and zero's once added remain at the label, we can
   draw this conclusion).

The first and third experiment are rather straightforward, while the
second is paradoxical, but not inconsistent.  Please note that is just
one way of extending our model to include super tasks.  We have only
shown that for these experiments, in our model, we come to consistent
conclusions. It does not mean that there are no other models which lead
to different, but also, within that model, consistent solutions.

A final remark: while thinking about these matters, we have wondered
whether we could create a model in which the second experiment would
lead to an urn containing an infinite number of balls. A possibility is
assuming that if a position is continuously occupied by a ball,
although the occupant ball may be swapped every now and again for
another ball, that at 12 p.m. the position is occupied by a so-called
LIMIT BALL.  For the second experiment we could than place balls 1, 10,
100 ..  2, 20, 200, .. each at its own spot in the urn. Each spot in
the urn, once occupied is than continuously occupied with a ball,
leading to limit balls.

This idea of continuity is stronger than the kinematic principle
suggested above, and we have not followed these ideas up enough to
decide whether this extended principle can be made consistent. If any
of the readers have feelings whether this can or cannot be done, I
would be interested to hear their arguments.

I conclude by stating that the result of the super task depends on how
our standard models are enlarged to include the execution of
supertasks. We have given one extension which leads to consistent
results for the supertasks suggested by Ross. Other models may lead to
different, but also consistent, conclusions.

Reference:

Victor Allis and Teunis Koetsier (1991).
On Some Paradoxes of the Infinite.
Brit. J. Phil. Sci. 42 pp. 187-194.

-- [e-mail] (Victor Allis)

I am interested in the origin of the puzzle.  As far as I know in this
form the puzzle occurs for the first time in Littlewood's "Mathematical
Miscellanea", which is an amusing little booklet from the 1950s (it may
be even older). Littlewood does not discuss the puzzle.  DOES ANYONE
KNOW OF EARLIER REFERENCES TO THIS PUZZLE?  The puzzle also occurs in
S. Ross's "A first course in probability", New York and London, 1988,
without critical comment.

-- [e-mail] (Teun Koetsier)

==> logic/timezone.p <==
Two people are talking long distance on the phone; one is in an East-
Coast state of the US, the other is in a West-Coast state of the US.
The first asks the other "What time is it?", hears the answer, and
says, "That's funny.  It's the same time here!"

==> logic/timezone.s <==
One is in Eastern Oregon (in Mountain time), the other in
Western Florida (in Central time), and it's daylight-savings
changeover day at 1:30 AM.

==> logic/unexpected.p <==
Swedish civil defense authorities announced that a civil defense drill would
be held one day the following week, but the actual day would be a surprise.
However, we can prove by induction that the drill cannot be held.  Clearly,
they cannot wait until Friday, since everyone will know it will be held that
day.  But if it cannot be held on Friday, then by induction it cannot be held
on Thursday, Wednesday, or indeed on any day.

What is wrong with this proof?

==> logic/unexpected.s <==
This problem has generated a vast literature (see below).  Several
solutions of the paradox have been proposed, but as with most paradoxes
there is no consensus on which solution is the "right" one.

The earliest writers (O'Connor, Cohen, Alexander) see the announcement as
simply a statement whose utterance refutes itself.  If I tell you that I
will have a surprise birthday party for you and then tell you all the
details, including the exact time and place, then I destroy the surprise,
refuting my statement that the birthday will be a surprise.

Soon, however, it was noticed that the drill could occur (say on Wednesday),
and still be a surprise.  Thus the announcement is vindicated instead of
being refuted.  So a puzzle remains.

One school of thought (Scriven, Shaw, Medlin, Fitch, Windt) interprets
the announcement that the drill is unexpected as saying that the date
of the drill cannot be deduced in advanced.  This begs the question,
deduced from which premises?  Examination of the inductive argument
shows that one of the premises used is the announcement itself, and in
particular the fact that the drill is unexpected.  Thus the word
"unexpected" is defined circularly.  Shaw and Medlin claim that this
circularity is illegitimate and is the source of the paradox.  Fitch
uses Godelian techniques to produce a fully rigorous self-referential
announcement, and shows that the resulting proposition is
self-contradictory.  However, none of these authors explain how it can
be that this illegitimate or self-contradictory announcement
nevertheless appears to be vindicated when the drill occurs.  In other
words, what they have shown is that under one interpretation of "surprise"
the announcement is faulty, but their interpretation does not capture the
intuition that the drill really is a surprise when it occurs and thus
they are open to the charge that they have not captured the essence of
the paradox.

Another school of thought (Quine, Kaplan and Montague, Binkley,
Harrison, Wright and Sudbury, McClelland, Chihara, Sorenson) interprets
"surprise" in terms of "knowing" instead of "deducing."  Quine claims
that the victims of the drill cannot assert that on the eve of the last
day they will "know" that the drill will occur on the next day.  This
blocks the inductive argument from the start, but Quine is not very
explicit in showing what exactly is wrong with our strong intuition
that everybody will "know" on the eve of the last day that the drill
will occur on the following day.  Later writers formalize the paradox
using modal logic (a logic that attempts to represent propositions
about knowing and believing) and suggest that various axioms about
knowing are at fault, e.g., the axiom that if one knows something, then
one knows that one knows it (the "KK axiom").  Sorenson, however,
formulates three ingenious variations of the paradox that are
independent of these doubtful axioms, and suggests instead that the
problem is that the announcement involves a "blindspot":  a statement
that is true but which cannot be known by certain individuals even if
they are presented with the statement.  This idea was foreshadowed by
O'Beirne and Binkley.  Unfortunately, a full discussion of how this
blocks the paradox is beyond the scope of this summary.

Finally, there are two other approaches that deserve mention.  Cargile
interprets the paradox as a game between ideally rational agents and finds
fault with the notion that ideally rational agents will arrive at the same
conclusion independently of the situation they find themselves in.  Olin
interprets the paradox as an issue about justified belief: on the eve of
the last day one cannot be justified in believing BOTH that the drill will
occur on the next day AND that the drill will be a surprise even if both
statements turn out to be true; hence the argument cannot proceed and the
drill can be a surprise even on the last day.

For those who wish to read some of the literature, good papers to start with
are Bennett-Cargile and both papers of Sorenson.  All of these provide
overviews of previous work and point out some errors, and so it's helpful to
read them before reading the original papers.  For further reading on the
"deducibility" side, Shaw, Medlin and Fitch are good representatives.  Other
papers that are definitely worth reading are Quine, Binkley, and Olin.

D. O'Connor, "Pragmatic Paradoxes," Mind 57:358-9, 1948.
L. Cohen, "Mr. O'Connor's 'Pragmatic Paradoxes,'" Mind 59:85-7, 1950.
P. Alexander, "Pragmatic Paradoxes," Mind 59:536-8, 1950.
M. Scriven, "Paradoxical Announcements," Mind 60:403-7, 1951.
D. O'Connor, "Pragmatic Paradoxes and Fugitive Propositions," Mind 60:536-8,
 1951
P. Weiss, "The Prediction Paradox," Mind 61:265ff, 1952.
W. Quine, "On A So-Called Paradox," Mind 62:65-7, 1953.
R. Shaw, "The Paradox of the Unexpected Examination," Mind 67:382-4, 1958.
A. Lyon, "The Prediction Paradox," Mind 68:510-7, 1959.
D. Kaplan and R. Montague, "A Paradox Regained," Notre Dame J Formal Logic
 1:79-90, 1960.
G. Nerlich, "Unexpected Examinations and Unprovable Statements," Mind
 70:503-13, 1961.
M. Gardner, "A New Prediction Paradox," Brit J Phil Sci 13:51, 1962.
K. Popper, "A Comment on the New Prediction Paradox," Brit J Phil Sci 13:51,
 1962.
B. Medlin, "The Unexpected Examination," Am Phil Q 1:66-72, 1964.
F. Fitch, "A Goedelized Formulation of the Prediction Paradox," Am Phil Q
 1:161-4, 1964.
R. Sharpe, "The Unexpected Examination," Mind 74:255, 1965.
J. Chapman & R. Butler, "On Quine's So-Called 'Paradox,'" Mind 74:424-5, 1965.
J. Bennett and J. Cargile, Reviews, J Symb Logic 30:101-3, 1965.
J. Schoenberg, "A Note on the Logical Fallacy in the Paradox of the
 Unexpected Examination," Mind 75:125-7, 1966.
J. Wright, "The Surprise Exam: Prediction on the Last Day Uncertain," Mind
 76:115-7, 1967.
J. Cargile, "The Surprise Test Paradox," J Phil 64:550-63, 1967.
R. Binkley, "The Surprise Examination in Modal Logic," J Phil 65:127-36,
 1968.
C. Harrison, "The Unanticipated Examination in View of Kripke's Semantics
 for Modal Logic," in Philosophical Logic, J. Davis et al (ed.), Dordrecht,
 1969.
P. Windt, "The Liar in the Prediction Paradox," Am Phil Q 10:65-8, 1973.
A. Ayer, "On a Supposed Antinomy," Mind 82:125-6, 1973.
M. Edman, "The Prediction Paradox," Theoria 40:166-75, 1974.
J. McClelland & C. Chihara, "The Surprise Examination Paradox," J Phil Logic
 4:71-89, 1975.
C. Wright and A. Sudbury, "The Paradox of the Unexpected Examination,"
 Aust J Phil 55:41-58, 1977.
I. Kvart, "The Paradox of the Surprise Examination," Logique et Analyse
 337-344, 1978.
R. Sorenson, "Recalcitrant Versions of the Prediction Paradox," Aust J Phil
 69:355-62, 1982.
D. Olin, "The Prediction Paradox Resolved," Phil Stud 44:225-33, 1983.
R. Sorenson, "Conditional Blindspots and the Knowledge Squeeze: A Solution to
 the Prediction Paradox," Aust J Phil 62:126-35, 1984.
C. Chihara, "Olin, Quine and the Surprise Examination," Phil Stud 47:191-9,
 1985.
R. Kirkham, "The Two Paradoxes of the Unexpected Hanging," Phil Stud
 49:19-26, 1986.
D. Olin, "The Prediction Paradox: Resolving Recalcitrant Variations," Aust J
 Phil 64:181-9, 1986.
C. Janaway, "Knowing About Surprises: A Supposed Antinomy Revisited," Mind
 98:391-410, 1989.

    -- [e-mail].

==> logic/verger.p <==
A very bright and sunny Day
The Priest did to the Verger say:
"Last Monday met I strangers three
None of which were known to Thee.
I ask'd Them of Their Age combin'd
which amounted twice to Thine!
A Riddle now will I give Thee:
Tell Me what Their Ages be!"

So the Verger ask'd the Priest:
"Give to Me a Clue at least!"
"Keep Thy Mind and Ears awake,
And see what Thou of this can make.
Their Ages multiplied make plenty,
Fifty and Ten Dozens Twenty."

The Verger had a sleepless Night
To try to get Their Ages right.
"I almost found the Answer right.
Please shed on it a little Light."
"A little Clue I give to Thee,
I'm older than all Strangers three."
After but a little While
The Verger answered with a Smile:
"Inside my Head has rung a Bell.
Now I know the answer well!"


Now, the question is:

How old is the PRIEST??
               ======

==> logic/verger.s <==
The puzzler tried to take the test;
Intriguing rhymes he wished to best.
But "Fifty and ten dozens twenty"
made his headache pound aplenty.
When he finally found some leisure,
He took to task this witty treasure.

"The product of the age must be
Twenty-Four Hundred Fifty!"
Knowing that, he took its primes,
permuted them as many times
as needed, til he found amounts
equal to, by all accounts,
twice the Verger's age, so that
He would have that next day's spat.

The reason for the lad's confusion
was due to multiple solution!
Hence he needed one more clue
to give the answer back to you!
Since only one could fit the bill,
and then confirm the priest's age still,
the eldest age of each solution
by one could differ, with no coercion.  <=(Sorry)

Else, that last clue's revelation
would not have brought information!
With two, two, five, seven, and seven,
construct three ages, another set of seven.
Two sets of three yield sixty-four,
Examine them, yet one time more.
The eldest age of each would be
forty-nine, and then, fifty!

With lack of proper rhyme and meter,
I've tried to be the first completor
of this poem and a puzzle;
my poetry, you'd try to muzzle!
And lest you think my wit is thrifty,
The answer, of course, must be fifty!
If dispute, you wish to tender,
note my addresss, as the sender!

--
Kevin Nechodom <[e-mail]>

==> logic/weighing/balance.p <==
You are given 12 identical-looking coins, one of which is counterfeit
and weighs slightly more or less (you don't know which) than the
others.  You are given a balance scale which lets you put the same
number of coins on each side and observe which side (if either) is
heavier.  How can you identify the counterfeit and tell whether it
is heavy or light, in 3 weighings?

More generally, you are given N coins, one of which is heavy or light.

==> logic/weighing/balance.s <==
Martin Gardner gave a neat solution to this problem.

Assume that you are allowed W weighings.  Write down the 3^W possible
length W strings of the symbols '0', '1', and '2'.  Eliminate the three
such strings that consist of only one symbol repeated W times.

For each string, find the first symbol that is different from the symbol
preceeding it.  Consider that pair of symbols.  If that pair is not 01,
12, or 20, cross out that string.  In other words, we only allow strings
of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^W-3)/2 strings left.  This is how many coins you can
handle in W weighings.

Perform W weighings as follows:

    For weighing I, take all the coins that have a 0 in string
    position I, and weigh them against all the coins that have
    a 2 in string position I.

    If the side with the 0's in position I goes down, write down
    a 0.  If the other side goes down, write down a 2.  Otherwise,
    write down a 1.

After the W weighings, you have written down an W symbol string.  If
your string matches the string on one of the coins, then that is the
odd coin, and it is heavy.  If none of them match, than change every
2 to a 0 in your string, and every 0 to a 2.  You will then have a
string that matches one of the coins, and that coin is lighter than
the others.

Note that if you only have to identify the odd coin, but don't have to
determine if it is heavy or light, you can handle (3^W-3)/2+1 coins.
Label the extra coin with a string of all 1's, and use the above
method.

Note also that you can handle (3^W-3)/2+1 coins if you *do* have to
determine whether it is heavy or light, provided you have a single reference
coin available, which you know has the correct weight. You do this by
labelling the extra coin with a string of all 2s. This results in it being
placed on the same side of the scales each time, and in that side of the
scales having one more coin than the other each time. So you put the
reference coin on the other side of the scales to the "all 2s" coin on each
weighing.

Proving that this works is straightforward, once you notice that the
method of string construction makes sure that in each position, 1/3
of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a
string occurs, then the string obtained by replacing each 0 with a
2 and each 2 with a 0 does not occur.

If you already know the odd coin is heavy (or light), you can handle
3^W coins.  Given W weighings, there can only be 3^W possible
combinations of balances, left pan heavy, and right pan heavy.

The algorithm in this case:

Divide the coins into three equal groups... A, B, and C. Weigh A
against B. If a pan sinks, it contains the heavy coin, otherwise, the
heavy coin is in group C. If your group size is 1, you've found the coin,
otherwise recurse on the group containing the heavy coin.

==> logic/weighing/box.p <==
You have ten boxes; each contains nine balls.  The balls in one box
weigh 0.9 kg; the rest weigh 1.0 kg.  You have one weighing on an
accurate scale to find the box containing the light balls.  How do you
do it?

==> logic/weighing/box.s <==
Number the boxes 0-9.  Take 0 balls from box 0, 1 ball from box 1, 2
balls from box 2, etc.  Now weigh all those balls and follow this
table:

If odd box is    Weight is
0        45 kg
1        44.9 kg
2        44.8 kg
3        44.7 kg
4        44.6 kg
5        44.5 kg
6        44.4 kg
7        44.3 kg
8        44.2 kg
9        44.1 kg

==> logic/weighing/find.median.p <==
What is the least number of pairwise comparisons needed to find the median of
2n+1 distinct real numbers?


==> logic/weighing/find.median.s <==
Consider median of three numbers {a,b,c}.
Let G[a,b]=max(a,b) and L[a,b]=min(a,b)
If we assume that median of {a,b,c} can be computed by two
comparisons, then the solution must be one of the following:
G[c,G[a,b]], G[c,L[a,b]], L[c,G[a,b]], L[c,L[a,b]].
However, it is easily seen that none of these provides
a solution. Therefore, we need more than two comparisons to
get median of three numbers.

Now, consider median of 5 numbers {a,b,c,d,e}.
There are two possible ways to start the computation.
Let Ci[a,b] denote the ith comparison between {a} and {b}.
First, we could start with C1[a,b] and C2[c,d].
Second, we could start with C2[a,C1[b,c]].
We ignore other trivialities such as C1[a,a] or C2[a,C1[a,b]].

In the first case, the next operation is to find
median of S={e,C1[a,b],C2[c,d]} which requires at least three
comparisons in addition to the two comparisons already performed.
So the total cost of the first approach is at least 5 comparisons.
However, if the median is not equal to {e} then we can always
choose C1 and C2 such that the median is not in S.

In the second case, the next step is to find median of S={C2[a,C1[b,c]],d,e}.
Again, the total cost of this approach is at least five comparisons.
If median is not equal to {d} or {e}, we can again always
choose C1 and C2 such that the median is not in S.

Other starting sets, such as {e,d,c,b,a}, can always be ordered
as {a,b,c,d,e}. This shows that the argument covers all possible cases.

Navid,
[e-mail]

==> logic/weighing/gummy.bears.p <==
Real gummy drop bears have a mass of 10 grams, while imitation gummy
drop bears have a mass of 9 grams.  Spike has 7 cartons of gummy drop bears,
4 of which contain real gummy drop bears, the others imitation.
Using a scale only once and the minimum number of gummy drop bears, how
can Spike determine which cartons contain real gummy drop bears?

==> logic/weighing/gummy.bears.s <==
Spike uses 51 gummy drop bears:  from the 7 boxes he takes respectively
0, 1, 2, 4, 7, 13, and 24 bears.

The notion is that each box of imitation bears will subtract its
number of bears from the total "ideal" weight of 510 grams (1 gram of
missing weight per bear), so Spike weighs the bears, subtracts the
result from 510 to obtain a number N, and finds the unique combination
of 3 numbers from the above list (since there are 3 "imitation" boxes)
that sum to N.

The trick is for the sums of all triples selected from the set S of
numbers of bears to be unique.  To accomplish this, I put numbers into
S one at a time in ascending order, starting with the obvious choice,
0.  (Why is this obvious?  If I'd started with k > 0, then I could
have improved on the resulting solution by subtracting k from each
number) Each new number obviously had to be greater than any previous,
because otherwise sums are not unique, but also the sums it made when
paired with any previous number had to be distinct from all previous
pairs (otherwise when this pair is combined with a third number you
can't distinguish it from the other pair)--except for the last box,
where we can ignore this point.  And most obviously all the new
triples had to be distinct from any old triples; it was easy to find
what the new triples were by adding the newest number to each old sum
of pairs.

Now, in case you're curious, the possible weight deficits and their
unique decompositions are:

3       = 0 + 1 + 2
5       = 0 + 1 + 4
6       = 0 + 2 + 4
7       = 1 + 2 + 4
8       = 0 + 1 + 7
9       = 0 + 2 + 7
10      = 1 + 2 + 7
11      = 0 + 4 + 7
12      = 1 + 4 + 7
13      = 2 + 4 + 7
14      = 0 + 1 + 13
15      = 0 + 2 + 13
16      = 1 + 2 + 13
17      = 0 + 4 + 13
18      = 1 + 4 + 13
19      = 2 + 4 + 13
20      = 0 + 7 + 13
21      = 1 + 7 + 13
22      = 2 + 7 + 13
24      = 4 + 7 + 13
25      = 0 + 1 + 24
26      = 0 + 2 + 24
27      = 1 + 2 + 24
28      = 0 + 4 + 24
29      = 1 + 4 + 24
30      = 2 + 4 + 24
31      = 0 + 7 + 24
32      = 1 + 7 + 24
33      = 2 + 7 + 24
35      = 4 + 7 + 24
37      = 0 + 13 + 24
38      = 1 + 13 + 24
39      = 2 + 13 + 24
41      = 4 + 13 + 24
44      = 7 + 13 + 24

Note that there had to be (7 choose 3) distinct values; they end up
ranging from 3 to 44 inclusive with 7 numbers missing:  4, 23, 34, 36,
40, 42, and 43.

-- David Karr ([e-mail])

==> logic/weighing/optimal.weights.p <==
What is the smallest set of weights that allow you to weigh on a
balance scale every integer number of kilograms up to some number N?

==> logic/weighing/optimal.weights.s <==
a) EQUATION
-----------
Obviously (I hate this word! :-) any weight Y that can be weighed
by X1, X2, ... Xn can be written as:

    Y = A1*X1 + A2*X2 + .... + An*Xn

where Ai is equal to -1, or 0, or 1.

b) UPPER BOUND FOR Y(n)
-----------------------
Each Ai can have one of three values, so the total number of
combinations of values for A1,A2, ... An is 3^n. At least one of these
combinations gives Y=0 (A1=A2=...=An=0). Out of the remaining 3^n-1
combinations, some give a negative Y (for example A1=A2=...=An=-1).
and some a positive Y (and some might also give zero values, e.g. if
X1=X2, and A1=1, A2=-1).
Because of symmetry it's easy to see that the combinations that give Y>0
are at most half i.e. (3^n-1)/2. It is also possible that different
combinations might give the same value of Y, and it is also possible
that these values of Y are not successive.
However, to obtain an upper bound, lets assume the best case i.e.
all (3^n-1)/2 combinations give different, positive, and successive
values, so:
    Y(n) <= (3^n-1)/2

c) AN OPTIMAL ALGORITHM FOR CHOOSING Xn
---------------------------------------
I will present an algorithm for choosing the weights X1,X2,...Xn.
Then we will prove that it is optimal.

For n=1, we choose X1=1, and of course Y(1) = 1.

Let's assume that we have already chosen n weights X1, X2 ... Xn,
and that we can weigh all Y where 1<=Y<=Y(n).
We are allowed to get an extra new weight Xn+1.
If we choose:
    Xn+1 = 2*Y(n)+1
then we get
    Y(n+1) = Y(n) + Xn+1 = 3*Y(n)+1

Proof:
    for 1<= Y <= Y(n):
    use the weights X1...Xn (ignoring the new one)
    for Y(n)+1 <= Y < Xn+1 = 2*Y(n)+1
    Put Xn+1 on one side of the scale, and on the other side put
    the unknown weight, and a combination of X1...Xn so that
    this combination weighs "Xn+1 - Y" (which is a number
    in the range 0...Y(n), so *there exists* such a combination)
    for 2*Y(n)+1 <= Y <= 3*Y(n)+1:
    put the unknown weight on one side, and on the other side
    put Xn+1, and combination of X1...Xn with a weight equal to
    "Y - Xn+1" (which again is a number in the range 0...Y(n),
    so there exists such a combination)

So, to summarize, if we use such an algorithm, we have:
    X1 = 1;
    Y(1) =1;

    Xn+1 = 2*Y(n)+1
    Y(n+1) = Y(n) + Xn+1 = 3*Y(n) + 1

It's easy to prove (e.g. by induction) that:
    Y(n) = (3^n-1)/2
    X(n) = 3^n

So, Y(n) is equal to the upper bound we found before, so this algorithm is
optimal, and the weights you must choose are powers of 3.

Spyros Potamianos
[e-mail]


==> logic/weighing/weighings.p <==
Some of the supervisors of Scandalvania's n mints are producing bogus coins.
It would be easy to determine which mints are producing bogus coins but,
alas, the only scale in the known world is located in Nastyville,
which isn't on very friendly terms with Scandalville.  In fact, Nastyville's
king will only let you use the scale twice.  Your job?  You must determine
which of the n mints are producing the bogus coins using only two weighings
and the minimum number of coins (your king is rather parsimonious, to put it
nicely).  This is a true scale, i.e. it will tell you the weight of whatever
you put on it.  Good coins are known to have a weight of 1 ounce and it is
also known that all the bogus mints (if any) produce coins that are
light or heavy by the same amount.

Some examples: if n=1 then we only need 1 coin, if n=2 then clearly 2
coins suffice, one from each mint.

What are the solutions for n=3,4,5?  What can be said for general n?

==> logic/weighing/weighings.s <==
Oh gracious and wise king, I have solved this problem by first
simplifying and then expanding.  That is, consider the problem of
being allowed only a single weighing.  Stop reading right now if you
want to think about it further.

There are three possible outcomes for each mint (light, OK, heavy)
which may be represented as (-1, 0, +1).  Now, let each mint represent
one place in base 3.  Thus, the first mint is the ones place, the
second the threes place, the third is the nines place and so on.  The
number of coins from each mint must equal the place.  That is, we'll
have 1 coin from mint 1, 3 from mint 2, 9 from mint 3, and, in
general, 3^(n-1) from mint n.

By weighing all coins at once, we will get a value between 1 + 3 + 9 +
...  and -1 + -3 + -9 + ...  In fact, we notice that that value will
be unique for any mint outcomes.  Thus, for the one weighing problem,
we need

sum for i=1 to n (3^(i-1))

which evaluates to (3^n - 1)/2

I'm fairly satisfied that this is a minimum for a single weighing.
What does a second weighing give us?  Well, we can divide the coins
into two groups and use the same method.  That is, if we have 5 mints,
one weighing will be:

1 coin from mint 1 + 3 coins from mint 2 + 9 coins from mint 3

while the other weighing will be:

1 coin from mint 4 + 3 coins from mint 5

It's pretty plain that this gives us a total coinage of:

   3^(n/2) - 1 for even n and, after some arithmetic agitation:
   2 * 3^((n-1)/2) - 1 for odd n

I think the flaw in this solution is that we don't know ahead of time
the amount by which the coins are off weight.  So if you weigh 1 coin
from mint 1 together with 3 coins from mint 2 and the result is heavy
by 3x units, you still don't know whether the bogus coins are from
mint 3 (heavy by x units) or from mint 1 (heavy by 3x units).  Note
that we're not given the error amount, only the fact that is is equal
for all bogus coins.

Here is my partial solution:

After considering the above, it would seem that on each of the two
weighings we must include coins from all of the mints (except for the
special cases of small n).  So let ai (a sub i) be the number of coins
from mint i on weighing 1 and bi be the number of coins from mint i on
weighing 2.  Let the error in the bogus coins have a value x, and let
ci be a the counterfeit function: ci is 0 if mint i is good, 1
otherwise.

Then
    Sum   ai ci x = delta1        error on weighing 1
    Sum   bi ci x = delta2        error on weighing 2

Now the ratio of delta1 to delta2 will be rational regardless of the
value of x, since x will factor out; let's call this ratio p over q (p
and q relatively prime).  We would like to choose { ai } and { bi }
such that for any set of mints J, which will be a subset of { 1 , 2 ,
... , n }, that

    Sum aj    ( = Sum  ai ci ) is relatively prime to Sum bj.

If this is true then we can determine the error x; it will simply be
delta1/p, which is equal to  delta2/q.

If the { ai } have been carefully chosen, we should be able to figure
out the bogus mints from one of the weighings, provided that
all subsets ( { { aj } over all J } ) have unique sums.
This was the strategy proposed above, where is was suggested
that ai = 3 ** (i-1) ; note that you can use base 2 instead
of base 3 since all the errors have the same sign.

Well, for the time being I'm stumped.

This agrees with the analysis I've been fighting with.  I actually
came up with a pair of functions that "almost" works.  So that the
rest of you can save some time (in case you think the way I did):
    Weighing 1: 1 coin from each mint
    Weighing 2: 2^(k-1) coins from mint k, for 1...k...n
    (total 2^n - 1 coins)

Consider the n mints to be one-bit-each -- bit set -> mint makes bogus
coins.  Then we can just state that we're trying to discover "K",
where K is a number whose bit pattern _just_ describes the bogosity of
each mint.  OK - now, assuming we know 'x', and we only consider the
*difference* of the weighing from what it should be, for weighing 1,
the devaiation is just the Hamming weight of K -- that is the number
of 1-bits in it -- that is, the number of bogosifying mints.  For
weighing 2, the deviation is just K!  When the nth bit of K is set,
then that mint contributes just 2^n to the deviation, and so the total
deviation will just be K.

So that set me in search of a lemma: given H(x) is the hamming weight
of x, is f(x) = x / H(x) a 1-1 map integers into rationals?  That is,
if x/H(x) = y/H(y) can we conclude that x = y?

The answer (weep) is NO.  The lowest pair I could find are 402/603
(both give the ratio 100.5).  Boy it sure looked like a good
conjecture for a while!  Sigh.


There are two parts to the problem. First let us try to come up with a
solution to finding the answer in 2 weighings - then worry about using the
min. number of coins.
Solutions are for GENERAL n.

Let N = set of all mints, 1 to n. Card(N) = n.
Let P = set of all bogus mints. Let Card(P) = p.

Weighing I: Weigh n coins, 1 from each mint.

Since each "good" coins weighs one ounce, let delta1 be the error in weighing.
Since all bogus coins are identical, let delta1 be abs(error).
If x is the weight by which one bogus coin differs from a good coin,
 delta1 = p * x.

Weighing II: The coins to be weighed are composed thusly.

Let a1 be the number of coins from mint 1, a2 # from mint2 .. and an from
mint n. All ai's are distinct integers.

Let A = Set of all ai's.

Let delta2 = (abs.) error in weighing 2 = x * k
    where k is the number of coins that are bogus in weighing two.
Or more formally
        k = sigma(ai)
         (over all i in P)

Assuming p is not zero (from Weighing I - in that case go back and get beheaded
for giving the king BAAAAAD advice),
    Let ratio = delta1/delta2 = p/k.
    Let IR = delta2/delta1 = k/p = inverse-ratio (for later proof).

Let S(i) be the bag of all numbers generated by summing i distinct elements
from A. Clearly there will be nCi (that n comb. i) elements in S(i).

[A bag is a set that can have the same element occur more than once.]

So S(1) = A
and S(n) will have one element that is the sum of all the elements of A.

Let R(i) = {x : For-all y in S(i), x = i/y} expressed as p/q (no common
                                factors).
(R is a bag too).

Let R-A = Bag-Union(R(i) for 1>= i >=n). (can include same element twice)

Choose A, such that all elements of R-A are DISTINCT, i.e. Bag(R-A) = Set(R-A).

Let the sequence a1, a2, .. an, be an L-sequence if the above property is
true. Or more simply, A is in L.

**********************************************************************
CONJECTURE: The bogus mint problem is solved in two weighings if A is in L.

Sketchy proof: R(1) = all possible ratios (= delta1/delta2) when p=1.
R(i) = all possible ratio's when p=i.

Since all possible combinations of bogus mints are reflected in R, just match
the actual ratio with the generated table for n.

************************************************************************
A brief example. Say n=3. Skip to next line if you want.
Let A=(2,3,7).

p=1 possible ratios = 1/2 1/3 1/7
p=2 possible ratios = 2/5 2/9 1/5(2/10)
p=3 possible ratios = 1/4(3/12) (lots of blood in Scandalvania).

As all outcomes are distinct, and the actual ratio MUST be one of these,
match it to the answer, and start sharpening the axe.

Note that the minimum for n=3 is A=(0,1,3)
possible ratios are
p=1 infinity (delta2=0),1,1/3
p=2 2/1,2/3,1/2
p=3 3/4

************************************************************************

All those with the determination to get this far are saying OK, OK how do we
get A.

I propose a solution that will generate A, to give you the answer in two
weighings, but will not give you the optimal number of coins.

Let a1=0

For i>=2 >=n

ai = i*(a1 + a2 + ... + ai-1) + 1

*****************************************
*        i-1            *
*    ai = i* [Sigma(aj)] + 1     *   ****Generator function G*****
*        j=1            *
*****************************************

If A is L, all RATIO's are unique. Also all inverse-ratio's (1/ratio) are
unique. I will prove that all inverse-ratio's (or IR's) are unique.

Let A(k), be the series generated by the first k elements from eqn. G.(above)

************************************************************************

PROOF BY INDUCTION.

A(1) = {0} is in L.
A(2) = {0,1} is in L.

ASSUME A(k) = {0,1, ..., ak} is in L.

T.P.T. A(k+1) = {0,1, ..., ak, D) is in L where D is generated from G.

We know that all IR's(inverse ratio's)  from A(k) are distinct.

Let K = set of all IR's of A(k).

Since A(k+1) contains A(k), all IR's of A(k) will also be IR's of A(K+1).

So for all P, such that (k+1) is not in P, we get a distinct IR.

So consider cases when (k+1) is in P.

p=1 (i.e. (k+1) = only bogus mint), IR = D

______________________________________________________________________
CONJECTURE: Highest IR for A(k) = max(K) = ak

Proof:     Since max[A(k)] = ak,
        for p'= 1, max IR = ak/1 = ak
        for p'= 2, max IR (max sum of 2 ai's)/2
               = (ak + ak-1)/2 < ak (as ak>ak-1).
        for p'= i max IR sum of largest i elements of A(k)
                      --------------------------------
                        i
                < i * ak/i = ak.
    So max. IR for A(k) is ak.
______________________________________________________________________

D > ak
So for p=1 IR is distinct.

Let Xim be the IR formed by choosing i elements from A(k+1).
    Note: We are choosing D and (i-1) elements from A(k).
          m is just an index to denote each distinct combination of
          (i-1) elemnts of A(i).

______________________________________________________________________
CONJECTURE : For p=j, all new IR's Xjm are limited to the range
         D/(j-1) > Xjm > D/j.

Proof:
    Xjm = (D + {j-1 elements of A(k)})/j

    Clearly Xjm > D/j.

    To show: max[Xjm] < D/(j-1)

    Note: a1 + a2 .. + ak < D/(k+1)

       max[Xjm] = (D + ak + ak-1 +  ... + a(k-j+1))/j
        < (D + D/(k+1))/j
        = D (k+2)/(k+1)j
        = [D/(j-1)] * alpha.

    alpha = (j-1)/(j)  *  (k+2)/(k+1)

        Since j <= k, (j-1)/j <= (k-1)/k < (k+1)/(k+2)

    IMPLIES alpha < 1.

Conjecture proved.

______________________________________________________________________
CONJECTURE : For a given p, all newly generated IR's are distinct.

Proof by contradiction:

Assume this is not so.

Implies
    (D + (p-1) elements of A(k))/p
    = (D + some other (p-1) elements of A(k))/p

Implies SUM[(p-1) elements of A(k)] = SUM[ some other (p-1) elements of A(k)]

Implies SUM[(p-1) elements of A(k)]/(p-1)
        = SUM[some other (p-1) elements]/(p-1)

Implies A(k) is NOT in L.

Contra.

Hence conjecture.
______________________________________________________________________

CONJECTURE: A(k+1) is in L.

Since all newly generated IR's are distinct from each other, and all newly generated IR's are greater than previous IR's, A(k+1) is in L.

==> logic/zoo.p <==
 I took some nephews and nieces to the Zoo, and we halted at a cage marked

            Tovus Slithius, male and female.
          Beregovus Mimsius, male and female.
             Rathus Momus, male and female.
        Jabberwockius Vulgaris, male and female.

 The eight animals were asleep in a row, and the children began to guess
 which was which.  "That one at the end is Mr Tove."  "No, no!  It's Mrs
 Jabberwock," and so on.  I suggested that they should each write down
 the names in order from left to right, and offered a prize to the one
 who got most names right.

 As the four species were easily distinguished, no mistake would arise in
 pairing the animals; naturally a child who identified one animal as Mr
 Tove identified the other animal of the same species as Mrs Tove.

 The keeper, who consented to judge the lists, scrutinised them carefully.
 "Here's a queer thing.  I take two of the lists, say, John's and Mary's.
 The animal which John supposes to be the animal which Mary supposes to be
 Mr Tove is the animal which Mary supposes to be the animal which John
 supposes to be Mrs Tove.  It is just the same for every pair of lists,
 and for all four species.

 "Curiouser and curiouser!  Each boy supposes Mr Tove to be the animal
 which he supposes to be Mr Tove; but each girl supposes Mr Tove to be
 the animal which she supposes to be Mrs Tove.  And similarly for the oth-
 er animals.  I mean, for instance, that the animal Mary calls Mr Tove
 is really Mrs Rathe, but the animal she calls Mrs Rathe is really Mrs
 Tove."

 "It seems a little involved," I said, "but I suppose it is a remarkable
 coincidence."

 "Very remarkable," replied Mr Dodgson (whom I had supposed to be the
 keeper) "and it could not have happened if you had brought any more
 children."

 How many nephews and nieces were there?  Was the winner a boy or a girl?
 And how many names did the winner get right?    [by Sir Arthur Eddington]

==> logic/zoo.s <==
Given that there is at least one boy and one girl (John and Mary are
mentioned) then the answer is that there were 3 nephews and 2 nieces,
the winner was a boy who got 4 right.

Number the animals 1 through 8, such that the females are even and the
males are odd, with members of the same species consecutive; i.e.  1 is
Mr. Tove, 2 Mrs. Tove, etc.

Then each childs guesses can be represented by a permutation.  I use
the standard notation of a permutation as a set of orbits.  For
example: (1 3 5)(6 8) means 1 -> 3, 3 -> 5, 5 -> 1, 6 -> 8, 8 -> 6 and
2,4,7 are unchanged.

[1]  Let P be any childs guesses.  Then P(mate(i)) = mate(P(i)).

[2]  If Q is another childs guesses, then [P,Q] = T, where [P,Q] is the
commutator of P and Q (P composed with Q composed with P inverse
composed with Q inverse) and T is the special permutation (1 2) (3 4)
(5 6) (7 8) that just swaps each animal with its spouse.

[3]  If P represents a boy, then P*P = I (I use * for composition, and
I for the identity permutation: (1)(2)(3)(4)(5)(6)(7)(8)

[4]  If P represents a girl, then P*P = T.

[1] and [4] together mean that all girl's guesses must be of the form:
    (A B C D) (E F G H) where A and C are mates, as are B & D,
    E & F G & H.

So without loss of generality let Mary = (1 3 2 4) (5 7 6 8)
Without to much effort we see that the only possibilities for other
girls "compatible" with Mary (I use compatible to mean the relation
expressed in [2]) are:
    g1:  (1 5 2 6) (3 8 4 7)
    g2:  (1 6 2 5) (3 7 4 8)
    g3:  (1 7 2 8) (3 5 4 6)
    g4:  (1 8 2 7) (3 6 4 5)

Note that g1 is incompatible with g2 and g3 is incompatible with g4.
Thus no 4 of Mary and g1-4 are mutually compatible.  Thus there are at
most three girls: Mary, g1 and g3 (without loss of generality)

By [1] and [3], each boy must be represented as a product of
transpostions and/or singletons: e.g. (1 3) (2 4) (5) (6) (7) (8) or
(1) (2) (3 4) (5 8) (6 7).

Let J represent John's guesses and consider J(1).
If J(1) = 1, then J(2) = 2 (by [1]) using [2] and Mary J(3) = 4, J(4) =
3,  and g1 & J => J(5) = 6, J(6) = 5, & g3 & J => J(8) = 7 J(7) = 8
i.e. J = (1)(2)(3 4)(5 6)(7 8).  But the [J,Mary] <> T.  In fact, we
can see that J must have no fixed points, J(i) <> i for all i, since
there is nothing special about i = 1.

If J(1) = 2, then we get from Mary that J(3) = 3.  contradiction.

If J(1) = 3, then J(2) = 4, J(3) = 1, J(4) = 2 (from Mary) =>
   J(5) = 7, J(6) = 8, J(7) = 5, J(8) = 6 => J = (1 3)(2 4)(5 7)(6 8)
   (from g1)
But then J is incompatible with g3.

A similar analysis shows that J(1) cannot be 4,5,6,7 or 8; i.e. no J
can be compatible with all three girls.  So without loss of generality,
throw away g3.

We have Mary = (1 3 2 4) (5 7 6 8)
        g1   = (1 5 2 6) (3 8 4 7)

The following are the only possible boy guesses which are compatible
with
both of these:

  B1: (1)(2)(3 4)(5 6)(7)(8)
  B2: (1 2)(3)(4)(5)(6)(7 8)
  B3: (1 3)(2 4)(5 7)(6 8)
  B4: (1 4)(2 3)(5 8)(6 7)
  B5: (1 5)(2 6)(3 8)(4 7)
  B6: (1 6)(2 5)(3 7)(4 8)

Note that B1 & B2 are incombatible, as are B3 & B4, B5 & B6, so at most
three of them are mutually compatible.  In fact, Mary, g1, B1, B3 and
B5 are all mutually compatible (as are all the other possibilities you
can get by choosing either B1 or B2, B3 or B4, B5 or B6.  So if there
are 2 girls there can be 3 boys, but no more, and we have already
eliminated the case of 3 girls and 1 boy.

The only other possibility to consider is whether there can be 4 or
more boys and 1 girl.  Suppose there are Mary and 4 boys.  Each boy
must map 1 to a different digit or they would not be mutually
compatible.  For example if b1 and b2 both map 1 to 3, then they both
map 3 to 1 (since a boy's map consists of transpositions), so both
b1*b2 and b2*b1 map 1 to 1.  Furthermore, b1 and b2 cannot map 1 onto
spouses.  For example, if b1(1) = a and b is the spouse of a, then
b1(2) = b.  If b2(1) = b, then b2(2) = a.  Then b1*b2(1) = b1(b) = 2
and b2*b1(1) = b2(a) = 2 (again using the fact that boys are all
transpostions).  Thus the four boys must be:

B1: (1)(2)...    or (1 2)....
B2: (1 3)...     or (1 4) ...
B3: (1 5) ...    or (1 6) ...
B4: (1 7) ...    or (1 8) ...

Consider B4.  The only permutation of the form (1 7)... which is
compatible
with Mary ( (1 3 2 4) (5 7 6 8) ) is:

   (1 7)(2 8)(3 5)(4 6)

The only (1 8)... possibility is:

   (1 8)(2 7)(3 6)(4 5)

Suppose B4 = (1 7)(2 8)(3 5)(4 6)

If B3 starts (1 5), it must be (1 5)(2 6)(3 8)(4 7) to be compatible
with B4.  This is compatible with Mary also.

Assuming this and B2 starts with (1 3) we get B2 = (1 3)(2 4)(5 8)(6 7)
in order to be compatible with B4.  But then B2*B3 and B3*B2 moth map 1
to 8.  I.e. no B2 is mutually compatible with B3 & B4.

Similarly if B2 starts with (1 4) it must be (1 4)(2 3)(5 7)(6 8) to
work with B4, but this doesn't work with B3.

Likewise B3 starting with (1 6) leads to no possible B2 and the
identical reasoning eliminates B4 = (1 8)...

So no B4 is possible!

I.e at most 3 boys are mutually compatiblw with Mary, so 2 girls & 3
boys is optimal.

Thus:

Mary = (1 3 2 4) (5 7 6 8)
Sue  = (1 5 2 6) (3 8 4 7)
John = (1)(2)(3 4)(5 6)(7)(8)
Bob  = (1 3)(2 4)(5 7)(6 8)
Jim  = (1 5)(2 6)(3 8)(4 7)

is one optimal solution, with the winner being John (4 right: 1 2 7 & 8)