Brain-Teaser 906: Truthful salesman
From The Sunday Times, 2nd December 1979 [link]
Seated happily one Sunday morning in my local pub, solving the Brain-teaser, I was accosted by the slightly inebriated resident bore. He said: “I have a puzzle for you which concerns seven people who were either engineers or salesmen and, of course, salesmen always tell the truth and engineers always lie. I will make four statements from which you must deduce how many salesmen there are:
1. B and E are salesmen;
2. A and C have different occupations;
3. D says that G is an engineer;
4. A says that B declares that C insists that D asserts that E affirms that F states that G is a salesman”.I said: “That’s a very old one”, and told him the answer. Grinning, he then replied, “Yes, that would be the correct answer if all the four statements were true, but it is not the correct answer because I intentionally made one of the four statements false. Further, if were to tell you how many salesmen there were under these new circumstances, you would be able to tell me which statement was false”.
“Ah”, I said, “that’s a much more interesting problem”. I thought for a moment and indeed I was able to tell him not only which statement was false but also how many salesmen there really were.
Which statement was false and how many salesmen were there really?
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.
[teaser906]
John Crabtree and 
Frits, 
Hugh+Casement, and 
NigelR, 
GeoffR, 
S2T2 
Jim Randell 8:50 am on 28 August 2022 Permalink |
This Python program runs in 54ms. (Internal runtime is 233µs).
Run: [ @replit ]
from collections import defaultdict from enigma import (subsets, peek, printf) # salesman or engineer? jobs = (Sales, Eng) = (True, False) # does X make statements s? check = lambda X, s: (X == s) # map number of salesmen to index of false statement m = defaultdict(set) # choose jobs for A - G for (A, B, C, D, E, F, G) in subsets(jobs, size=7, select="M"): # evaluate the statements: ss = [ # 1. "B and E are salesmen" (B == E == Sales), # 2. "A and C have different occupations" (A != C), # 3. "D says that G is an engineer" check(D, G == Eng), # 4. "A says that B declares that C insists that D asserts that E affirms that F states that G is a salesman check(A, check(B, check(C, check(D, check(E, check(F, G == Sales)))))), ] # exactly one statement is false if ss.count(False) == 1: m[[A, B, C, D, E, F, G].count(Sales)].add(ss.index(False)) # look for unique values for (k, vs) in m.items(): if len(vs) == 1: v = peek(vs) + 1 printf("{k} salesmen -> statement {v} is false")Solution: The false statement is number 4. And there are 4 salesmen.
And there are 4 possible arrangements of salesmen:
If all statements are true then there are 5 salesmen. The possible arrangements are:
LikeLike
John Crabtree 3:19 am on 30 August 2022 Permalink |
I was introduced to the original puzzle in Paul Nahin’s book, “The Logician and Engineer”, Princeton University Press, 2013, pp 58-59 and 65-66. He gave these references:
i) D.M. McCallum and J.B. Smith, “Mechanized Reasoning: Logical Computers and their Design”, Electronic Engineering (a UK magazine), April 1951, pp 126-133 (page nos. not given by Nahin)
ii) C. E. Shannon, “Computers and Automata”, Proc. of the Institute of Radio Engineers (U.S.A.), Oct 1953, pp 1234-1241. Nahin notes that there was a typo in Shannon’s representation of McCallum and Smith’s problem. I believe that it does not affect the nature of, or the solution to, the problem.
A asserts B may be written as A XNOR B = 1, ie both true or both false.
St. 4, if true, may be written as A XNOR (B XNOR (C XNOR (D XNOR (E XNOR (F XNOR G))))) = 1
And so A XNOR B XNOR C XNOR D XNOR E XNOR F XNOR G = 1
X XNOR Y XNOR Z = 1 is equivalent to X XOR Y XOR Z = 1
And so St. 4, if true, may be written as
A XOR B XOR C XOR D XOR E XOR F XOR G = 1
This is familiar to electrical engineers as the expression for a half-adder circuit ie binary addition ignoring the carry. And so if St. 4 is true, there are an odd number of salesman, and if it is false there are an even number of salesmen. (This method is not given by Nahin).
If all of the statements are true, there are 5 salesmen including F. If St. 1 is false, there are 3 salesmen. If Sts. 2 or 3 are false, there can be 3 or 5 salesmen.
And so St. 4 is false and there are 4 salesmen (with F being an engineer).
LikeLike