Puzzler - Hand Shakes

My wife and I attend a party with four other couples. When we arrive there’s a certain amount of hand-shaking, but no one shakes his own hand and no husband shakes his wife’s hand. I ask the nine other guests how many hands each shook, and I get nine different answers. How many hands did my wife shake?

Solution: There must be exactly one person who shook 0, 1, 2, ..., 8 hands. The person who shook 8 hands shook everyone's except his/her spouses'. So everyone shook atleast one hand except for the spouse, who therefore must have shaken 0 hands. So 8 is paired with 0. Similarly, 7 is paired with 1, 6 with 2, 5 with 3, and 4 is left alone. The only person who didn't have a spouse in the people you asked is your wife, so your wife shook 4 hands.

___________________________________________________________________________________

Discrete Fourier Transform

Suppose we have to multiply two degree polynomials together, $A(x)B(x) = C(x)$ where $A$ and $B$ are given, $C$ is unknown. Let $A,B,C$ be of degree $r,s,r+s$ respectively, and let $n$ be the smallest power of 2 larger than $r+s$.  \[    A(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1}     \] \[    B(x) = b_0 + b_1x + b_2x^2 + ... + b_{n-1}x^{n-1}     \] \[    C(x) = c_0 + c_1x + c_2x^2 + ... + c_{2n-2}x^{2n-2}     \]
Note that the coefficients indexed larger than the respective degrees are simply zero. Then we can find our coefficients of $C$ in $\mathcal{O}(n^2)$ by multiplying the coefficients of $A$ and $B$ together in the convoluted sum \[    c_k = \sum_{j=0}^{k}a_j b_{k-j}    \]
But $n=2^{20}$ and $\mathcal{O}(n^2)$ is too costly, so we need a better method. Through the use of the FFT we can find coefficients $c_k$ in $\mathcal{O}(n\log n)$ time by

1.     (FFT) Evaluate $A$ and $B$ at $n$th roots of unity $\omega^k, \;\;\;\; k=0,...,n-1$
2.      Find $C(\omega^k) = A(\omega^k) B(\omega^k)$  
3.      (iFFT) Find $C$ via polynomial interpolation  

Step (1) Suppose we write $A(x) = A_0(x^2) + xA_1(x^2)$ where \[   A_0(x) = a_0 + a_2x + a_4x^2 + ... + a_{n-2}x^{n/2-1} \] \[    A_1(x) = a_1 + a_3x + a_5x^2 + ... + a_{n-1}x^{n/2-1}  \]
To evaluate $A$ at the $n$th roots of unity, we need to evaluate $A_0$ and $A_1$ at the square of each of the roots. But this is the same as evaluating the $(n/2)$th roots of unity at two polynomials of degree $n/2-1$. We immediately get a recursive algorithm (Fast Fourier Transform) with complexity $T(n) = 2T(n/2) + 2n = \mathcal{O}(n\log n).$ We can easily generalize this to work for $n$ as a power of any prime by splitting $A$ into more parts (or any number provided you have its prime factorization).

Step (2) We evaluate $C(\omega^k )$ in $O(n)$ operations.

Step (3) We have formed a linear system $Mc^* = c$, where $M$ is the matrix $(\omega^{kj})$, $c^*$ is the vector of values $ c_k $, and $c$ is the vector of values $C(\omega^{km})$. $M$ is a Vandermonde matrix, so it has an inverse. Thus, we can find $c^{*}$ by applying $M^{-1}$ to both sides, $c^* = M^{-1} c$. It turns out $M^{-1} = (1/n (\omega^{-ij}))$ and applying this matrix to $c$ is the same as step 1, namely the inverse Fourier transform.

Python Code




    from cmath import exp, pi 

    def FFT(X):
       
        n = len(X)
        w = exp(-2*pi*1j/n)

        if n > 1
            X = FFT(X[::2]) + FFT(X[1::2])

            for k in xrange(n/2):

                xk = X[k]
                X[k] = xk + w**k*X[k+n/2]
                X[k+n/2] = xk - w**k*X[k+n/2]

        return X


___________________________________________________________________________________

Gravity Toy

Recently found this fun program on the web that lets you create our solar system in 2D. Pretty fun to play with.

___________________________________________________________________________________

Lexicographic Index of Subsets

Suppose we have a set of $n$ items labelled $\{1,2,...,n\}$. We want to enumerate the subsets of $s$ items somehow. A natural way to do this is to use a lexicographic ordering of the sorted sets. So for example if $n=10$ and $s=4$, we would get the following assignments:

$\{1, 2, 3, 4 \} : 1$

$\{1, 2, 3, 5 \} : 2$

$\{1, 2, 3, 6 \} : 3$

...

$\{7, 8, 9, 10 \} : {10 \choose 4 }$

Solution 1 - Counting Above

The best way to show this is by example. The lexicographic index is the total number of subsets minus the number of subsets lexically larger. Suppose $n = 10$ and $s=4$ and our subset $u = \{2,4,5,9\}$. The subsets that are lexically larger than $u$ look like the following:

$ \#\{ > 2, ... \} = {8 \choose 4} $

$ \#\{ 2, >4, ... \} = {6 \choose 3} $

$ \#\{ 2, 4, >5, ... \} = {5 \choose 2} $

$ \#\{ 2, 4, 5, >9 \} = {1 \choose 1} $

It is easy to see the pattern and generalize. Our formula is then

\[ enum(u) = {n \choose s} - \sum_{j=1}^{s}{n-u_j \choose s-j+1} \]

Solution 2 - Counting Below

The lexicographic index is one plus the number of subsets lexically smaller. Suppose $n = 10$ and $s=4$ and our subset $u = \{2,4,5,9\}$. The subsets that are lexically smaller look like the following:

$ \# \{< 2, ... \} = \# \{ ... \} - \# \{ \geq 2, ... \} = { 10 \choose 4} - {9 \choose 4} $

$ \# \{2, < 4, ... \} = \# \{ 2, ... \} - \# \{ 2, \geq 4, ... \} = { 8 \choose 3} - {7 \choose 3} $

$\# \{2, 4, <5, ...\} = \# \{ 2, 4, ... \} - \# \{ 2, 4, \geq5, ... \} = { 6 \choose 2} - {6 \choose 2}$

$\# \{2, 4, 5, <9\} = \# \{ 2, 4, 5, ... \} - \# \{ 2,4,5, \geq 9 \} = { 5 \choose 1} - {2 \choose 1} $

It is easy to see the pattern and generalize. Defining $u_0 = 0$, our formula is then 

\[ enum(u) = 1 + \sum_{j=1}^{s} \left[ {n-u_{j-1} \choose s-j+1} - {n-u_j+1 \choose s-j+1} \right] \]

If you telescope this sum, you end up with formula given by Solution 1.

Exercise: How can we calculate the inverse? Given a number, what subset does it correspond to?

___________________________________________________________________________________