Thursday, November 12, 2009

Robert A. Kraus' Logic Puzzles

I just found out about half an hour ago that GeoCities has shut down.

Within the last decade, I've only visited 2 sites within GeoCities: mine (created when I was still a teenager), and another by Robert A. Kraus. Frankly, only the latter is worth talking about.

Kraus had authored several logic puzzles and hosted it on the site. The most interesting collection for me is what he called "meta-puzzles". These puzzles are way too tedious to solve manually, and a spreadsheet program is the suggested tool to use.

I enjoyed these puzzles. If I were to introduce someone who enjoys puzzles and brain teasers to the joy of problem solving with a computer, this would be the way.


Here's my solution to one of his meta-puzzles in Maple.
Inheiritance Envelopes (by Robert A. Kraus)

A wealthy man had three sons all of whom were quite good at math and logic. To get a share of his inheiritance each had to correctly determine a positive integer which he had chosen. He told them that the number had four different non-zero decimal digits, in ascending order.

He prepared three sealed envelopes each of which contained a number. The first contained the product of the four digits, the second contained the sum of the squares of the four digits, the third contained the sum of the product of the first two digits and the product of the last two digits, and the envelopes were clearly marked as such. He showed the three envelopes to the three sons and had them each take one at random.

The sons were stationed at three different computers so that they couldn't communicate with one another (but were linked to the father's computer). After one hour they could submit a number or decline. Anyone who submitted a wrong answer would be eliminated and get nothing. If one or more submitted the correct answer they would each receive a share of the inheritance, and the contest would end with the others getting nothing. If no one submitted the correct answer they would be instructed to work on the problem for another hour. The process would repeat as often as necessary. Each of the sons decided not to submit an answer unless they sure it was correct.

At the end of the first hour no one had submitted an answer.
At the end of the second hour no one had submitted an answer.
At the end of the third hour no one had submitted an answer.
At the end of the fourth hour all three of them submitted the correct answer!

Can you determine the number?
F := [
L -> L[1]*L[2]*L[3]*L[4],
L -> L[1]^2 + L[2]^2 + L[3]^2 + L[4]^2,
L -> L[1]*L[2] + L[3]*L[4]

filter := (S, pred) -> map(m -> `if`(pred(m), m, NULL), S):

mapMultiset := (f, pos) -> {op(
convert(map(f, [op(pos)]), multiset)

singles := (f, pos) -> filter(pos,
p -> member([f(p), 1], mapMultiset(f, pos))

allSingles := (pos) -> op(map(singles, F, pos)):

pos := {op(combinat[choose](9, 4))}:
pos := pos minus (`union`(allSingles(pos))):
pos := pos minus (`union`(allSingles(pos))):
pos := pos minus (`union`(allSingles(pos))):
sol := `intersect`(allSingles(pos)):
> sol;
{[3, 4, 7, 9]}
> F(op(sol));
[756, 155, 75]

No comments:

Post a Comment