Posted by: holdenlee | May 9, 2010

B7s: April 24, 2010; May 8, 2010


4/24 Problem: Let X be a closed subset of \mathbb{R}^n. Prove that there exists a function f:\mathbb{R}^n\to\mathbb{R} that is zero on X, positive outside X, and whose partial derivatives of all orders all exist.

Solution: To be added.

5/8 Problem 1: [MS 1965/1] Let p be a prime, n\in \mathbb{N}, and S a set with p^n elements. Let P be a family of partitions into nonempty parts of sizes divisible by p such that the intersection of any two parts that occur in any of the partitions has at most 1 element in common. Find \max(P). (Scroll down for solution)

5/8 Problem 2: [MS 1965/2] Let R be a finite commutative ring. Prove that R has an identity element iff the annihilator of R is 0. (The annihilator of R is the set \{a\in R\mid ar=0 \text{ for all } r\in R\}.)

Note: Here a commutative ring does not by definition need to have an identity. Multiplication is associative and commutative (i.e. R is a commutative semigroup), distributive over addition, and R is an additive group.

Solution: The answer is

\displaystyle \frac{p^n-1}{p-1}.

(A) The bound is attainable: Think of S as the vector space \mathbb{F}_p^n. For a line W through the origin (i.e. a one-dimensional subspace of S), let the partition P_W consist of the cosets of W. The family of such partitions satisfies the given conditions: each part has p elements and every two lines can intersect at only one point. The number of such partitions is just the number of lines passing through the origin. There are p^n-1 choices for a point other than the origin for the line to pass through, which determines the line. However, each of the p-1 points beside the origin on the line give the same line, so we must divide by p-1.

(B) The bound is optimal. Let m be the number of partitions in P. Take any point O. Each partition must have exactly one set containing O; call them S_1,\ldots,S_m. Since two sets in the partition cannot intersect in more than one point, S_i-\{O\} are all disjoint. Each has at least p-1 elements since each set in a partition has to have at least p elements. The union \bigcup (S_i-\{O\}) must have at most |S-\{O\}|=p^n-1 elements, so

(p-1)m\leq p^n-1,

giving the desired bound.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: