An amusing Japanese cartoon on combinatorial explosion:
Tastefully done, I would say. The target audience consists not of this blog’s readers, but rather of their children.
Hat tip: Michael Lugo
Let’s play a game:
You build an ordered list of real numbers, and you conceal it from me. You then compute for each , and you give me the -tuple . Finally, I build a list of real numbers such that for all . Can I conclude that my list is a permutation of yours (or equal to it)?
Each ordered list of elements is an -tuple. We can also think of an ordered list of reals as a vector in , where the list’s -th element is the vector’s -th entry.
The following 3-stage diagram hopefully clarifies the essence of this -player game:
where I am player #1, and you’re player #2. The game’s three stages are:
We know that it’s always possible to build list , because if is equal to or a permutation of , then all equality conditions
will be satisfied. What we don’t know is whether any list that satisfies the equality conditions will be a permutation of . In more rigorous terms: if are permutations of one another, then it is necessary that the equalities hold. What we would like to know is whether the fact that the equalities hold is sufficient for us to conclude that 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
where is a contant, and 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:
Consider a set with elements (where all elements of are distinct). We can build ordered lists of elements by taking elements from set and using them (with no repetition) to build -tuples. With elements we can build distinct -tuples.
Let us think in terms of vectors in , where each vector represents a particular ordered list of the elements of some set with elements. If are permutations of one another, then they contain the same elements, but in a different order; consequently, for every we have
Let be an indicator function, such that if and only if are permutations of one another ( otherwise). Let be defined as
for all . We can then conclude that
The condition is necessary. Is it sufficient?! In other words, if is true, can we conclude that vectors are permutations of one another?
This is an interesting problem. Think about it!
From Harvard’s Math Department webpage, here’s today’s Putnam problem:
Take such that , and consider all subsets of elements of the set . Each subset has a smallest element. Let be the arithmetic mean of these smallest elements. Prove that .
For starters, note that there are
different subsets of elements of the set ; let’s denote these subsets by , where and . If the minimum element of subset is given by , we then have
This is all very nice, but computing 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.
In this case, we have
different subsets of the set . Since is quite small, we can quickly and easily find all the different subsets:
and the smallest element of each subset:
And finally we have
Note that .
Let’s start by considering two extreme examples of subsets of
where . The smallest element of each of these subsets is given by
and therefore we have for every . While there’s only one subset of whose smallest element is , there is more than one subset whose smallest element is . If one can compute the number of subsets whose smallest element is , then one has solved the problem.
Let’s now consider all subsets (of elements of set ) whose smallest elements are . How many are them? If the smallest element of each of these sets is , then the remaining elements of the subset must be elements of set , whose cardinality is , and therefore we have
such subsets. If we consider all subsets whose smallest elements are (where ), then the remaning elements of these subsets must be elements of set , whose cardinality is . Therefore, there are
subsets whose smallest elements are . Note that if , we have
subset only, as I had mentioned above. Since we now know how many subsets with a specific smallest element there are, we can compute by taking the weighted average
The denominator should me equal to , 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.