From csus.edu!news.starnet.net!wupost!uwm.edu!hookup!news.mathworks.com!uunet!in1.uu.net!newstf01.news.aol.com!newsbf02.news.aol.com!not-for-mail Sun Feb 26 08:03:29 1995
Path: csus.edu!news.starnet.net!wupost!uwm.edu!hookup!news.mathworks.com!uunet!in1.uu.net!newstf01.news.aol.com!newsbf02.news.aol.com!not-for-mail
From: kptben@aol.com (KPT Ben)
Newsgroups: sci.math
Subject: Excellent Discrete Puzzle!
Date: 26 Feb 1995 02:28:37 -0500
Organization: America Online, Inc. (1-800-827-6364)
Lines: 35
Sender: root@newsbf02.news.aol.com
Message-ID: <3ipaj5$im4@newsbf02.news.aol.com>
Reply-To: kptben@aol.com (KPT Ben)
NNTP-Posting-Host: newsbf02.mail.aol.com
Occasionally I stumble onto a math problem that's simple to state, sounds
simple to solve, and yet turns out to be mind-bogglingly difficult. The
king of these puzzles is Fermat's Last Theorem, though it obviously cannot
be solved by brute force.
Here's one that sounds quite simple, but the solution is mighty elusive...
If you have a free weekend, give it a try. Credit to Prof. Art Benjamin of
Harvey Mudd College for telling me about it:
"Two mathematicians, Sam and Polly, are sitting around one day when a
Martian comes down from outer space and says:
'I'm thinking of two whole numbers X and Y, 3 <= X <= Y <= 97, and I'll
give their sum to Sam and their product to Polly.'
He does so, then takes off in his spaceship. The following conversation
ensues:
Sam (to Polly) : 'You can't possibly know what X and Y are.'
Polly: 'That was true, but now I do.'
Sam: 'Now I do too.'
Find X and Y."
There is a unique solution, took me several hours to find... I'm curious
if anyone reading this can solve it too, and possibly compare techniques
used to close in on the answer.
Have fun, and good luck!!
Ben Weiss
HSC Software
P.S. Find two positive integers A and B such that A*B = 1,000,000, and
the decimal representations of A and B contain no zeroes... ;)
From formal-methods-request@cs.uidaho.edu Wed Mar 1 11:10 PST 1995
Return-Path:
Received: from blaze.csci.csusb.edu by silicon.csci.csusb.edu (5.0/SMI-SVR4)
id AA06144; Wed, 1 Mar 1995 11:10:27 +0800
Received: from dworshak.cs.uidaho.edu by blaze.csci.csusb.edu (AIX 3.2/UCB 5.64/4.03)
id AA22626; Wed, 1 Mar 1995 11:01:59 -0800
Received: (from daemon@localhost) by dworshak.cs.uidaho.edu (8.6.10/1.0) id KAA29210 for formal-methods-explode; Wed, 1 Mar 1995 10:57:19 -0800
Received: from kingi.cs.uidaho.edu (kingi.cs.uidaho.edu [129.101.100.15]) by dworshak.cs.uidaho.edu (8.6.10/1.0) with ESMTP id KAA29206 for ; Wed, 1 Mar 1995 10:57:12 -0800
Received: (mbarnett@localhost) by kingi.cs.uidaho.edu (8.6.10/1.0) id KAA11302; Wed, 1 Mar 1995 10:57:23 -0800
Errors-To: formal-methods-request@cs.uidaho.edu
Sender: formal-methods-request@cs.uidaho.edu
Errors-To: formal-methods-request@cs.uidaho.edu
Precedence: bulk
From: Michael Barnett
Date: Wed, 1 Mar 1995 10:57:23 -0800
Message-Id: <199503011857.KAA11302@kingi.cs.uidaho.edu>
To: formal-methods@cs.uidaho.edu
Subject: Knights and Knaves
Content-Type: text
Content-Length: 3378
Status: R
Once again, James Foster and I are teaching a course on program
derivation using Ed Cohen's (excellent) book _Programming in the
1990s_. The first part of the course teaches the equational logic as
presented in Gries and Schneider _A Logical Approach to Discrete Math_
(yet another excellent book!). This time we have been trying to
encourage the students to apply the logic by giving them a lot of
Knights and Knaves puzzles. We are stressing how one models a
situation in the "real world" in the logic, then performs
manipulations without regard to the "meaning" of the symbols, and then
reinterprets the result back into the "real world".
Knights and Knaves puzzles were popularized by the philosopher Raymond
Smullyan (as far as I know). They concern an island that is populated
exclusively by two types of people: knights that always tell the truth
and knaves that always lie. The puzzles concern situations where
people make statements and you must figure out who is a knight and who
is a knave. I've found one that I just gave to the class:
There are three people A, B, and C. A says "B and C are of the
same type." Someone then asks C, "Are A and B of the same type?"
What does C answer?
_What is the Name of this Book_, Raymond Smullyan
chapter 3, problem 35
I really like this one because using the logic leads to a particulary
simple solution compared to his answer. The way to model these
problems is to model the fact that X is a knight by the proposition x.
That way if X is a knave, -x holds (the negation of x). If X makes a
statement, S, it can be modeled by the formula x = s (x equivales s)
where s is the propositional model of the statement S. This works
since the truth value of anything X says is equivalent to the truth
value of X's knighthood. So the above problem becomes:
1. A = (B = C) [Notice the parentheses are unnecessary since =
as equivales is associative.]
2. C = (A ? B)
and the puzzle is to decide whether ? is = or != (discrepency). Here
is a solution, starting with the formula containing the unknown:
C = (A ? B)
= < 1., using associativity >
A = B = (A ? B)
= < clearly ? is =, else the formula is equivalent to false >
A = B = (A = B)
=
true
The conclusion of "true" means that choosing ? to be = leads to no
contradiction. Here is Smullyan's answer:
I'm afraid we can solve this problem only by analysis into cases.
Case One: A is a knight. Then B,C really are of the same type.
If C is a knight, then B is also a knight, hence is of the same
type as A, so C being truthful must answer "Yes". If C is a knave,
then B is also a knave (since he is the same type as C), hence
is of a different type than A. So C, being a knave, must lie and
say "Yes".
Case Two: A is a knave. Then B,C are of different types. If C
is a knight, then B is a knave, hence he is of the same type
as A. So C, being a knight, must answer "Yes." If C is a knave,
then B, being of a different type than C, is a knight, hence of
a different type than A. Then C, being a knave, must lie about
A and C being of different types, so he will answer "Yes".
This in both cases, C answers "Yes".
I highly recommend Smullyan's books. They are a lot of fun.
Mike