### Finding all paths

Consider the following problem: You are given a two-dimensional array of integers and you are allowed to place a chess king on one of the arrays. The king can move in any of the eight directions at a time and you want to know how many (simple) paths this king can go that satisfy that the corresponding numbers are strictly increasing and that end in an even number.

As an example, consider the following array:

 0 1 2 3 

In this array, we have the paths [0], [0 1 2], [0 2], [1 2], [2] (strictly increasing and ending in an even number).
Read the rest of this entry »

### A hiring problem

Imagine the following scenario: You want to hire a new employee, and of course you want to take the best candidate. Therefore, you conduct a series of interviews with the candidates one after another. We now impose the following restriction: You have to tell the candidate whether he or she is good enough or not (i.e. if you want to hire him or her) directly after the interview. That is, once you told a candidate you hire her or him, the interview process is over and you do not interview any more candidates. And once you told a candidate you won’t hire her or him, this candidate is away and can not be hired anymore. We now consider a strategy to solve this problem: We hire a candidate if he or she is better than the expected value of the best of all following candidates. If there are no more candidates, we have to hire the last candidate.

### Vim LatexSuite missing features

Since Emacs needs quite an amount of time to start, I decided to give vim a try and am quite happy with it. However, I missed a feature that I appreciated since I came to know it in AucTeX: Showing and browsing the table of contents. So, I implemented a basic table of contents myself.
Read the rest of this entry »

### An interesting bijection

I came across the following identity recently: $\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}$. This can be proved in various ways. Here, I will describe a “combinatorial proof”.
Read the rest of this entry »

### Addendum: Encoding tuples with numbers

I described how to encode tuples of natural numbers into natural numbers. Now, I wrote (hacked) a small piece in Haskell to try it in practice.
Read the rest of this entry »

### Intermezzo: A brainf***-interpreter

Here’s a 290-characters interpreter for the brainf*** programming language I wrote.
Read the rest of this entry »

### A nice property of primes

A while ago, a friend of mine told me that he once knew a number with the following property: “You can prepend any number before that number and will always obtain a prime number.”

Of course, he was just kidding: Such a number can’t exist, because a number is divisible by 3 if and only if its digit sum is divisible by 3. So, it is no problem to find a number to prepend such the digit sum of the resulting number is divisible by 3. That implies that the resulting number is not a prime.

However, it’s possible to prove a similar theorem…
Read the rest of this entry »

### A very nice proof of existence

We consider a propositional logic formula in conjunctive normal form, containing $2^k-1$ clauses, where each clause has exactly k (distinct) variables.

We prove that this formula is satisfiable.
Read the rest of this entry »

### A little thougt about how to encode tuples of natural numbers with prime numbers

I have always been interested in how to encode certain things into simple natural numbers. This post shows a way to encode sets and tuples of natural numbers, that I personally find quite nice.
Read the rest of this entry »

### Messing with skolemization

In predicate logic, skolemization is a central method to manipulate logic formulas. Since we had to do some homework on those formulas, and I always mixed up the parentheses, I decided to have it done by the computer.
Read the rest of this entry »