Archive for the ‘Combinatorics’ Category

Playing with Permutations

July 24, 2008

Let’s play a game:

You build an ordered list y = (y_1, y_2, \ldots, y_n) of n real numbers, and you conceal it from me. You then compute c_k = \sum_{i=1}^n y_i^k for each k \in \{1,2,\ldots,n\}, and you give me the n-tuple c = (c_1, c_2, \ldots, c_n). Finally, I build a list x = (x_1, x_2, \ldots, x_n) of n real numbers such that \sum_{i=1}^n x_i^k = c_k for all k \in \{1,2,\ldots,n\}. Can I conclude that my list is a permutation of yours (or equal to it)?

__________

Each ordered list of n elements is an n-tuple. We can also think of an ordered list of n reals as a vector in \mathbb{R}^n, where the list’s i-th element is the vector’s i-th entry.

The following 3-stage diagram hopefully clarifies the essence of this 2-player game:

where I am player #1, and you’re player #2. The game’s three stages are:

  1. player #2 builds an ordered list y \in \mathbb{R}^n, but player #1 doesn’t have access to it.
  2. player #2 gives player #1 the n “measurements” c = (c_1, c_2, \ldots, c_n), where c_k = \sum_{i=1}^n y_i^k.
  3. player #1 builds ordered list x \in \mathbb{R}^n from c = (c_1, c_2, \ldots, c_n) such that \sum_{i=1}^n x_i^k = c_k for all k \in \{1,2,\ldots,n\}.

We know that it’s always possible to build list x, because if x is equal to y or a permutation of y, then all n equality conditions

\begin{array}{rl} \displaystyle\sum_{i=1}^n x_i &= c_1\\ \displaystyle\sum_{i=1}^n x_i^2 &= c_2\\ \vdots\\ \displaystyle\sum_{i=1}^n x_i^n &= c_n\\\end{array}

will be satisfied. What we don’t know is whether any list x that satisfies the equality conditions will be a permutation of y. In more rigorous terms: if x, y are permutations of one another, then it is necessary that the n equalities hold. What we would like to know is whether the fact that the n equalities hold is sufficient for us to conclude that x, y are permutation of one another.

But how can player #1 build the desired ordered list? A possibility would be for player #1 to solve the following system on polynomial equations in variables x_1, x_2, \ldots, x_n

\begin{array}{rl} x_1 + x_2 + \ldots + x_n &= c_1\\ x_1^2 + x_2^2 + \ldots + x_n^2 &= c_2\\ \vdots\\ x_1^n + x_2^n + \ldots + x_n^n &= c_n\\\end{array}

where c is a contant, and x is a variable.

The game I propose on this post stems from two closely related problems I have been thinking of since January 2008. I have written a few posts on these problems already:

Tags:
Posted in Combinatorics | 9 Comments »

Thinking about permutations

January 18, 2008

Consider a set S with |S|=n elements (where all elements of S are distinct). We can build ordered lists of n elements by taking elements from set S and using them (with no repetition) to build n-tuples. With n elements we can build n! distinct n-tuples.

Let us think in terms of vectors in \mathbb{R}^n, where each vector represents a particular ordered list of the elements of some set with n elements. If x, y \in \mathbb{R}^n are permutations of one another, then they contain the same elements, but in a different order; consequently, for every p \in \mathbb{N} we have

\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n y_i^p.

Let I: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \{0,1\} be an indicator function, such that I(x,y) = 1 if and only if x,y are permutations of one another (I(x,y)=0 otherwise). Let g_p: \mathbb{R}^n \rightarrow \mathbb{R} be defined as

g_p(z) = \displaystyle\sum_{i=1}^n z_i^p,

for all p \in \mathbb{N}. We can then conclude that

I(x,y) = 1 \Rightarrow g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}.

The condition g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N} is necessary. Is it sufficient?! In other words, if g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N} is true, can we conclude that vectors x,y are permutations of one another?

This is an interesting problem. Think about it!

Update (Jan. 25, 2008): this post was featured on the 25th edition (Silver Jubilee) of the Carnival of Mathematics.

Tags:,
Posted in Combinatorics, Mathematics, Puzzles | 12 Comments »

Today’s Putnam problem – Dec. 01, 2007

December 1, 2007

From Harvard’s Math Department webpage, here’s today’s Putnam problem:

Take r such that 1 \leq r \leq n, and consider all subsets of r elements of the set \{1, 2, \ldots, n\}. Each subset has a smallest element. Let F(n,r) be the arithmetic mean of these smallest elements. Prove that F(n,r) = \frac{n+1}{r+1}.

For starters, note that there are

m = \displaystyle\binom{n}{r} = \frac{n!}{(n-r)! r!}

different subsets of r elements of the set \{1, 2, \ldots, n\}; let’s denote these subsets by S_i, where i \in \{1, 2, \ldots, m\} and |S_i| = r. If the minimum element of subset S_i is given by \min(S_i), we then have

F(n,r) = \displaystyle\frac{1}{m} \sum_{i=1}^m \min(S_i).

This is all very nice, but computing \min(S_i) is not that straightforward. The best way to make sure that one understands the problem at hand is to consider an example, and that’s what I will do now.

Example: n=4 and r=2

In this case, we have

m = \displaystyle\binom{4}{2} = \frac{4!}{2! 2!} = 6

different subsets of the set \{1, 2, 3, 4\}. Since m=6 is quite small, we can quickly and easily find all the different subsets:

S_1 = \{1, 2\}

S_2 = \{1, 3\}

S_3 = \{1, 4\}

S_4 = \{2, 3\}

S_5 = \{2, 4\}

S_6 = \{3, 4\}

and the smallest element of each subset:

\min(S_1) = 1

\min(S_2) = 1

\min(S_3) = 1

\min(S_4) = 2

\min(S_5) = 2

\min(S_6) = 3.

And finally we have

F(4,2) = \displaystyle\frac{\left(1 +1 +1 + 2 +2 + 3\right)}{6} = \displaystyle\frac{10}{6} = \displaystyle\frac{5}{3}.

Note that F(4,2) = \displaystyle\frac{4+1}{2+1}.

My Solution:

Let’s start by considering two extreme examples of subsets of \{1, 2, \ldots, n\}

S_1 = \{1, 2, \ldots, r\}

S_m = \{n, n-1, \ldots, n - (r-1)\},

where |S_1| = |S_m| = r. The smallest element of each of these subsets is given by

\min(S_1) = 1

\min(S_m) = n - (r-1) = n - r + 1

and therefore we have 1 \leq \min(S_i) \leq n -r + 1 for every i \in \{1, 2, \ldots, m\}. While there’s only one subset of \{1, 2, \ldots, n\} whose smallest element is n - r + 1, there is more than one subset whose smallest element is 1. If one can compute the number of subsets whose smallest element is k \in \{1, 2, \ldots, n - r + 1\}, then one has solved the problem.

Let’s now consider all subsets (of r elements of set \{1, 2, \ldots, n\}) whose smallest elements are 1. How many are them? If the smallest element of each of these sets is 1, then the remaining r-1 elements of the subset must be elements of set \{2, 3, \ldots, n\}, whose cardinality is n-1, and therefore we have

\displaystyle \binom{n-1}{r-1}

such subsets. If we consider all subsets whose smallest elements are k (where k \in \{1, 2, \ldots, n-r+1\}), then the remaning r-1 elements of these subsets must be elements of set \{k+1, k+2, \ldots, n\}, whose cardinality is n-k. Therefore, there are

\displaystyle \binom{n-k}{r-1}

subsets whose smallest elements are k. Note that if k = n-r+1, we have

\displaystyle \binom{n-(n-r+1)}{r-1} = \binom{r-1}{r-1} = 1

subset only, as I had mentioned above. Since we now know how many subsets with a specific smallest element there are, we can compute F(n, r) by taking the weighted average

\displaystyle F(n, r) = \frac{\displaystyle\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}}{\displaystyle\sum_{k=1}^{n-r+1} \binom{n-k}{r-1}}.

The denominator should me equal to m = \binom{n}{r}, and I have proved that already (I am not going to type the proof here because it’s a bit cumbersome). However, I can’t do much with the numerator. I am stuck. If you have any ideas, let me know.

Tags:,
Posted in Combinatorics, Puzzles | 2 Comments »

Follow

Get every new post delivered to your Inbox.

Join 47 other followers