Archive for the ‘Combinatorics’ Category

Back around 2000, I found a copy of Neal Koblitz’s text A Course in Number Theory and Cryptography at the Borders bookstore in Bangor, Maine.  I only worked my way through the first chapter, but was fascinated with these ideas.  I found Professor Koblitz’s website which, at the time, had a tutorial section on finite fields and elliptic curve cryptography (this may have been on the Certicom website, I can’t remember now).  I moved on to other forms of digital cryptography, like the Diffie-Hellman Key Exchange and RSA Cryptosystem, but always appreciated Prof. Koblitz’s work.  Recently, we dressed up for Halloween as a number and I chose to be the number 4.  As part of my costume, I drew the addition table for the Galois Field of order 4GF(4)=^{GF(2)[x]}/_{x^2+x+1}, and did a lot of thinking that week about the element a, which was defined as the root of the equation 0=x^2+x+1 in GF(2)

This past week, I decided to look at the mathematics behind Bitcoin and blockchain, and lo and behold, it is Finite Fields and Elliptic Curve Cryptography – I don’t know why it took me so long to find this out, but now I’m excited about these topics.  I am a little skeptical about the current “Bitcoin bubble.”  I’m not sure that these valuations are sustainable, but from everything I’ve read, the blockchain algorithm behind Bitcoin is revolutionary and the mathematics is “supercool.”

Here’s a graph of the equation y=x+1 in GF(2).


Read Full Post »

Yesterday in Pre-Calculus class we were discussing combinatorics and came across a series of questions on how many ways can a best 2 out of 3 sets tennis match be won and how many ways can a best 3 out of 5 tennis match be won.

For a 2 out of 3 scenario there are six possibilities (AA, ABA, BAA, BB, BAB, ABB) and for the 3 out of 5 scenario there are 20 possibilities (AAA, BAAA, ABAA, AABA, BBAAA, BABAA, BAABA, ABBAA, ABABA, AABBA and ten more in which B wins).

The question then came up of how to generalize these results.  The way I approached this was to consider how many ways one of the players could win and then double the answer to include the scenarios in which the other won.

One of the issues in this type of problem is that once the winner has won the required number of games the match ends, so that a best 2 out of 3 match could never end AAB, for instance.  Another issue is that each of the possibilities of winning in a different number of sets should be considered separately.  That is, winning in the minimum number of sets, then winning after having lost one set and so forth.

Taking all of these issues into account for a competition in which the winner must win \frac{n+1}{2} out of n leads to a general formula of 2*\displaystyle \sum_{k=0}^{\frac{n-1}{2}}{_\frac{n+2k-1}{2}}C_{k}.

Or – if the winner must win g out of 2g-1 then the formula would be 2*\displaystyle \sum_{k=0}^{g-1}{_{g+k-1}}C_{k}.

Read Full Post »


We were covering some elementary combinatorics in the Pre-Calculus course this past week and were discussing some problems from VK Balakrishnan’s Discrete Mathematics textbook.  I took a Discrete Math course at University of Maine in 2000 from Balakrishnan and really enjoyed the class.

I needed to make a quiz question for the Pre-Calculus class and tried to remember some of the more interesting ways Balakrishnan had constructed his problems and came up with this one:

Seven people (A, B, C, D, E, F, G) want to ride into Portland but the car will only hold four.  Person “A” owns the car and will always be driving.  People “F” and “G” don’t get along and won’t ride together.  If it makes no difference where in the car people sit, how many ways are there for four people to ride into Portland together?


Read Full Post »