Problem Description
Mr. Barclay and five of his
friends, each of whom works in a different field, just returned
from business trips. Each man used two different methods of
transportation during his trip. All six traveled by either plane
or train, but not both, and all six also traveled by bus, boat, or
trolley. No two used the same two methods of transportation.
From the information provided, determine the first and last names
of each man, his field (one deals in precious gems), and the two
methods of travel he used on his business trip.
-
Mr. Rogers, who is not
Vince or Russ, and Mr. Whitman together, used four different
methods of transportation.
-
Mr. Potter traveled by
bus. The oil company executive visited an area that can only
be reached by a boat from the mainland.
-
Neither Myron, nor Russ,
nor Mr. Henley, nor the mining engineer traveled by trolley.
-
Neither Leroy, who
traveled by bus, nor Jeremy is the manufacturer.
-
The agricultural
representative did not fly to his destination.
-
Vince, who is not Mr.
Henley, traveled by boat.
-
Dennis and Mr. Rogers
traveled by train. Mr. Strong traveled by plane.
-
Both Mr. Whitman and the
research scientist traveled by trolley.
Background & Techniques
I called this problem "stupid" for several days before
resorting to a program to prove it. Now that I've solved it,
I'll modify the adjective from "stupid" to "less than clear".
If you work on it, I'll tell you that Clue #1 says that 2 people
used the 4 modes of transportation, not 4 people as I originally
interpreted it.
I posted a
logic problem
solver several years ago which an excellent logic engine but
cumbersome input procedures. I may rewrite it one day to fix
that. It also is not flexible enough to handle this problem,
particularly the compound travel mode characteristics where each
man travels by "Plane & Boat", "Plane & Bus", Plane & Trolley",
Train & Boat", "Train & Bus", or "Train & Trolley" .
The clues partially specify travel by such statements as "traveled
by train", etc.
The alternative approach posted here has the facts and rules
hard coded into the program. More flexible for the
programmer but not of much use to the non-programmer. The program
uses "exhaustive search with pruning" to find the
solution quickly. There are 373,248,000 possible
solutions which might take an hour for the computer to check
But if we start by generating all possible assignments of Travel
Mode to First names, there are 720 possibilities.
(Dennis has one of 6 modes, Jeremy, has one of the remaining
5, etc. and 6x5x4x3x2x1 = 720). Each of these 720 will
have 720 ways to assign last names and each of those will have 720
ways to assign occupations. The large total stated above is
this product 720x720x720.
But back to the point, from Clue #7 we know that Dennis
traveled by Train. Since 1/2 the possibilities have him
traveling by Train and 1/2 by Plane, then half the time we
can stop checking after this test and we have "pruned" our
search space by 50%. If Dennis did travel by train for a
specific permutation, we can check to see if Vince traveled by
boat (Clue #6). He only does this in 1/3 of the outcomes, so
we have eliminated another 2/3 of the cases by this second test
and only 1/6 of the 373 million will need to be checked further.
Each successive rule will eliminate 5/6, 2/3, 1/2, 1/3,
or at least 1/6 of the remaining cases to be checked which if we
are applying several rules, quickly prunes the space to those
possible solutions that pass all of the test applied.
For the non-programmer, I have made a table in plain English
(there are 29 of them in their current form) which the user can select or ignore for any
test run. And of course, selecting all of them will be
the spoiler and give you the final solution, so do not run that
choice unless you have given up on solving it manually.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for Programmers
I assumed permutations of the 6 Last names, 6 Travel modes and
6 Occupations, represented the 6 First names in alphabetical
order. Here are the actual Delphi statements that assign
names to the various numeric values
{We will assume we are checking
first names in this order}
Dennis=1; Jeremy=2; Leroy=3; Myron=4; Russ=5; Vince=6;
{Then we will permute these 6
travel mode combinations, filtering as we go}
PlaneBoat=1; PlaneBus=2; PlaneTrolley=3; TrainBoat=4; TrainBus=5;
TrainTrolley=6;
{Any that pass First name-travel
mode rules will get checked against last name
rules with names permuted in this order}
Barclay=1; Henley=2; Potter=3; Rogers=4; Strong=5;Whitman=6;
{Finally remaining possibilities will get checked against rules
that involve
occupations in this order}
Ag=1; Gems=2; Mfg=3; Mining=4; Oil=5; Research=6;
So a solution like
Dennis, Rogers, Mining, Train/Trolley
Jeremy, Henley, Research, Plane/Trolley
Leroy, Strong, Gems, Plane/Bus
Myron, Whitman, Mfg., Plane/Boat
Russ, Potter, Agriculture, Train/Bus
Vince, Barclay, Oil, Train/Boat
is represented by permutation 425631 for Last
Names, 462315 for Occupations and 632154 for Travel Modes.
Special functions were written to identify rules which
specified only half of one of the travel modes (e.g. N
represents a Train if N>3,; N is a Bus if N=2 or N=5, etc.).
Permutations are generated for travel modes first, since those
seemed to do the most pruning early on; even negative rules
(..is not ...), eliminate 1/3 or 1/2 of the remaining choices. . Permutations
that pass the Fist-name vs. Travel Mode tests move to to the Last
Name permutations, where we apply all of the tests for First Name
vs. Last Name and Travel Mode vs. Last name. Finally
those that pass those filters get to Occupation permutations which
check Occupation vs. everything else. And, if all works
correctly a single possibility will fall out the bottom as the
unique solution.
Running/Exploring the Program