Solving seemingly simple math problems using Perl
Checking Is Better
The phrase "trust is good, checking is better" turns out to be true here. Listing 2 reads the formatted output from Listing 1 and, using the hash reference $met
, checks whether the participants actually are in a class with different people each time. If the script comes back without any output, everything is okay.
Listing 2
combi-verify
Prime Powers are More Difficult
However, if the array dimension is not a prime number, as with the initially requested 9x9 squares, the matter is more difficult. A solution doesn't even exist for a 6x6 arrangement, which Euler found out when he tried to make 36 officers from six different regiments, each with six different service ranks, march for a parade without either ranks or regimental affiliations repeating within a row or a squad [6].
He correctly concluded that this was theoretically impossible, but he also carelessly and hastily got carried away, making the assumption that there would also be no solution for dimensions 4n+2. A huge mistake! More than 150 years later, precisely in 1959, it turned out that there are actually solutions for 10x10 and 14x14. However, the fact that the problem of 36 officers is unsolvable has been well and truly proved by now.
Nine-Element Galois Field
If the dimension is a prime power (e.g., 9, the second power of the prime number 3), then you can use a Galois field F to construct the squares. This is a collection of n numbers for which the arithmetic operations of addition (+) and multiplication (*) are defined and, in turn, return a result in F.
In relation to the problem with the nine teachers, 18 male students and 27 female students, the Canadian mathematician suggested dividing them into six groups, each with nine participants: the teachers, the A- and B-male students and the C-, D-, and E-female students. He then formed the nine-element body made up of complex numbers (i2=-1),
F = {0, 1, 2, i, 1+i, 2+i, 2i, 1+2i, 2+2i}
reducing the addition and multiplication with modulo 3, thus ensuring that a combination of two elements from F again results in an element from F. For example,
(1 + 2i) * (1 + i) = -1 + 3i
which modulo 3 reduces to 2+0i, so to 2, which is again in F.
If you characterize the operations + and * as the field operations of addition and multiplication with modulo 3 that keeps the result within F, you can generate the numbers of participants in the groups using the formulas in Figure 8. In this representation, the variable d refers to each day's sequence number (1 to 9) and g to the number of the group (also 1 to 9). The result is the sequence number of the individual participant from the six different sub-classes showing who is in the particular group on the specified day.
Listing 3 merely implements these formulas and outputs the result for nine days, as initially shown in Figure 3. The array @field
defines the complex numbers in the Galois field in lines 5 to 9, and the function mapback()
from line 17 again selects the index of the element in F for a numeric result (e.g., the result of multiplication).
Listing 3
combi-design
The functions fadd()
and fmult()
(lines 41 and 52) implement the addition or multiplication reduced by modulo 3 of two elements from the field F. They receive the elements' index numbers, select the associated complex numbers from F, apply the respective operation to the real and imaginary parts of the operands, and trace the result back to the index of an element in F using mapback
.
The Galois field is named after the French mathematician Évariste Galois, who achieved a major mathematical breakthrough at the tender age of 18. What he might have achieved is pure speculation because he was involved in a pistol duel at the age of 20 in which he drew the short straw, dying the next day of his gunshot wound.
That's how it was in the 19th century: milestones in discrete mathematics one day and out with the flintlock pistol the next morning to shoot offenders. Life sure was exciting back then!
Mike Schilli
Michael Schilli works as a software engineer in the San Francisco Bay Area in California. In his column, which has been running since 1997, he researches practical applications of the Perl scripting language. He is happy to answer questions at mailto:mschilli@perlmeister.com.
Infos
- Usenet posting from 1996: https://groups.google.com/forum/m/?fromgroups#!topic/rec.puzzles/kSsEDkm1_gw
- Galois field: https://en.wikipedia.org/wiki/Finite_field
- Latin square: https://en.wikipedia.org/wiki/Latin_square
- "Mutually Orthognal Latin Squares and Finite Fields" by Padraic Bartlett, 2012: http://math.ucsb.edu/~padraic/mathcamp_2012/latin_squares/MC2012_LatinSquares_lecture2.pdf
- Listings for this article: ftp://ftp.linux-magazine.com/pub/listings/magazine/179
- Thirty-six officers problem: http://en.wikipedia.org/wiki/Thirty-six_officers_problem
« Previous 1 2 3
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.