Beni Bogoşel's blog

Putnam 2014 Problems

December 8, 2014 beni22sof Leave a comment

A1. Prove that every nonzero coefficient of the Taylor series of ${(1-x+x^2)e^x}$ about ${x=0}$ is a rational number whose numerator (in lowest terms) is either ${1}$ or a prime number.

A2. Let ${A}$ be the ${n\times n}$ matrix whose entry in the ${i}$ -th row and ${j}$ -th column is

$\displaystyle \frac1{\min(i,j)}$

for ${1\le i,j\le n.}$ Compute ${\det(A).}$

A3. Let ${a_0=5/2}$ and ${a_k=a_{k-1}^2-2}$ for ${k\ge 1.}$ Compute

$\displaystyle \prod_{k=0}^{\infty}\left(1-\frac1{a_k}\right)$

in closed form.

A4. Suppose ${X}$ is a random variable that takes on only nonnegative integer values, with ${E[X]=1,}$ ${E[X^2]=2,}$ and ${E[X^3]=5.}$ (Here ${E[Y]}$ denotes the expectation of the random variable ${Y.}$ ) Determine the smallest possible value of the probability of the event ${X=0.}$

A5. Let ${P_n(x)=1+2x+3x^2+\cdots+nx^{n-1}.}$ Prove that the polynomials ${P_j(x)}$ and ${P_k(x)}$ are relatively prime for all positive integers ${j}$ and ${k}$ with ${j\ne k.}$

A6. Let ${n}$ be a positive integer. What is the largest ${k}$ for which there exist ${n\times n}$ matrices ${M_1,\dots,M_k}$ and ${N_1,\dots,N_k}$ with real entries such that for all ${i}$ and ${j,}$ the matrix product ${M_iN_j}$ has a zero entry somewhere on its diagonal if and only if ${i\ne j?}$

B1. A base ${1}$ over-expansion of a positive integer ${N}$ is an expression of the form ${N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0}$ with ${d_k\ne 0}$ and ${d_i\in\{0,1,2,\dots,10\}}$ for all ${i.}$ For instance, the integer ${N=10}$ has two base 10 over-expansions: ${10=10\cdot 10^0}$ and the usual base 10 expansion ${10=1\cdot 10^1+0\cdot 10^0.}$ Which positive integers have a unique base 10 over-expansion?

B2. Suppose that ${f}$ is a function on the interval ${[1,3]}$ such that ${-1\le f(x)\le 1}$ for all ${x}$ and $\int_1^3f(x)\,dx=0.$ How large can ${\displaystyle\int_1^3\frac{f(x)}x\,dx}$ be?

B3. Let ${A}$ be an ${m\times n}$ matrix with rational entries. Suppose that there are at least ${m+n}$ distinct prime numbers among the absolute values of the entries of ${A.}$ Show that the rank of ${A}$ is at least ${2.}$

B4. Show that for each positive integer ${n,}$ all the roots of the polynomial

$\displaystyle \sum_{k=0}^n 2^{k(n-k)}x^k$

are real numbers.

B5. In the 75th Annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible ${n\times n}$ matrices with entries in the field ${\mathbb{Z}/p\mathbb{Z}}$ of integers modulo ${p,}$ where ${n}$ is a fixed positive integer and ${p}$ is a fixed prime number. The rules of the game are:

(1) A player cannot choose an element that has been chosen by either player on any previous turn.

(2) A player can only choose an element that commutes with all previously chosen elements.

(3) A player who cannot choose an element on his/her turn loses the game.

Patniss takes the first turn. Which player has a winning strategy?

B6. Let ${f:[0,1]\rightarrow\mathbb{R}}$ be a function for which there exists a constant ${K>0}$ such that ${|f(x)-f(y)|\le K|x-y|}$ for all ${x,y\in [0,1].}$ Suppose also that for each rational number ${r\in [0,1],}$ there exist integers ${a}$ and ${b}$ such that ${f(r)=a+br.}$ Prove that there exist finitely many intervals ${I_1,\dots,I_n}$ such that ${f}$ is a linear function on each ${I_i}$ and ${[0,1]=\bigcup_{i=1}^nI_i.}$

Categories: Olympiad Tags: olympiad, putnam

Five points on a circle, centroids and perpendiculars

December 5, 2014 beni22sof Leave a comment

Suppose you have ${5}$ different points on a circle. For each triangle formed by three of these points, consider the line passing through its centroid, perpendicular to the line determined by the other two.

Variations on Fatou’s Lemma – Part 2

November 29, 2014 beni22sof Leave a comment

As we have seen in a previous post, Fatou’s lemma is a result of measure theory, which is strong for the simplicity of its hypotheses. There are cases in which we would like to study the convergence or lower semicontinuity for integrals of the type $\int_\Omega f_ng_n$ where ${f_n}$ converges pointwise to ${f}$ and ${g_n}$ converges to ${g}$ in some fashion, but not pointwise. For example, we could have that ${g_n}$ converges to ${g}$ in ${L^1}$ . In this case we could write the integral $\int_\Omega f_ng_n$ as $\int_\Omega f d\mu_n$ where ${\mu_n}$ is the measure defined by ${\mu_n(A) = \displaystyle\int_A g_n}$ . All measures considered in this post will be positive measures.

Certain hypotheses on the measures ${\mu_n,\mu}$ allow us to find a result similar to Fatou’s Lemma for varying measures. In the following, we define a type of convergence for the measures ${\mu_n,\mu}$ , named setwise convergence, which will allow us to prove the lower semicontinuity result. We say that ${\mu_n}$ converges setwise to ${\mu}$ if ${\mu_n(A) \rightarrow \mu(A)}$ for every measurable set ${A}$ . The following proof is taken from Royden, H.L., Real Analysis, Chapter 11, Section 4. It is very similar to the proof of Fatou’s lemma given here.

Theorem A. Let ${\mu_n}$ be a sequence of measures defined on ${\Omega}$ which converges setwise to a measure ${\mu}$ and ${(f_n)}$ a sequence of nonnegative measurable functions which converge pointwise (or almost everywhere in ${\Omega}$ ) to the function ${f}$ . Then

$\displaystyle \int_\Omega f d\mu \leq \liminf_{n \rightarrow \infty} \int_\Omega f_n d\mu_n.$

Variations on Fatou’s Lemma – Part 1

November 13, 2014 beni22sof 1 comment

One of the most basic and powerful results of measure theory is Fatou’s Lemma. It provides information on the convergence of the integrals of functions which converge pointwise. The power of this lemma is the simplicity of its hypothesis. One of its interpretations is that the functional which to a positive function associates its integral is lower semicontinuous with respect to the pointwise convergence. Among other things, it allows us to prove the monotone convergence theorem, or Lebesgue’s dominated convergence theorem in just one line.

Fatou’s Lemma Suppose ${(X,\mathcal{M},\mu)}$ is a measure space and ${f_n : X \rightarrow [0,\infty]}$ is a sequence of integrable functions converging pointwise ${\mu}$ almost everywhere to ${f}$ . Then ${f}$ is measurable and

$\displaystyle \int_X f d\mu \leq \liminf_{n \rightarrow \infty} \int_X f_n d\mu.$

Proof: One of the classical proofs of this result goes as follows. Using the definition

$\displaystyle \int_X fd\mu = \sup\{ \int_X \varphi : \varphi \leq f,\ \varphi \text{ is a simple function} \}$

we note that it is enough to prove that

$\displaystyle \int_X \varphi d\mu \leq \liminf_{n \rightarrow \infty} \int_X f_n d\mu,$

for every simple function ${\varphi \leq f}$ .

Pick ${\varphi\leq f}$ and ${\varepsilon>0}$ . Suppose ${\int_X \varphi d\mu<\infty}$ . Denote ${E_n = \{x : (1-\varepsilon)\varphi \leq f_k(x),\ \text{ for every }k\geq n\}}$ . Note that ${E_n \subset E_{n+1}}$ and ${X = \bigcup_{n \geq 1} E_n}$ . If we denote ${E}$ the support of ${\varphi}$ , we may choose ${n_0}$ such that for every ${n \geq n_0}$ we have ${\mu(E\setminus E_n)<\varepsilon}$ . Thus

$\displaystyle \int_X f_k d\mu_k \geq \int_{E_k} f_k d\mu \geq (1-\varepsilon)\int_{E_k}\varphi d \mu \geq (1-\varepsilon) \int_X \varphi d\mu - (1-\varepsilon) \int_{E\setminus E_k} \varphi d\mu.$

Since ${\varphi}$ is bounded above by a constant ${M<\infty}$ and ${\mu(E\setminus E_k)<\varepsilon}$ , we have

$\displaystyle \int_X f_k d\mu \geq (1-\varepsilon) \int_E \varphi d\mu -(1-\varepsilon)\varepsilon M.$

Taking ${k \rightarrow \infty}$ we have

$\displaystyle \liminf_{k \rightarrow \infty} \int_X f_k d\mu \geq (1-\varepsilon) \int_E \varphi d\mu -(1-\varepsilon)\varepsilon M.$

Take ${\varepsilon \rightarrow 0}$ and then supremum over ${\varphi\leq f}$ to finish the proof. \hfill ${\square}$

Monotone convergence Suppose that ${f_k}$ is a sequence of function defined on ${X}$ such that

$\displaystyle 0 \leq f_k(x) \leq f_{k+1}(x),$

for every ${k \geq 1}$ and ${x \in X}$ . Denote ${f(x) = \lim_{k \rightarrow \infty} f_k(x)}$ . Then ${f}$ is measurable and

$\displaystyle \int_X fd\mu = \lim_{n \rightarrow \infty} \int_X f_n d\mu.$

Proof: The ${\limsup}$ comes from the monotonicity, while the ${\liminf}$ is just Fatou’s Lemma.

Dominated convergence Suppose ${f_k}$ is a sequence of measurable functions defined on ${X}$ which converges almost everywhere to ${f}$ . Moreover, suppose there exists an integrable function ${g}$ such that ${|f_n|\leq g}$ for every ${n}$ . Then

$\displaystyle \int_X fd\mu = \lim_{n \rightarrow \infty} \int_X f_n d\mu.$

Proof: Apply Fatou’s lemma to ${g_n = 2g-|f_n-f|\geq 0}$ .

It is straightforward to see that the positivity condition can be replaced with a domination from below. If ${f_n \geq -g}$ and ${g}$ is integrable, then apply Fatou’s lemma to ${f_n+g}$ to deduce that the conclusion still holds for ${(f_n)}$ . One may ask what happens with the ${\limsup}$ part. If ${ f_n \leq g}$ with ${g}$ integrable, then the reverse Fatou Lemma works. To see this, apply Fatou’s lemma to ${g-f_n \geq 0}$ .

Of course, every one of the few hypotheses made for the Fatou’s lemma are essential. If we allow negative functions, then ${f_n = -n \chi_{[0,1/n]}}$ is a counterexample. ${f_n}$ converges to zero almost everywhere, while the integrals of ${f_n}$ are equal to ${-1}$ . The inequality can be strict. Consider the similar functions ${f_n = n \chi_{[0,1/n]}}$ .

Seeing that the hypotheses needed for Fatou lemma to hold are simple enough, we may try and see which generalizations of Fatou lemma hold? One interesting direction is to consider not only variable functions, but also variable measures. This will be treated in a future post.

Categories: Measure Theory, Real Analysis Tags: Analysis, convergence, fatou, integral, semicontinuity

Problems of the Miklos Schweitzer Competition 2014

November 10, 2014 beni22sof 3 comments

Problem 1. Let ${n}$ be a positive integer. Let ${\mathcal{F}}$ be a familiy of sets that contains more than half of all subsets of an ${n}$ -element set ${X}$ . Prove that from ${\mathcal{F}}$ we can select ${\lceil \log_2 n\rceil+1 }$ sets that form a separating family of ${X}$ , i.e., for any two distinct elements of ${X}$ there is a selected set containing exactly one of the two elements.

Problem 2. let ${k \geq 1}$ and let ${I_1,...,I_k}$ be non-degenerate subintervals of the interval ${[0,1]}$ . Prove that

$\displaystyle \sum \frac{1}{|I_i \cup I_j|} \geq k^2,$

where the summation is over all pairs of indices ${(i,j)}$ such that ${I_i}$ and ${I_j}$ are not disjoint.

Problem 3. We have ${4n+5}$ points in the plane, no three of them collinear. The points are colored with two colors. Prove that from the points we can form ${n}$ empty triangles (they have no colored points in their interiors) with pairwise disjoint interiors, such that all points occuring as vertices of the ${n}$ triangles have the same color.

Problem 4. For a positive integer ${n}$ , let ${f(n)}$ be the number of sequences ${a_1,...,a_k}$ of positive integers such that ${a_i \geq 2}$ and ${a_1...a_k = n}$ for ${k \geq 1}$ . We make the convention ${f(1)=1}$ . Let ${\alpha}$ be the unique real number greater than ${1}$ such that ${\sum_{n=1}^\infty n^{-\alpha}=2}$ . Prove that

(i) ${ \sum_{ k = 1}^n f(k)= O(n^\alpha)}$ .
(ii) There exists no number ${\beta<\alpha}$ such that ${f(n)=O(n^\beta)}$ .

Problem 5. Let ${\alpha}$ be a non-real algebraic integer of degree two, and let ${P}$ be the set of irreducible elements of the ring ${\Bbb{Z}[\alpha]}$ . Prove that

$\displaystyle \sum_{ p \in P} \frac{1}{|p|^2} = \infty.$

Problem 6. Let ${\rho : G \rightarrow GL(V)}$ be a representation of a finite ${p}$ -group ${G}$ over a field of characteristic ${p}$ . Prove that if the restriction of the linear map ${\sum_{ g \in G} \rho(g)}$ to a finite dimensional subspace ${W}$ of ${V}$ is injective, then the subspace spanned by the subspaces ${\rho(g)W}$ ( ${g \in G}$ ) is the direct sum of these subspaces.

Problem 7. Lef ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a continuous function and let ${g: \Bbb{R} \rightarrow \Bbb{R}}$ be arbitrary. Suppose that the Minkowski sum of the graph of ${f}$ and the graph of ${g}$ (i.e. the set ${\{(x+y,f(x)+g(y) : x,y \in \Bbb{R}\}}$ has Lebesgue measure zero. Does it follow then that the function ${f}$ is of the form ${f(x)=ax+b}$ , with suitable constants ${a,b \in \Bbb{R}}$ ?

Problem 8. Let ${n \geq 1}$ be a fixed integer. Calculate the distance

$\displaystyle \inf_{p,f} \max_{0 \leq x \leq 1} |f(x)-p(x)|,$

where ${p}$ runs over polynomials of degree less than ${n}$ with real coefficients and ${f}$ runs over functions of the form

$\displaystyle f(x) = \sum_{ k = n}^\infty c_kx^k$

defined on the closed interval ${[0,1]}$ , where ${c_k\geq 0}$ and ${\sum_{k=n}^\infty c_k =1}$ .

Problem 9. Let ${\rho : \Bbb{R}^n \rightarrow \Bbb{R},\ \rho(x)=e^{-\|x\|^2}}$ , and let ${K \subset \Bbb{R}^n}$ be a convex body, i.e. a compact convex set with nonempty interior. Define the barycenter ${s_K}$ of the body ${K}$ with respect to the weight function ${\rho}$ by the usual formula

$\displaystyle s_K = \frac{\int_K \rho(x) x dx}{\int_K \rho(x)dx}.$

Prove that the translates of the body ${K}$ have pairwise distinct barycenters with respect to ${\rho}$ .

Problem 10. To each vertex of a given triangulation of the two dimensional sphere, we assign a convex subset of the plane. Assume that the three convex sets corresponding to the three vertices of any two dimensional face of the triangulation have at least one point in common. Show that there exist four vertices such that the corresponding convex sets have at least one point in common.

Problem 11. Let ${U}$ be a random variable that is uniformly distributed on the interval ${[0,1]}$ , and let

$\displaystyle S_n = 2\sum_{k=1}^n \sin(2kU\pi).$

Show that, as ${n \rightarrow \infty}$ , the limit distribution of ${S_n}$ is the Cauchy distribution with density function ${f(x) =\frac{1}{\pi(1+x^2)}}$ .

Source: http://www.bolyai.hu/SCH_angol_2014.pdf

Categories: Algebra, Analysis, Olympiad, Probability, Problem Solving Tags: Algebra, Analysis, Combinatorics, Geometry, miklos schweitzer, Probability

Monotonic bijection from naturals to pairs of natural numbers

October 23, 2014 beni22sof Leave a comment

This is a cute problem I found this evening.

Suppose ${\phi : \Bbb{N}^* \rightarrow \Bbb{N}^*\times \Bbb{N}^*}$ is a bijection such that if ${\phi(k) = (i,j),\ \phi(k')=(i',j')}$ and ${k \leq k'}$ , then ${ij \leq i'j'}$ .

Prove that if ${k = \phi(i,j)}$ then ${k \geq ij}$ .

Proof: The trick is to divide the pairs of positive integers into families with the same product.

$\displaystyle \begin{matrix} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & (1,6) & \cdots \\ & (2,1) & (3,1) & (2,2) & (5,1) & (2,3) & \cdots \\ & & &( 4,1) & & (3,2) & \cdots \\ & & & & & (6,1) & \cdots \end{matrix}$

Note that the ${M}$ -th column contains as many elements as the number of divisors of ${M}$ . Now we just just use a simple observation. Let ${\phi(k)=(i,j)}$ be on the ${M}$ -th column (i.e. ${ij = M}$ ). If ${n \geq 1}$ then ${\phi(k+n)=(i',j')}$ cannot be on one of the first ${M-1}$ columns. Indeed, the monotonicity property implies ${M = ij \leq i'j'}$ . The fact that ${\phi}$ is a bijection assures us that ${\phi(1),...,\phi(k)}$ cover the first ${M-1}$ columns. Moreover, one element from the ${M}$ -th column is surely covered, namely ${(i,j) = \phi(k)}$ . This means that

$\displaystyle k \geq d(1)+...+d(M-1)+1 \geq M = ij,$

where we have denoted by ${d(n)}$ the number of positive divisors of ${n}$ .

Categories: Algebra, Number theory, Olympiad Tags: Algebra, monotone, number theory, olympiad, trick

Solving Poisson’s equation on a general shape using finite differences

October 14, 2014 beni22sof 3 comments

One of the questions I received in the comments to my old post on solving Laplace equation (in fact this is Poisson’s equation) using finite differences was how to apply this procedure on arbitrary domains. It is not possible to use this method directly on general domains. The main problem is the fact that, unlike in the case of a square of rectangular domain, when we have a general shape, the boudary can have any orientation, not only the orientation of the coordinate axes. One way to avoid approach this problem would be using the Finite Element Method. Briefly, you discretize the boundary, you consider a triangulation of the domain with respect to this discretization, then you consider functions which are polynomial and have support in a few number of triangles. Thus the problem is reduced to a finite dimensional one, which can be written as a matrix problem. The implementation is not straightforward, since you need to conceive algorithms for doing the discretization and triangulation of your domain.

One other approach is to consider a rectangle ${D}$ which contains the shape ${\Omega}$ and add a penalization on the exterior of your domain ${\Omega}$ . The problem to solve becomes something like:

$\displaystyle (-\Delta +\mu I) u = 1 \text{ on }D$

where ${\mu}$ is defined by

$\displaystyle \mu(x) = \begin{cases} 0 & x \in \Omega \\ + \infty & x \notin \Omega\end{cases}. \ \ \ \ \ (1)$

Note that doing this we do not need to impose the boundary condition ${u=0}$ on ${\partial \Omega}$ . This is already imposed by ${\mu}$ , and the fact that ${u}$ is forced to be zero outside ${\Omega}$ .

Beni Bogoşel's blog

Putnam 2014 Problems

Five points on a circle, centroids and perpendiculars

Variations on Fatou’s Lemma – Part 2

Variations on Fatou’s Lemma – Part 1

Problems of the Miklos Schweitzer Competition 2014

Monotonic bijection from naturals to pairs of natural numbers

Solving Poisson’s equation on a general shape using finite differences

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

All Time

Visitors

Follow “Beni Bogoşel's blog”

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

All Time

Visitors

Follow “Beni Bogoşel's blog”