random stuff
by math154, Dec 15, 2013, 7:43 AM
I should stop procrastinating on finals studying. Anyway, here are some nice problems from Putnam seminar this semester... (A lot of these are probably Putnam problems even if I didn't label them as such.)
1. (MIT Problem Solving Seminar, Congruences and Divisibility) Consider![$f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$](//latex.artofproblemsolving.com/9/8/f/98fc63aef1bb3cafef1cdb5a6955dc61e83d7204.png)
with 
. Suppose that ![$f'(x)f(x)^{-1} \in \mathbb{Z}[[x]]$](//latex.artofproblemsolving.com/1/1/0/110455880d6f898bbe2cf590f19d41be521f989d.png)
. Prove or disprove that 
for all 
.
2. (MIT Problem Solving Seminar, Abstract Algebra) Let
be a noncommutative ring with identity. Show that if an element 
has more than one right inverse, then 
has infinitely many right inverses.
3. (MIT Problem Solving Seminar, ``Hidden'' Independence and Uniformity) A snake on the
chessboard is a nonempty subset 
of the squares of the board obtained as follows: Start at one of the squares and continue walking one step up or to the right, stopping at any time. The squares visited are the squares of the snake. Find the total number of ways to cover an chessboard with disjoint snakes.
4. (MIT Problem Solving Seminar, Generating Functions; Putnam 1948 A6) Show that![\[ x + \frac23 x^3 + \frac23\frac45 x^5 + \frac23\frac45\frac67 x^7 + \cdots = \frac{\sin^{-1}{x}}{\sqrt{1-x^2}}. \]](//latex.artofproblemsolving.com/0/4/4/044e0c7ac640ca3d433de716fdc354e033502aa1.png)
5. (MIT Problem Solving Seminar, Probability) Choose
points 
at random from the unit interval ![$[0,1]$](//latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
. Let 
be the probability that 
for all 
. Compute the generating function 
.
6. (MIT Problem Solving Seminar, Analysis; Putnam 1996 B6) Let
be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive reals 
such that 
.
7. (MIT Problem Solving Seminar, Analysis; Putnam 1999 A5) Prove that there is a constant
such that for every polynomial 
of degree 
, 
.
8. (MIT Problem Solving Seminar, Recurrences; Putnam 1997 A6) For a positive integer and any real number 
, define 
recursively by 
, 
, and for 
, ![\[ x_{k+2} = \frac{cx_{k+1} - (n-k)x_k}{k+1}. \]](//latex.artofproblemsolving.com/d/8/d/d8dc064aea34a798099ffe3046c4a148da1fe477.png)
Fix and then take to be the largest value for which 
. Find in terms of and 
, 
.
9. (MIT Problem Solving Seminar, Polynomials; Putnam 1956 B7?) The nonconstant polynomials
and 
with complex coefficients have the same set of numbers for their zeros but possibly different multiplicities. The same is true of the polynomials 
and 
. Prove that 
.
1. (MIT Problem Solving Seminar, Congruences and Divisibility) Consider
![$f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$](http://latex.artofproblemsolving.com/9/8/f/98fc63aef1bb3cafef1cdb5a6955dc61e83d7204.png)
with 
. Suppose that ![$f'(x)f(x)^{-1} \in \mathbb{Z}[[x]]$](http://latex.artofproblemsolving.com/1/1/0/110455880d6f898bbe2cf590f19d41be521f989d.png)
. Prove or disprove that 
for all 
.2. (MIT Problem Solving Seminar, Abstract Algebra) Let
be a noncommutative ring with identity. Show that if an element 
has more than one right inverse, then 
has infinitely many right inverses.
,
.
denotes 
,
has the same (finite) size as 
.
.
,
and we deduce 
.
.
implies 
,![\[ 0 = (1-y_0x)(1-y_0x) = 1-y_0x-y_0x+y_0xy_0x = 1-y_0x-y_0x+y_0 1 x = 1-y_0x. \]](http://latex.artofproblemsolving.com/5/a/b/5ab13dae46c2bdc4ba2130e4c1e8759a17b91045.png)
,
,
from 
.3. (MIT Problem Solving Seminar, ``Hidden'' Independence and Uniformity) A snake on the
chessboard is a nonempty subset 
of the squares of the board obtained as follows: Start at one of the squares and continue walking one step up or to the right, stopping at any time. The squares visited are the squares of the snake. Find the total number of ways to cover an chessboard with disjoint snakes.
in the Cartesian plane.
,
as follows: if 
is end of a snake, then set 
;
or 
)
is that 
for any two points 
along the same ``main'' diagonal. Indeed, for any such 
with 
for all 
.
denote the number of valid 
,
.
.
,
)
for 
.
,
and 
tiles corresponding to 
,
,
for any non-invertible square with 
.
-
-
,
grid with 
.
chessboards. When 
,4. (MIT Problem Solving Seminar, Generating Functions; Putnam 1948 A6) Show that
![\[ x + \frac23 x^3 + \frac23\frac45 x^5 + \frac23\frac45\frac67 x^7 + \cdots = \frac{\sin^{-1}{x}}{\sqrt{1-x^2}}. \]](http://latex.artofproblemsolving.com/0/4/4/044e0c7ac640ca3d433de716fdc354e033502aa1.png)
.
,![$G'(x) - 1 = x[G(x) + xG'(x)]$](http://latex.artofproblemsolving.com/1/d/c/1dcce0d68b41330be4b006ca946ecadead78b938.png)
,
.
.
and 
,![\[ G(x)\sqrt{1-x^2} = \int_0^x \frac{1}{1-t^2}\sqrt{1-t^2}\;dt = \sin^{-1}{x}, \]](http://latex.artofproblemsolving.com/7/a/4/7a469e8f2d208e9b3cfaf2b3daef35114e565b21.png)
![\[ (\sin^{-1}{x})' = (1-x^2)^{-1/2} = \sum_{k\ge0}\binom{-1/2}{k}(-x^2)^k = \sum_{k\ge0}(-1)^k\frac{(2k-1)!!}{2^k k!}(-1)^k x^{2k} = \sum_{k\ge0}\frac{(2k-1)!!}{2^k k!}x^{2k}, \]](http://latex.artofproblemsolving.com/1/d/f/1dfeb788fd8faa485b583c469bf305f696b84641.png)
,![\[ \sin^{-1}{x}(1-x^2)^{-1/2} = \sum_{a\ge0}\frac{(2a-1)!!}{(2a+1)2^a a!}x^{2a+1}\sum_{b\ge0}\frac{(2b-1)!!}{2^b b!}x^{2b} = \sum_{n\ge0}x^{2n+1}\sum_{a+b=n}\frac{(2a-1)!!(2b-1)!!}{2^n(2a+1)a!b!}. \]](http://latex.artofproblemsolving.com/b/5/7/b57cee32944d98afb39dbda4098b487d127907ca.png)
,
.5. (MIT Problem Solving Seminar, Probability) Choose
points 
at random from the unit interval ![$[0,1]$](http://latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
. Let 
be the probability that 
for all 
. Compute the generating function 
.
,
is a polynomial with constant term 
.
and for 
,
.
.
(for 
)
and 
.
.
,
suggests trying 
for some (formal) power series 
.
,
,
we get 
,
.
must equal 
,
.6. (MIT Problem Solving Seminar, Analysis; Putnam 1996 B6) Let
be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive reals 
such that 
.
denote our convex 
.
,
for some 
,
for each 
.
lies in the \emph{interior} 
(indpendent of 
lies in 
,
and 
.
and ![$(u,v)\in[C^{-1/\epsilon},C^{1/\epsilon}]^2$](http://latex.artofproblemsolving.com/a/0/b/a0b60420867ff42413d5cf37e762cc82576da543.png)
.![$S = [\frac12 n^{-1/\epsilon},2n^{1/\epsilon}]^2$](http://latex.artofproblemsolving.com/6/c/1/6c1cbae452cd8f9f05138af04bb4c56edb26581a.png)
,
means 
,7. (MIT Problem Solving Seminar, Analysis; Putnam 1999 A5) Prove that there is a constant
such that for every polynomial 
of degree 
, 
.
,![$x\in[-1,1]$](http://latex.artofproblemsolving.com/5/2/e/52ebe6de79419fad5a4cc599c58421f8140a8e18.png)
satisfying 
is contained in an interval of length at most 
.
,
,
.
.
,
.
,
and the same sign as 
,![$[-1,-(1-\epsilon)]$](http://latex.artofproblemsolving.com/0/6/3/06351d9c5991c9e9fbcda93c0f7ca48e28924c59.png)
or ![$[1-\epsilon,1]$](http://latex.artofproblemsolving.com/3/6/9/369c3fea031c4c25f1c1994813e6f8dcca48b5d8.png)
,
.
and write 
for some complex numbers 
.
.
lies in a union of intervals of total length at most 
,
,
.8. (MIT Problem Solving Seminar, Recurrences; Putnam 1997 A6) For a positive integer
and any real number 
, define 
recursively by 
, 
, and for 
, ![\[ x_{k+2} = \frac{cx_{k+1} - (n-k)x_k}{k+1}. \]](http://latex.artofproblemsolving.com/d/8/d/d8dc064aea34a798099ffe3046c4a148da1fe477.png)
Fix and then take to be the largest value for which 
. Find in terms of and 
, 
.
,
for 
.
,
,![\[ (c-(n-1)t)f(t) = \sum_{k\ge0}cx_{k+1}t^k - (n-1)x_k t^k = \sum_{k\ge0} (k+1)x_{k+2}t^k - (k-1)x_k t^k = (1 - t^2)f'(t). \]](http://latex.artofproblemsolving.com/9/5/9/959c00b484ca60e4523ca022ab77ec92c624c6dc.png)
is a root of 
,
with multiplicity 
,
.
(since 
)
.
,
,
is maximal (such that 
,
for 
.9. (MIT Problem Solving Seminar, Polynomials; Putnam 1956 B7?) The nonconstant polynomials
and 
with complex coefficients have the same set of numbers for their zeros but possibly different multiplicities. The same is true of the polynomials 
and 
. Prove that 
.
be the set of roots (without multiplicity) of a polynomial ![$f\in\mathbb{C}[x]$](http://latex.artofproblemsolving.com/4/c/7/4c7af160dbe982332c129a4220f16366307a9ff7.png)
.![$P,Q\in\mathbb{C}[x]$](http://latex.artofproblemsolving.com/b/1/2/b127fe9cd6bbd70dcc23ac527bea2eea34e95fee.png)
such that 
and 
.
and complex 
,![\[ P(x) = c(x-b_1)^{s_1}\cdots(x-b_n)^{s_n};\qquad P(x)+1 = c(x-a_1)^{r_1} \cdots (x-a_m)^{r_m} \]](http://latex.artofproblemsolving.com/7/b/1/7b17a2a207df436c1515d85f09edd843cda02fe9.png)
![\[ Q(x) = d(x-b_1)^{u_1} \cdots (x-b_n)^{u_n};\qquad Q(x)+1 = d(x-a_1)^{t_1} \cdots (x-a_m)^{t_m} \]](http://latex.artofproblemsolving.com/1/7/7/177a79b36bc85b7dfbd269d576b13743ae721ed8.png)
and positive integers 
with 
and 
.
and 
must be disjoint 
![\[ (x-b_1)^{s_1-1}\cdots(x-b_n)^{s_n-1}(x-a_1)^{r_1-1}\cdots(x-a_m)^{r_m-1} \mid P' = (P+1)'. \]](http://latex.artofproblemsolving.com/9/c/e/9ce2661a48b7b0f4faa63808e7418be6fe329196.png)
,
.![\[ (x-b_1)\cdots(x-b_n)(x-a_1)\cdots(x-a_m)\mid P-Q = (P+1)-(Q+1) \ne0 \]](http://latex.artofproblemsolving.com/1/9/9/1994327ea3ef95e81d01b8882157a519030638e7.png)
,
,
.
has at least 
roots from 
from This post has been edited 11 times. Last edited by math154, Dec 15, 2013, 8:45 AM
July 2014
June 2014