Category Archives: Uncategorized

Random matrices and pentagonal numbers

Here is a clever problem:

Let us fix $n$. Take at random, with uniform probability, a $n \times n$ binary matrix (call it $A$).
Let: $\gamma_n = P[\det_{Z_2}(A)=1]$.
(You can think of it as taking determinant of matrix normally and asking for a probability that it is odd number.)
Find the value of: $\gamma = \lim_{n\to\infty} \gamma_n$

(It’s not that gamma! Although, it is still related to Euler!)

I finally did it! In 2009-2010, I was helping the Codechef competitions to start.
I created more than 30 problems that were used across 12 different contests.
After, I got distracted (Master Thesis, PhD studies), and I stopped.
After those years, I finally took time to browse my local database of my problems and try and match them
with problems at Codechef. (I never uploaded them directly, it was always uploaded on spoj.pl, and then they were copied.) It was sometimes tricky, but I managed. I feel good about it, like when reconnecting after a long time with a friend. Here is the list of all of them.

What are my impressions about problem setting?
It is a perfect transition between participation in contests and work as a researcher. How so?

Asymptotics and generating functions

(Warning, equation-heavy post!)

A while ago I stumbled upon a following problem (when doing analysis of a certain distributed exploration algorithm):

We have $n$ groups of agents, each of equal size (lets say $=1$. Positions of groups are indexed: $1, 2,\ldots,n$. Groups ,,diffuse”, and they diffuse at different speeds, depending on the position of the group:
$\lambda_i = \frac{1}{i}$
(where $\lambda_i$ is the amount of agents disappearing from group being at position $i$ in one unit of time)

Whenever a group size is reduced to 0, (it will be always a first group), every other one is shifted:
$2 \to 1, 3 \to 2, \ldots, n \to (n-1)$
$[0,a_2,a_3,\ldots,a_n] \text{ into} [a_2,a_3,\ldots,a_n]$

Question: How long does it take to dissipate all the groups? (We are not interested in exact formula, just asymptotic one.)

For example, if $n=3$:
$[1,1,1] \to [0,\frac{1}{2},\frac{2}{3}]$
(1 unit of time)
$[\frac{1}{2},\frac{2}{3}] \to [0,\frac{5}{12}]$
($\frac{1}{2}$ units of time)
$[\frac{5}{12}] \to [0]$
($\frac{5}{12}$ units of time)
and the answer is $1 + \frac{1}{2} + \frac{5}{12} = \frac{23}{12}$

Catalan numbers, mirror image and walks enumeration

I always enjoyed seeing short and elegant proofs of theorems that I knew before.
I really enjoy this short proof that number of proper placing of $n$ opening and $n$ closing brackets($n$-th Catalan number) is equal to:
$C_n = \frac{1}{n+1} {2n\choose n}$.

for example, there are 2 ways to properly place 2 opening and 2 closing brackets, out of 6 total ways:
 (()), ()(), ())(, )((), )()(, ))(( 

First, we may transform the problem into one about walks on plane.
If we take (0,0) as a starting position, and assign to ‘(‘ a walk into UP-RIGHT direction, and ‘)’ a walk into DOWN-RIGHT direction, we might encode sequences of brackets. So, encoding of ((())))(() is:

Enumeration of Antimatroids, part IV

I promise to finish this topic with this post! (part 1, part 2, part 3)

We ended with a rather efficient (but still double exponential) code that gave us hope to extend the sequence a little bit further. So, what can we improve? Constant, a little, by efficient parallelisation.

Enumeration of Antimatroids, part III

Let us continue the fun we had before here.

How do we speed up the calculation? Well, we need to limit somehow the space on which we perform the search.
Very obvious way is to eliminate the symmetries. Every permutation $\pi \in S_n : \{0,1\ldots,n-1\} \to \{0,1\ldots,n-1\}$ induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:
$\sigma = (120) = \{ 0 \to 1; 1 \to 2; 2 \to 0 \}$
working on :
$F = \{ \{\}, \{0\}, \{0,1\}, \{0,2\}, \{0,1,2\} \}$
gives:
$\sigma(F) = \{ \{\}, \{1\}, \{1,2\}, \{1,0\}, \{1,2,0\} \} = \{ \{\}, \{1\}, \{1,2\}, \{0,1\}, \{0,1,2\} \}$
1, 1, 3, 22, 485, 59386, ...