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