Xmas said:
DemoCoder said:
Try this one:
Or another one:
You are given a write once memory with 7 bits. That is, once a '1' bit is written to a position, it cannot be changed. How can you write a 3-bit number (integers 0-7) 4 times into this memory? For example, I want to write the numbers 5, 2, 6, 3 into this memory. After each write, I should be able to read the number back unambiguously.
That seems to be only possible if the sequence of numbers is known beforehands.
Nope, I'll explain.
A projective plane of order N is a plane with N^2 + N + 1 points, N+1 lines, with the following properties
1) any two points define a line
2) any two lines determine a point
3) each line contains n+1 points on it
4) each point has n+1 lines through it
Basically, a projective plane has no parallel lines. All lines intersect somewhere. See
http://mathworld.wolfram.com/ProjectivePlane.html
Let's consider the special case of the projective plane of order 2. It has 7 points, 7 lines, is related to many other branches of math, and looks like this
I am now going to show you how to store 4 3-bit integers into 7 bits, in any order, without the sequence being known before hand.
As a general rule, if the memory is in state
i and you want to store an
i, then do nothing.
1) if the memory is empty, and you want to store I, write a '1' into bit position I. To read back, if memory contains only 1 bit, then that bit position represents the integer we stored.
2) if the memory contains 1 bit, and is in state I, and you want to write J, then store '1' in position K where {I,J,K} are on a line in the Fano plane. (see picture).
To read back, if memory contains just two '1' bits, then the state of the memory is the empty third position on the line in the Fano plane containing the positions. (e.g. if bits 5 and 2 are '1', then look in the plane for a line defined by 5 and 2, and that means the memory contains '3', the other point that is on the line)
3) if the memory contains 2 bits, and you want to store I, put in two more '1' bits (anywhere) such that atleast one of four 1 bits is position I, and the other 3 are on a line in the Fano plane
To read back, if memory contains 4-bits, look in the fano plane for the three points that are co-linear. The one left all by itself (not on a line) is the state of the memory.
4) to store I, if bit position I is 0, write two '1's into the other two 0 bits. If bit position I is '1', find the line containing I and J (where J is the current "state" of the memory) and put a 1 bit there.
To read back:
if memory contains 6 '1' bits, then the number stored is the only bit that is not a '1' (the 0 bit). E.g. the only point in the fano plane not "marked"
If the memory contains 5 bits, then the number stored is found by taking the two bit positions that are 0 bits, looking at the line in the fano plane containing those two points, in which case, the value stored in the third point.
Let's walk through storing 5,2,6,3.
First, let's store 5. I put a '1' bit in position 5 (numbered left from 0)
0 0 0 0 0 1 0
I can unambiguously read this back of course
Now let's store 2. There is a 1 bit already, so I follow rule two. Find the line containing 5,2 and store the third point. (look at diagram, 5,2,3 are on a line), so I write '1' in position 3
0 0 0 1 0 1 0
I can read this back easily by looking up the line with 5,3 and finding '2' as the third point.
Now let's write 6. The memory contains 2 '1' bits, so I need to write two more '1' bits for a total of 4. Atleast one of them has to be bit position 6, and the other three must form a line. Let's write bits 6 and 2
0 0 1 1 0 1 1
I can read this back by looking at the fano plane and seeing that 5,2,3 define a line, and 6 is by itself.
Now, I want to write a '3' bit. I have to follow rule 4. Since 3 is already marked, the rule says to find the line containing the previous state (6) and the number I want to write (3), and put a 1 into the other point on the line defined by 6 and 3, that's 4.
0 0 1 1 1 1 1
I can read this by noticing bits 0 and 1 are '0', looking at those two points in the Fano plane, and seeing that the line they are on is 0,1,3, therefore 3 is the state of the memory.
Magic eh? That's why I remember this after seeing it like 9 years ago in school, an amazing result. The fano plane is beautiful as is the related structures (Latin squares, block designs, steiner triples, etc)
BTW, my fano plane is labeled differently than the one in the image I linked. Draw a triangle, label the corners 6 5 3 in clock wise fashion. In between 6 and 5 at the midpoint, label 1. In between 5 and 3, midpoint label 2. In between 3 and 6, midpoint label 4. And in the center of the triangle, put a 0.
Now draw lines 1,0, 3 2,0,6 4,0,5 and a circle 1,2,4
I'll PM the answers so that others can have a go.
