|
|
The most complicated puzzle I ever saw
A couple of years ago, back then I was working for the German company
Softlab, my collegue Sepp Kamerloher
brought up a mathematical puzzle with a real background: A friend of
his, who happened to be a teacher, tried to set up school meetings
by grouping participants in a certain way, but failed to do so because
of the complexity of the problem.
We all tried hard, but none of us software engineers was able solve
the problem, either --
so I posted the question to rec.puzzles, a Usenet newsgroup for
mathematical problems. Shortly after, a mathematician from Canada
responded, throwing breath-taking mathematics at the problem. He
came up with a solution which was far beyond what anyone thought
possible! All I had to do was write a short Perl script ... Enjoy!
----------------------------------------------------------------------
Newsgroup: rec.puzzles
Subject: Hard to solve real world prob
Date: 1996/01/15
Author: Michael Schilli
----------------------------------------------------------------------
Hi everybody,
i got a puzzle with real background: When a collegue told me the
problem, it seemed easy for me solving it with a simple program
in a few minutes. But oh! After spending several *days* programming, I
gave up. This is one of the strangest things I ever saw.
Don't underestimate the problem like I did.
Try to solve it! Any help apprechiated.
Michael.
There are
18 boys
27 girls
9 instructors
and the task is: The kids and the instructor shall meet on 5 days in 9
groups per day with
2 boys
3 girls
1 instructor
each and the groups are to be put together that way
THAT NEITHER ANY KID OR ANY INSTRUCTOR MEET IN THE SAME GROUP
MORE THAN ONCE DURING THE 5 DAYS.
The solution should look something like that:
DAY1 GROUP1 boy1 boy2 girl1 girl2 girl3 instr1
DAY1 GROUP2 boy3 boy4 girl4 girl5 girl6 instr2
...
DAY2 GROUP1 boy17 boy18 girl23 girl24 girl25 instr2
DAY2 GROUP2 boy15 boy16 girl14 girl15 girl16 instr3
...
...
I tried several strategies: Starting with just filling the groups one by one
(you'll get stuck before the second day), then backtracking
(how long does it take to backtrack like 10^50 possiblities?) ...
Good luck, folks!
----------------------------------------------------------------------
Newsgroup: rec.puzzles
Subject: Re: Hard to solve real world prob
Date: 1996/01/18
Author: heuser13 (Barry Wolk)
----------------------------------------------------------------------
First, it is not clear from your statement exactly what the conditions are. I am
interpreting them as follows: each person is in a different group number
every day, and every two people meet each other at most once. "They meet"
means they both are in the same group on the same day.
I have answered several design problem here in rec.puzzles, but this has to
be the most complicated one. And yet, if you throw enough mathematics at
the problem, it is actually quite easy. The magic words are
"9-element Galois field" and "mutually orthogonal 9-by-9 latin squares." If
you know what all that means, you should see immediately how to do this
problem. However, I promise not to use those words again.
We start with the complex numbers, written a + b i, with i^2 = -1. Let F be the
following 9-element subset of the complex numbers:
F = { 0, 1, 2, i, 1 + i, 2 + i, 2 i, 1 + 2 i, 2 + 2 i }
Define "addition" on F as follows: for any 2 elements of F, add them in the
usual way as complex numbers, and reduce the sum mod 3. This will give
an element of F, which is defined to be the result of that addition. The key
point is that, whatever the answer is, it must belong to F.
Define "multiplication" on F similarly, by reducing mod 3 the ordinary
product of complex numbers, to get an element of F as the answer.
I will use + for ordinary addition, and +_ for this "addition" on F.
Similarly, let * denote ordinary multiplication, amd let *_ denote
this "multiplication" on F.
Examples:
(1 + 2 i) + (2 + 2 i) = 3 + 4 i Reducing this mod 3 gives
(1 + 2 i) +_ (2 + 2 i) = 0 + 1 i = i, which belongs to F.
(1 + 2 i) * (1 + i) = -1 + 3 i Reducing this mod 3 gives
(1 + 2 i) *_ (1 + i) = 2 + 0 i = 2, which belongs to F.
Now, split the 18 boys into 2 sets, called A and B, each set having 9 boys.
Split the 27 girls into 3 sets, called C, D and E, each set having 9 girls. The
problem only asks for 5 days, but I will give a schedule for 9 days. So
EVERYTHING has 9 elements, namely the groups, the days, the instructors,
the A-boys, the B-boys, the C-girls, the D-girls, and the E-girls.
Number each of these things by using the elements of F as indices. So I
can talk about group number 0, instructor number 2+i, day number 1+2i, etc.
Finally, after all those preliminaries, here is the schedule. If g and d are
elements of F, the following people are in group number g on day number d:
instructor number (d +_ ( 1 *_ g)) = d +_ g
A-boy number (d +_ ( 2 *_ g))
B-boy number (d +_ ( i *_ g))
C-girl number (d +_ ((1+i) *_ g))
D-girl number (d +_ ((2+i) *_ g))
E-girl number (d +_ ( (2i) *_ g))
The specific elements of F that appear in these formulas are unimportant,
since any 6 distinct non-zero elements of F can be used.
To prove that everything works, you need to check several algebraic
properties of these operations +_ and *_ . Here is an example:
When does A-boy number a meet C-girl number c? If this
happens in group number g on day number d, then we must have
d +_ ( 2 *_ g) = a, d +_ ((1+i) *_ g) = c
However, those 2 equations have a unique solution for the
2 unknowns d and g. So these 2 people meet exactly once.
Have fun trying to translate this solution into the form of the answer that you
suggested.
Ignore the "From:" line -- heuser13 is a terminal, not a person.
Barry Wolk
Dept of Mathematics
University of Manitoba
Winnipeg Manitoba Canada
----------------------------------------------------------------------
Newsgroup: rec.puzzles
Subject: Re: Hard to solve real world prob
Date: 1996/01/21
Author: Michael Schilli
----------------------------------------------------------------------
Standing ovations for Barry Wolk! He really made it. The following short perl
program I wrote creates the output above - which is, believe it or not, a valid
solution for 9 days!
Thanks to everybody for helping in this puzzle.
Michael.
#!/usr/bin/perl -w
foreach $day (1..9)
{ foreach $group (1..9)
{ print "DAY$day GROUP$group: ";
print "i", fcalc($day, '+', fcalc(2, '*', $group)), " ";
print "b", fcalc($day, '+', fcalc(3, '*', $group)), " ";
print "b", fcalc($day, '+', fcalc(4, '*', $group)) + 9, " ";
print "g", fcalc($day, '+', fcalc(5, '*', $group)), " ";
print "g", fcalc($day, '+', fcalc(6, '*', $group)) + 9, " ";
print "g", fcalc($day, '+', fcalc(7, '*', $group)) + 18, "\n";
}
print "\n";
}
### Syntax: fcalc($fval1, '+'|'*', $fval2), $fval=1..9
sub fcalc
{
my($f1,$op,$f2) = @_;
my @F = ( [0,0], [1,0], [2,0], [0,1], [1,1], [2,1], [0,2], [1,2], [2,2] );
my @res;
$f1--; $f2--;
my($r1,$i1,$r2,$i2) = ($F[$f1][0], $F[$f1][1], $F[$f2][0], $F[$f2][1]);
($op eq '+') && (@res = (($r1 + $r2)%3, ($i1 + $i2)%3));
($op eq '*') && (@res = (($r1 * $r2 - $i1 * $i2)%3,
($r1 * $i2 + $r2 * $i1)%3));
for($i=0; $i<=$#F; $i++)
{ return($i+1) if $res[0] == $F[$i][0] && $res[1] == $F[$i][1]; }
}
__END__
Output:
DAY1 GROUP1: i1 b1 b10 g1 g10 g19
DAY1 GROUP2: i2 b3 b13 g5 g15 g25
DAY1 GROUP3: i3 b2 b16 g9 g17 g22
DAY1 GROUP4: i4 b7 b12 g6 g18 g20
DAY1 GROUP5: i5 b9 b15 g7 g11 g26
DAY1 GROUP6: i6 b8 b18 g2 g13 g23
DAY1 GROUP7: i7 b4 b11 g8 g14 g21
DAY1 GROUP8: i8 b6 b14 g3 g16 g27
DAY1 GROUP9: i9 b5 b17 g4 g12 g24
DAY2 GROUP1: i2 b2 b11 g2 g11 g20
DAY2 GROUP2: i3 b1 b14 g6 g13 g26
DAY2 GROUP3: i1 b3 b17 g7 g18 g23
DAY2 GROUP4: i5 b8 b10 g4 g16 g21
DAY2 GROUP5: i6 b7 b13 g8 g12 g27
DAY2 GROUP6: i4 b9 b16 g3 g14 g24
DAY2 GROUP7: i8 b5 b12 g9 g15 g19
DAY2 GROUP8: i9 b4 b15 g1 g17 g25
DAY2 GROUP9: i7 b6 b18 g5 g10 g22
DAY3 GROUP1: i3 b3 b12 g3 g12 g21
DAY3 GROUP2: i1 b2 b15 g4 g14 g27
DAY3 GROUP3: i2 b1 b18 g8 g16 g24
DAY3 GROUP4: i6 b9 b11 g5 g17 g19
DAY3 GROUP5: i4 b8 b14 g9 g10 g25
DAY3 GROUP6: i5 b7 b17 g1 g15 g22
DAY3 GROUP7: i9 b6 b10 g7 g13 g20
DAY3 GROUP8: i7 b5 b13 g2 g18 g26
DAY3 GROUP9: i8 b4 b16 g6 g11 g23
DAY4 GROUP1: i4 b4 b13 g4 g13 g22
DAY4 GROUP2: i5 b6 b16 g8 g18 g19
DAY4 GROUP3: i6 b5 b10 g3 g11 g25
DAY4 GROUP4: i7 b1 b15 g9 g12 g23
DAY4 GROUP5: i8 b3 b18 g1 g14 g20
DAY4 GROUP6: i9 b2 b12 g5 g16 g26
DAY4 GROUP7: i1 b7 b14 g2 g17 g24
DAY4 GROUP8: i2 b9 b17 g6 g10 g21
DAY4 GROUP9: i3 b8 b11 g7 g15 g27
DAY5 GROUP1: i5 b5 b14 g5 g14 g23
DAY5 GROUP2: i6 b4 b17 g9 g16 g20
DAY5 GROUP3: i4 b6 b11 g1 g12 g26
DAY5 GROUP4: i8 b2 b13 g7 g10 g24
DAY5 GROUP5: i9 b1 b16 g2 g15 g21
DAY5 GROUP6: i7 b3 b10 g6 g17 g27
DAY5 GROUP7: i2 b8 b15 g3 g18 g22
DAY5 GROUP8: i3 b7 b18 g4 g11 g19
DAY5 GROUP9: i1 b9 b12 g8 g13 g25
DAY6 GROUP1: i6 b6 b15 g6 g15 g24
DAY6 GROUP2: i4 b5 b18 g7 g17 g21
DAY6 GROUP3: i5 b4 b12 g2 g10 g27
DAY6 GROUP4: i9 b3 b14 g8 g11 g22
DAY6 GROUP5: i7 b2 b17 g3 g13 g19
DAY6 GROUP6: i8 b1 b11 g4 g18 g25
DAY6 GROUP7: i3 b9 b13 g1 g16 g23
DAY6 GROUP8: i1 b8 b16 g5 g12 g20
DAY6 GROUP9: i2 b7 b10 g9 g14 g26
DAY7 GROUP1: i7 b7 b16 g7 g16 g25
DAY7 GROUP2: i8 b9 b10 g2 g12 g22
DAY7 GROUP3: i9 b8 b13 g6 g14 g19
DAY7 GROUP4: i1 b4 b18 g3 g15 g26
DAY7 GROUP5: i2 b6 b12 g4 g17 g23
DAY7 GROUP6: i3 b5 b15 g8 g10 g20
DAY7 GROUP7: i4 b1 b17 g5 g11 g27
DAY7 GROUP8: i5 b3 b11 g9 g13 g24
DAY7 GROUP9: i6 b2 b14 g1 g18 g21
DAY8 GROUP1: i8 b8 b17 g8 g17 g26
DAY8 GROUP2: i9 b7 b11 g3 g10 g23
DAY8 GROUP3: i7 b9 b14 g4 g15 g20
DAY8 GROUP4: i2 b5 b16 g1 g13 g27
DAY8 GROUP5: i3 b4 b10 g5 g18 g24
DAY8 GROUP6: i1 b6 b13 g9 g11 g21
DAY8 GROUP7: i5 b2 b18 g6 g12 g25
DAY8 GROUP8: i6 b1 b12 g7 g14 g22
DAY8 GROUP9: i4 b3 b15 g2 g16 g19
DAY9 GROUP1: i9 b9 b18 g9 g18 g27
DAY9 GROUP2: i7 b8 b12 g1 g11 g24
DAY9 GROUP3: i8 b7 b15 g5 g13 g21
DAY9 GROUP4: i3 b6 b17 g2 g14 g25
DAY9 GROUP5: i1 b5 b11 g6 g16 g22
DAY9 GROUP6: i2 b4 b14 g7 g12 g19
DAY9 GROUP7: i6 b3 b16 g4 g10 g26
DAY9 GROUP8: i4 b2 b10 g8 g15 g23
DAY9 GROUP9: i5 b1 b13 g3 g17 g20
|
|
