22 Jun 2002 (updated 22 Jun 2002 at 15:27 UTC)
»
Jobhunt
Status: Successfully gained freelance project work for a couple of people. Possibility of training.
Interesting problem number one:
The basis of this problem descends from an idea in Jack Cohen and Ian Stewarts book "the collapse of Chaos". The idea is this:
DNA contains some (if what limited) redundancy. This redudancy is in the form of the dna sequence CAT where to be mutated into CAC that they both specify the same amino acid.
Could this prinicple be applied to computer communications? To see, I proposed the following question:
Inital setup:
Using the nth base, and having a number which has a length of b
bits, there are of course, b ^ n possible different permutations of
the number (Assuming that you can not have any blank spaces).
These numbers can then all be placed as nodes on a grid, with lines
connecting each point of the grid elsewhere, but they are placed in
such a way that if you move from one node to the next node, only one
bit will change. I.e. using a base ten system, you could make a valid
move from 15 to any in the following set:
{ 05, 10, 11, 12, 13, 14, 16, 17, 18,
19, 25, 35, 45, 55, 65, 75, 85, 95 }
For a base 2 system, this is commonly known as a Kernaugh map.
ie
0 0 1 1
0 1 1 0 Where the number for each node can be read by
| | | | reading the top and side values.. for the point
00 -+-+-+-+- marked with a O, it represents the value 1101.
| | | |
01 -+-+-O-+-
| | | |
11 -+-+-+-+-
| | | |
10 -+-+-+-+-
| | | |
Question:
How many points can you get onto the grid, where each point satisfies
the following rule:
a point nor its direct neighbours (ie all the nodes which have a
single bit's difference between them and the point) can not
intersect with another point OR another point's direct neigbours.
Is there a rule to say how you should arrange them? What is the
relationship between the number of points and the number of moves
between them (assuming you can ignore the above rule).
I think that I have solved it for a base two system, but am working on a proof for it. hahaha
Erratum
A b bit system of the nth base will have n^b combinations