A problem of combinatronic$ :: ATTN: Mr Mok Kong Shen
BenZen
I recently stumbled on Mr Mok Kong Shen's WWW page
and found two interesting cryptology related problems,
with a potential reward.
http://home.t-online.de/home/mok-kong.shen/
After someone kindly translated the combinatronics question
into Layman's language; I could make more sense of it and
the challenge seemed appealing so I already wrote a
program with some of my neophyte ideas about it.
Then I wondered about the 200$ reward.
What are the exact criterias, aside the fact Mr Shen expects the applicants
to be 'experts' as he states in the first parragraph ?
Then I noticed the date on this page:
Publication date: 14th Nov. 1997. Last revised: 3rd August 1999.
Certainly he must have received some satisfactory solutions since then ?
Then why does he still want to distribute this 200$ reward; Or is he very rich ?
I hope this is not a covered way to gather 'fresh ideas' for free while the reward
could never be really granted. Oh I know some University professors who are
constantly giving their little problems to students. One of them even started
a company with a idea from a fiend of mine; rewritten under his name.
But I am pretty confident this is not the case.
So I wonder, how many applicants have already received the reward ?
Could Mr Kong be kind enough to comment on the interesting ideas
he already received.
Or maybe some of you in this group already had the pleasure of wining the reward ?
Regards,
Neophyte cryptologist... Therefore I don't quality.
Ben
======== My 2 cent wort of combinatronics ===========
About my preliminary one night study on this particular problem, I attach my
own neophyte findings, from yesterday's work. This puzzle is amusing indeed.
------
HAMMING DISTANCE
A measure of the difference between two messages,
each consisting of a finite string of characterS,
expressed by the number of characters that need to be changed
to obtain one from the other. E.g., 0101 and 0110 has a Hamming distance
of two whereas "Butter" and "ladder" are four characters apart
(see error detecting code, error correcting code). (Krippendorff)
-------
-------
LATIN SQUARE background:
Latin squares are also linked to algebraic objects known as quasigroups.
A quasigroup is defined in terms of a set, Q, of distinct symbols and
a binary operation (called multiplication) involving only the elements of Q.
A quasigroup's multiplication table turns out to be a Latin square.
Each element of the set Q occurs exactly once in each row and each column
of the table.
Computer scientists have proved that the quasigroup completion problem
belongs to a category of difficult computational problems described as
NP-complete. As the number of elements, n, increases,
a computer’s solution time grows exponentially in the worst case.
A good link on this can be found here:
http://www.vsv.slu.se/johnb/java/latin2.htm
Basic program to create Latin Squares from random seed.
10 CLS : DEFINT A-Z: COLOR 15: PRINT "ANY POSSIBLE LATIN SQUARE"
20 COLOR 11: INPUT "ENTER NUMBER OF TREATMENTS"; N
30 INPUT "ENTER NUMBER FOR RANDOM SEED"; RN: RN = RND(-RN)
40 COLOR 15: DIM C(N): DIM A(N, N)
50 FOR R = 1 TO N
60 FOR C = 1 TO N: C(C) = C: NEXT C: J = N
70 FOR C = 1 TO N: I = 0
80 X = INT(RND * J + 1)
90 REM CHECK COLUMN IF OK (ROW IS INHERENTLY OK)
100 FOR H = 1 TO R - 1
110 IF I > 50 THEN 60: REM ROW NO GOOD
120 IF A(H, C) = C(X) THEN I = I + 1: GOTO 80: REM COLUMN NO GOOD
130 NEXT H
140 A(R, C) = C(X): J = J - 1
150 FOR K = X TO J: C(K) = C(K + 1): NEXT K: NEXT C
160 FOR CL = 1 TO N: PRINT USING "###"; A(R, CL); : NEXT: PRINT : NEXT
-------
Now Back to Shen's problem:
http://home.t-online.de/home/mok-kong.shen/#problem1
For arbitrary given m determine g(m) := max { n | H(m,n) > 0 }.
With the help of John; I could figure-out the question.
--- John Layman's language. ---
g(m) is the largest multiple of m for which there exists an m by g(m)
matrix of which the each group of m columns are an m by m Latin
square, so that within each of these squares, no two columns have the
same number in any row, and any two columns from two different squares
have exactly one number matching.
Defining H(m,n) as the number of _distinct_ such matrices, when we are
really looking for the largest n for which any such matrix exists, is
somewhat of a confusing smokescreen.
--------------------------------
--- Okay.. In Benzman's language now. ---
What Bubba wants is; For an arbitrary m the largest set of
Shen's squares(*) for which the following restrictions apply:
*) -A Shen's square is a variant of Latin Square with column 1
always be (1, 2, ..... m). 'm' being the size of a column.
-Also, Shen's sqares have a special property on any pairs of
its (m) columns. The total difference between elements of these
columns must be (m) also.
1) The superset of Shen's squares must be of a dimension: (m x n);
n being a multiple of m.
2) Between any pairs of columns within the whole set (n)
The total difference between elements of these columns must
be (m-1) also.
3) No two Shen's squares within must be considered equivalent.
Equivalence being defined as transformed to one other by
simple permutation of columns.
---------------------------------------
So we want the largest Bubba said !
Let's rewrite the sample basic algorithm in C language,
in which I can Zen it better. Boy it's gonna be a fun rainy saturday night ;)
Thanks bubba... I always wanted to work on N-complex proggies but my boss
would not let me.
Since I'm new to this, I'm gonna proceed in steps.
1) Write a simple C version of the random Latin square generator.
2) Add Shen's rules to generate a version 1, limited (m) size Shen square. ;)
3) Determine a better algorithm.
4) Get the money and give it to Tom St-Denis for summer break. ;)
A few minute reading the BASIC Latin square program sufficed
to make me sick; It's completely unstructured with goto's out
of loops; And dependent on a random trials and errors.
Impossible to predict computational time. == Trash.
Seems that I must write my own amusing version.
I studied a little to understand the Latin Square Theory better:
FACT 1: Marriage Theorem. (Taken from the web)
"Latin squares of order n are extremely numerous for n>3.
Indeed, the first row can be any one of n! permutations.
After the first row is chosen, there are approximately n!/e choices
for the second row (e is the base for the natural logarithm).
And, no matter how many rows are chosen less than n rows consistent
with being a latin square, it is always possible to choose another row.
So any consistent start with k rows can always be completed to
a latin square. This fact is based on a fundamental theorem in combinatorics
variously known as the Marriage Theorem and the theorem on
distinct representatives."
Playing with my own program, I found another interesting FACT.
FACT#2
We can Always build a Latin Square, from a ((i+j)modulo size)+1;
Where i,j are row,column indexes starting at 0.
IDEA:
From that starting square, I might build a program that can
then find the permutations to all other squares. When I can
establish the proper construction rules.
Indeed, this initial square fits Shen's criterias for column 1.
IDEA: From the symetry I could find four at a time.
Yet, the restriction for the first column prevents this on
the first submatrix.
IDEA: The non-equivalence criterias forbids to use row shuffling.
Only horizontal flips could be useful later.
IDEA: I noticed that in order to have Hamming value of m-1 between
submatrix, one item per column MUST be identical,
in each sub-matrix; since each column must have distinct value.
Then any of the rows between any sub matrix MUST have
exactly one match. This is a strong requirement that will greatly
limit the number of such sub-matrix, I call Shen squares.
(*) Then It's always possible to duplicate one row from submatrix 1,
onto the other ones.
A very efficient rudimentary formula like S(i,j) =((i+j)modulo size)+1,
can be adapted to this idea, by simple remapping of S(i,j) through a
vectored (indirection) matrix T. Matrix T1 is a array of permutable
pointers into a final result matrix S2; S, being the original Shen matrix
derived from ((i+j) mod m)+1;
Q:.. Instead of the obvious (duplicating an entire row onto each matrixes);
Is it possible to target just any row element S(Ki,j) ;Where Ki is an
element of a column hold array Ch(i) = [K1,K2...m].
ex: Fixing row1 for m=4; Ch = [1,1,1,1]; Then determine the proper
Transformation matrix T1 from it from a simple algorithm.
IDEA: I wonder if after a sufficient study, I can generalize the technique and
without even generating these Shen sub-matrix; determine the exact
number of allowed permutations for each; Thus giving rise to a simple
equation: F(m,n) = number of possible sub-matrix, for any m. By first
finding a rule that computes the greatest n, multiple of m.
IDEA: I shall eventually find-out it's a N-complex problem, but right now
the restrictions with Hamming of (m-1) on the sub-matrix seems
to be key limiting factor.
Other ideas are being tested in my preliminary BenShen Square program.
This was my two cents worth; Wishing good luck to the neophytes like myself.
===========================================================
Mok-Kong Shen
BenZen wrote:
>
[snop]
> Then I wondered about the 200$ reward.
> What are the exact criterias, aside the fact Mr Shen expects the applicants
> to be 'experts' as he states in the first parragraph ?
I am happy that you have interest to tackle the problem.
The reward is yet open. The criteria is that you have
to give a proof of the result just like any accepted
results in mathematics are proved. (As to the word
'expert', anyone who solves the problem is an expert
for me (compared to myself whose poor knowledge is
not sufficient to solve it).)
M. K. Shen
BenZen
I will continue to work on the problem at leisure time,
while understanding the Mathematical proof is currently out of my reach.
You are kindly, very humble, and I conclude noone has yet resolved it.
I shall hereby present my excuses for doubting your purpose,
and continue to appreciate and share your Mathematical enthousiam.
I should have known better from reading your favorite citation:
'Should not we, then, exert ourselves to do good? '
-From Tai Shang Kan Ying Pien. Probable author: Ko Hung, 4th century A.D
Here is one of my favorite:
"Turn your face to the sun and the shadows fall behind you." -Maori proverb
This is also on my top ten list:
"Vision without action is a daydream. Action without vision is a nightmare."
-Japanese proverb
But there is one thought that emerged while talking a walk this winter,
and I noted it; It is not in my habbit, and that alone makes it my favorite. ;)
There is no peace of mind without purpose.
There is no rest, each day at a time.
There is no glory, without proper ending.
Regards,
Benoit Jobin AKA: Ben Zen.
========================
akh tI akh gAyi ka:h -Kashmiri
One plus one make eleven.
(In unity there is strength. Two heads are better than one. )