Balanced Incomplete Block Designs, Difference Sets, Klein's Quartic Curve, Projective Planes, and lots more!

I've been busy lately and unable to provide the answer for the Extreme Programming Code Review problem posted last time. I chose this problem, because when I was taking a graduate combinatorics class in college, the underlying problem had an almost mystic relation to a large number of other areas of combinatorics and geometry, as well as producing a simple, but beautiful and symmetric structure.

Mathematical history has many examples of similar, but harder arrangement problems. Catherine The Great supposedly kicked things off by posing to Euler, The 36 Officers Problem. Later, Kirkman proposed the 15 schoolgirl problem (my oh my, a Reverend and thoughts of schoolgirls eh?). These seemingly simple problems acted as a catalyst and resulted in great advances in the field of combinatorics, which has enormous applications in many fields. One application of course, is solving the problem I posed.

The problem says, given 7 people, arrange them into 7 teams of 3 each, such that no two people are ever on the same team twice. It is probably possible to construct this design using trial and error, but there are many other ways to do it.

Let us number the programmers 0 through 6, and start off with the team {0,1,3}. If we were to add 1 to each number, it is easy to see that the new team will consist of 3 new members, no two of which are in the first team. {1,2,4} And likewise, the same will be true for each new team, for all teams {x+0, x+1, x+3} up to x=0 to 6. The first two positions will always differ by 1, the second and third by 2, and the first and third by 3. If you read down the three columns, we're just rewritten the numbers 0 through 6 shifted by 1 or 2 places. Here's our list of teams, you can also verify them by visual inspection.

{0,1,3}
{1,2,4}
{2,3,5}
{3,4,6}
{4,5,0}
{5,6,1}
{6,7,2}

It turns out that this solution is also unique except for permuting order.

Combinatorics describes this as a t-(v,k,l) design. A t-(v,k,l) design is a set P of v points, a set of subsets of P called blocks (also called lines) B containing k points, and an incidence structure I in P * B which describes the relation of P and B (which elements of P are in which blocks). For any t points, exactly l blocks are incident.

Our problem says that there are p=7 points, and it says that for any t=2 points, they are contained in only l=1 block (team), and the blocks consist of k=3 points. Therefore, our problem is to construct a 2-(7,3,1) design. Such 2-designs are called Steiner Triple Systems and denoted STS(7). One result of combinatorics is that STS(v) exists if and only if v = 1 or 3 (mod 6).

So what's so special about this problem to get so worked up about? It turns out there are many connections with STS(7) and other areas of mathematics, in addition to which I mentioned in the header, there are also connections to coding theory, latin squares, octonions, simple groups, and geometry.

And now I will show you how this problem is connected to the Balsa Wood problem, as well as to very beautiful geometry.

Recall that there are 7 teams of 3-programmers, 7 programmers, no two programmers are on the same team twice. Remember back to the defination of a 2-(7,3,1) design, the programmers are called "points" and the teams are called "lines". If no two programmers are on the same team twice, that means 2 programmers (or points) uniquely determine a line, and also, that at most, two teams can only have 1 programmer in common, which says that any two lines intersect at one and only 1 point. Hmm...

• 7 points
• 7 lines
• 2 points determine a line
• 2 lines determine a point

What would happen if we wrote down those 7 programmers and connected the dots according to teams?



We form what's called a projective plane. This plane, the projective plane of order 2 called the Fano Plane has the interesting property that there are no parallel lines. It also has a 168-fold symmetry. (another interesting property, since each line has 3 points as well as each point is incident with 3 lines, you can interchange points and lines to no effect! The Fano Plane is its own dual.)

How can we use this to solve the Balsa Wood problem? I will give a partial solution, by showing the solution for 3 successive writes.

• if you are writing X and the ram is already in state X, do nothing
  
• if the ram is empty, and you're writing I, then place a 1 in bit position I
• if the ram contains 1 bit in position I and you are writing the number J, find a line (I,J,K) and place a 1 in bit position K
• if the ram contains 2 bits in positions I, K, and you are writing value X, write 2 more bits such that 3 of the bits will be colinear on a line, and X will be a point NOT on that line. That is, if X != I or != K, then find the line (I,J,K) and place a 1 bit in position J, as well as in position X. If X == I then write two bits on the other line containing K, and if X == K, then write two bits on the other line containing I.

Step 2 and 3 work because of the inherent property of projective planes. Step 2 works because 2 points uniquely determine a line. Step 3 works, because no matter what, there are three lines intersecting any point colinear with X, therefore, you can always place 2 1-bits on one of those lines.

The rules for reading are as follows:

• if the memory is blank, nothing has been written yet
• if exactly one bit is written in position I, then the value in the memory is I
• if exactly two bits are written in position I and K, then the value in the memory is J, where J is on the line containing I and K
• if exactly 4 bits are written in positions X, I, J, K, find the 3 positions which form a colinear line, the one which is "left out" by itself is the value in the memory.

I leave the construction of the final rule for writing and reading, as well as an argument as to its correctness to the reader. There is an alternate solution to this problem by using womcode techniques, which have applications to both error correcting codes and cryptography. Sadly, Rivest and Shamir seemed to have patented it, and the solution to the Balsa Wood problem actually violates the patent.

Another related problem to look up is the Transylvanian Lottery Problem, also solved with the Fano Plane.


-Ray

The Extreme Programming Code Review Problem

You manage a team of 7 programmers and have become a recent convert to extreme programming. You have decided to use a style of pair-programing that you call the weekly triplet review.

Each day of the week, 3 programmers will be picked from the 7 available to conduct code reviews together such that no two programmers will ever be on the same team more than once in one week. (Note, these programmers work on weekends too, so you need 7 teams of 3.)

If the programmers are numbered 1 through 7, can you enumerate all the possible teams?

-Ray

P.S. It is no coincidence that this problem features 7 objects like the previous problem. Believe it or not, this is a hint: if you solve this problem, you may have some inspiration for how to solve the Balsa Wood RAM problem.

Puzzles you can't solve with Google

One of the techniques that people commonly use in interviewing software engineers is to use puzzle questions to ascertain the problem solving process of candidates. However, the problems themselves are generally drawn from commonly asked puzzle questions, some of them even famous puzzle problems, which lets candidates solve them either by search engine, or by memorization.

So what's a good source of problems to ask which are not generally available on the internet? Well, many college mathematics or computer science textbooks contain obscure and hard example problems which are not generally covered in internet discussions.

One of them, that I encountered over 12 years ago, still burns in my memory today because of connections with quite beautiful mathematical structures. I will reproduce the problem below, obfuscated from the original way it was stated, in order to avoid book searches. I have only seen this problem discussed twice by others in 20 years of internet usage. It has analogous solutions in some ACM/IEEE/CiteSeer references, but in general is not discussed in IT or Puzzle literature.

I will post the solution later in another message.

The Balsa Wood RAM Machine

You are given a computer attached to a unique memory device consisting of a number of sticks of Balsa Wood, 7 to be exact. The computer can read from this memory by checking to see whether a given stick of wood in position X is either broken or unbroken, representing a 1 or a 0 respectively. The computer can also write to this memory, but it can only write *1* bits, it cannot write a 0, that is, it can break sticks, but it cannot repair a broken stick.

The computer operates on decimal number in the range 0-6, and the question arises, how many times can the computer write a number to the RAM and read it back? What would the read and write procedures look like?

As an example, you can imagine that if the RAM is empty, if you want to write a decimal value X, you place a 1 in the Xth RAM position (break stick X). You read this value back by observing which position contains a broken stick.

The RAM however has 6 more unbroken sticks, can't we use this to support multiple writes? Yes, a second write could be supported for value Y by breaking all sticks except Y, in which the read procedure would be to observe which stick is left unbroken.

Those are the trivial procedures. What about 3 writes or 4? It turns out that 4 writes are possible. So, the question is:

Specify an algorithm for writing 4 values into the RAM and being able to read them back at each step, without foreknowledge of what was written before.

That is, your task is to produce two procedures: WRITE(BitSet current, Integer valueFromZeroToSix) -> returning BitSet and READ(BitSet current) -> returning Integer, in which the following is true:

1) WRITE returns a new BitSet produced by taking the old BitSet and changing only 0 to 1s. It also replaces the current bitset with the return value.
2) READ(WRITE(current, X)) == X
3) Any sequence of WRITE and READ operations may occur as long as the number of WRITE operations is less than 5.


I will post the solution some time in the future.

-Ray