[REBOL] Re: Another coffee break problem?
From: joel:neely:fedex at: 11-Nov-2003 7:35
Hi, Anton...
Anton Rolls wrote:
> I can see you are going to ask us to
> generalize it later so it can do integers
> higher than 8.
>
Since Gregg has already partially debagged the cat, I'll admit that
I have some generalizations in mind, but not that particular one ;-)
> I think for this set of numbers 12 is the
> only sum you will get, but just to be clear,
> shouldn't it be: "it's a magic square because
> each row and column sum to the same number" ?
>
Yes, but only because a square is a rectangle with the same height
and width...
WARNING: YOU ARE NOW ENTERING THE [scary music] ALGEBRA ZONE!
A rectangular display of numbers with R rows and C columns contains
R*C cells. The simplest way to fill those cells with distinct values
is to use the first R*C natural numbers, such that 0 <= n < R*C. The
sum of all of the values is then
(+i : 0 <= i < R*C : i) = R*C * (R*C - 1) / 2
Adding the requirement that all row totals be equal tells us that the
row total must be the grand total divided by the number of rows, so
all row totals = R * C * (R * C - 1) / 2 / R
= C * (R * C - 1) / 2
and likewise
all col totals = R * C * (R * C - 1) / 2 / C
= R * (R * C - 1) / 2
so that e.g. for a 3 x 5 "simple magic" rectangle,
grand total = 3 * 5 * (3 * 5 - 1) / 2
= 15 * 14 / 2
= 15 * 7
= 105
all row totals = 105 / 3 = 35
all col totals = 105 / 5 = 21
and, of course, if R and C are equal, the magic row and col totals
will be equal (so e.g. for the 3 x 3 case, 9 * 8 / 2 / 3 = 12).
If I wanted to be sneaky, I'd ask how many magic rectangles there are
with 99 rows and 100 columns!
YOU ARE NOW ENTERING AN ALGEBRA-FREE ZONE! ;-)
HINT AHEAD -- Don't read if you want to solve it on your own steam!
.
.
.
.
.
.
.
.
.
.
Since there are 362880 ways to arrange 9 distinct values, the key
issue is to do something more economical than simply generating all
possible permutations, checking each one for magicness.
-jn-
