Updates (resources link, new website/blog)
by math154, Jul 31, 2014, 5:17 PM
MIT website: http://web.mit.edu/vywang/www/
Wordpress blog: http://vywang.wordpress.com/ (will hopefully have stuff once I figure out how to do http://lucatrevisan.wordpress.com/latex-to-wordpress/)
In particular, new shared resources link (handouts, notes, etc., both my own and other googled ones; in particular, I now have most of the stuff I wanted to share from HS*): https://www.dropbox.com/sh/kzf5l6uyzgkk2tj/AAA_xuAMQHX1dlswHAuwi5e8a
EDIT 7/26/19: This is broken. Some files may be available upon request (email me), but for many reasons I cannot post a public link. My understanding is that other people have been creating their own repositories, anyways.
(The link will inevitably break once I start moving stuff around, so let me know if that's the case. But I'll try to at least keep it updated on my website.)
*but was too lazy to. Note that this is a suboptimal way to share resources. An easy optimization would be to have a globally shared folder for every subject (more realistically, to avoid an organizational nightmare, people could label their files with multiple tags). This is actually sort of the idea behind https://selectedpapers.net/ (http://gowers.wordpress.com/2013/06/16/the-selected-papers-network/). Hopefully Alex Zhu sets up something along these lines for his startup.
(I should also add that just having resources without guidance is suboptimal too... but adding guidance/some direction doesn't seem too hard after collecting resources... also the linked blog post discusses a lot more about contests. Generally, I think better communication/collaboration in the contest community (and in general) could do a lot...)
Wordpress blog: http://vywang.wordpress.com/ (will hopefully have stuff once I figure out how to do http://lucatrevisan.wordpress.com/latex-to-wordpress/)
In particular, new shared resources link (handouts, notes, etc., both my own and other googled ones; in particular, I now have most of the stuff I wanted to share from HS*): https://www.dropbox.com/sh/kzf5l6uyzgkk2tj/AAA_xuAMQHX1dlswHAuwi5e8a
EDIT 7/26/19: This is broken. Some files may be available upon request (email me), but for many reasons I cannot post a public link. My understanding is that other people have been creating their own repositories, anyways.
(The link will inevitably break once I start moving stuff around, so let me know if that's the case. But I'll try to at least keep it updated on my website.)
*but was too lazy to. Note that this is a suboptimal way to share resources. An easy optimization would be to have a globally shared folder for every subject (more realistically, to avoid an organizational nightmare, people could label their files with multiple tags). This is actually sort of the idea behind https://selectedpapers.net/ (http://gowers.wordpress.com/2013/06/16/the-selected-papers-network/). Hopefully Alex Zhu sets up something along these lines for his startup.
(I should also add that just having resources without guidance is suboptimal too... but adding guidance/some direction doesn't seem too hard after collecting resources... also the linked blog post discusses a lot more about contests. Generally, I think better communication/collaboration in the contest community (and in general) could do a lot...)
This post has been edited 4 times. Last edited by math154, Jul 27, 2019, 1:05 AM
and 
for 
)
such that 
when 
for some bijection 
(and 
leaves 
)
,
;
(or write out stuff more carefully) then we're good to go. Anyway here 
works, where 
is a fixed positive integer and 
is just a scale factor to make 
,
.
using a uniform continuity bound to bound 
when 
is small. (We need uniform continuity since the same bound will apply independently of ![$f(i/n) [\binom{n}{i} x^i(1-x)^{n-i}]$](http://latex.artofproblemsolving.com/2/e/6/2e61ecea3266b65f0be72b15927ef80ce7807009.png)
term has "smooth/well-behaved contribution" that peaks when 
.
at 
,
at the 
,![$[x_{i-1},x_{i+1}]$](http://latex.artofproblemsolving.com/5/f/8/5f8ae149879869e82b087ee4f181d07b8f0d3285.png)
particularly hard to control, given that our main bound will probably come from uniform continuity of 
around ![$[-1,1]$](http://latex.artofproblemsolving.com/3/9/f/39f506ebeeeb72f62147990614a67f4e30b7c751.png)
:
.
for 
,
for 
and 
for 
.![$g(x) := \prod_{k=0}^{n} (x-t_k) = \frac{\sqrt{x^2-1}}{2^n}[(x+\sqrt{x^2-1})^n - (x-\sqrt{x^2-1})^n]$](http://latex.artofproblemsolving.com/7/6/d/76dfb22f0c2079f221f9866d893ea92a267872a1.png)
with 
,
on 
if 
,
otherwise. So letting 
and noting that 
,![\[ \frac{x - P_n(x)}{2} = g(x)\left(\frac{t_n}{x-t_n}\frac{2^{n-2}}{(-1)^n n} + \sum_{k > n/2}^{n-1} \frac{t_k}{x-t_k}\frac{2^{n-1}}{(-1)^k n}\right). \]](http://latex.artofproblemsolving.com/b/1/6/b1641e06e18eaf0b8be0eb042c3079c19b210837.png)
we have 
,
,
a negative number with increasing magnitude as 
increases in ![$(n/2,n]$](http://latex.artofproblemsolving.com/6/7/5/6757bc5f8dce899871cf5f66c725faed73963434.png)
.![\[ \frac{|x-P_n(x)|}{2} \le |g(x)| \frac{2^{n-2}}{n} (1 + 2\cdot 1) \le \frac{3}{2n} \]](http://latex.artofproblemsolving.com/4/a/2/4a25d6a76c6b2ee9491339ce899afa06627c7fd7.png)
,
for all ![$x\in[-1,1]$](http://latex.artofproblemsolving.com/5/2/e/52ebe6de79419fad5a4cc599c58421f8140a8e18.png)
,
-![$f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$](http://latex.artofproblemsolving.com/9/8/f/98fc63aef1bb3cafef1cdb5a6955dc61e83d7204.png)
with 
.![$f'(x)f(x)^{-1} \in \mathbb{Z}[[x]]$](http://latex.artofproblemsolving.com/1/1/0/110455880d6f898bbe2cf590f19d41be521f989d.png)
.
for all 
.
be a noncommutative ring with identity. Show that if an element 
has more than one right inverse, then 
,
.
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 
.
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 
in the Cartesian plane.
,
as follows: if 
is end of a snake, then set 
;
or 
)
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 
,![\[ 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)
,
.
at random from the unit interval ![$[0,1]$](http://latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
.
be the probability that 
for all 
.
.
,
is a polynomial with constant term 
.
and for 
,
.
.
(for 
and 
.
.
,
suggests trying 
for some (formal) power series 
.
,
,
we get 
,
.
must equal 
,
.
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 
,
of degree 
,
.
,
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 
,
,
.
,
recursively by 
,
,
,![\[ x_{k+2} = \frac{cx_{k+1} - (n-k)x_k}{k+1}. \]](http://latex.artofproblemsolving.com/d/8/d/d8dc064aea34a798099ffe3046c4a148da1fe477.png)
Fix 
.
.
,
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 
.
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 
.
.
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 
all distinct points on opposite sides; for Pascal, no two opposite sides parallel)
,
on 
,
is above, 
is below 
,
is a plane, etc.
,
,
,
,
are coplanar, so 
and 
intersect at a point on the line equal to the intersection of planes 
and 
,
and 
,
,
,
(possibly degenerate, but then the result's obvious) intersects plane 
,
,
,
be positive rational numbers and let 
be integers greater than 1. If ![$\sum_{i=1}^{n}\sqrt[k_i]{a_i}\in\mathbb{Q}$](http://latex.artofproblemsolving.com/6/d/3/6d3268640d63424770f2abb2e6c42657d054ace0.png)
,![$\sqrt[k_i]{a_i}\in\mathbb{Q}$](http://latex.artofproblemsolving.com/1/e/9/1e98b3af4db054d32f00d529032658c15875251a.png)
for all 
and go by contradiction. For motivation we look at the 
case. WLOG 
are ``minimal'' in the sense that 
for 
.
for all 
is the minimal polynomial of 
over the rationals, so 
.
;
and we can easily get a contradiction by considering the ![$[x^{k_1-1}]$](http://latex.artofproblemsolving.com/a/1/3/a131a3600dec6f0f8fc7d7d771d8e0224b7b78cc.png)
coefficients.![\[x^{k_1}-a_1\mid \prod_{\omega_i^{k_i}=1,2\le i\le n}(S-x-\sum_{i=1}^{n}\omega_i a_i^{1/k_i})\in\mathbb{Q}[x],\]](http://latex.artofproblemsolving.com/1/c/e/1ce1cb394f58859b98d50fe5b410b813d4c9a5a1.png)
t
and (any) nontrivial 
t
,
.![\[ 0=\Re(S-S) = \Re(a_1^{1/k_1}(1-\omega_1))+\sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) > \sum_{i=2}^{n}\Re((1-\omega_i)a_i^{1/k_i}) \ge 0,\]](http://latex.artofproblemsolving.com/2/3/9/2399ccddd04a1f97962cffb620d26fa61541fa66.png)
are all positive, but then 
.
square board contains either 
or 
.
there are two; we restrict our attention to 
.
of each entry so we're working in 
instead; we're choosing some of the 
entires to be 1. Viewing this as the equation 
(where boundary cases are 0 for convenience), we can set up a matrix equation 
where 
iff entries 
(there are 
total) are neighboring, and 
has a 1 for each entry 
(whence 
must be the all-zero vector and there's exactly one solution)---note that for 
(as we're working 
that contributes 1 to the sum (i.e. doesn't vanish), draw an arrow from 
for each 
board into disjoint directed cycles of size 1 or 
for some 
(arrows connect neighboring elements---these directed cycles correspond to permutation cycles). These cycles are nontrivially ``reversible'' iff 
,
)
,
it's easy to check that 
where 
,
,
is Fibonacci, as all dominoes intersecting one of two axes must lie within the axes (by symmetry). By induction we get 
.
)
are even it seems hard to reduce the problem.
be a connected graph disconnected by the removal of (all of the edges of) any odd cycle. Prove that 
be two positive integers. A graph 
is 
-
such that 
and 
are 
-
to a vertex colored 
in 
,
,
and 
,
for 
and 
and define 
by the first and second coordinates, respectively---the induced subgraphs 
can easily be split in the desired form.) 
and 
are both bipartite.
without inducing an odd cycle. Now assume for the sake of contradiction that 
)
,
.
and 
(indices modulo 
)
are connected in 
for all 
.
is connected in 
to at least one vertex of 
denote the time it takes for car 
when in and out of town, respectively; let 
(not both zero) be the distances from flag 
to get to flag 
for some 
for all 
pairwise distinct cars (WLOG cars 
for all 
and 
.
iff![\[(x_k,y_k)\in S_{i,j}=\{(x,y)\mid L_{i,j}(x,y)=(a_i-a_j)x+(b_i-b_j)y+(t_i-t_j)>0\},\]](http://latex.artofproblemsolving.com/f/9/f/f9f56603a6e3049e2438f5de19aa67b1403e9a91.png)
and 
iff 
.
in the Cartesian plane for 
and 
)
(where 
is the number of lines) distinct regions (well-known, e.g. 
and 
are in the same region iff the orderings at flags 
are equal, so we're done by pigeonhole.
(in reduced form) is infinitely often not a prime power.
and primes from 
to 
for 
,
,
as well. Subtracting dudes, get a contradiction.
for some integer ![$f\in\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/1/1/9/119792ece753aa569a509d6f54a0a9f7f9ccc014.png)
is a nonconstant monic polynomial.
.
for all 
;
is the set of primes, then
gives the desired contradiction, since 
and consider a set 
pairwise distinct positive integers smaller than or equal to 
.
and three nonzero integers 
such that 
,
,
.
and then find the 
,
by![\[(x,y,z)=(sb-tc,rc-sa,ta-rb).\]](http://latex.artofproblemsolving.com/a/6/1/a61a0691f211ac68254bd29c6f0536a29f57cd5e.png)
This gives us the idea of fixing 
(all nonzero for pigeonhole to work out).
(or all 
,
are all nonzero.) Luckily, the rest works out easily: to make 
,
,
indices, for 
,
,
(optimal by AM-GM) 
and 
)
triples with ![$[2,n^3]$](http://latex.artofproblemsolving.com/1/9/0/190b163fcdebd34730f1948a1c136e57d3fe3692.png)
)
times, as desired.
of integers with 
,
is called a skipping set for 
if 
for any 
.
be the maximum size of a skipping set for 
.
,
.
elements, so we end up with at least 
elements, which is realized for 
.
,
,
for 
.
for 
will give the maximum (we know it can't be far). Indeed, we can get 
with 
.
always. Assume for the sake of contradiction that 
for some 
alone: letting 
for 
and 
,![\[1335\le f(a,b)\le f(a) = \lceil{(q+1)/2}\rceil r+\lceil{q/2}\rceil (a-r).\]](http://latex.artofproblemsolving.com/d/1/d/d1d66c4771c0c5fb8ec65c5f1f5efa297a1613bd.png)
If 
is odd, this becomes 
,
.
.
,
,
and from the previous paragraph, 
.
,
,
.
,
,
,
with the following property: for any real numbers 
,
,
,
and 
(with real but not necessarily integer exponents), then 
.
)
to telescope products some way or differentiation), or just special values. Screwing around, it turns out differentiation is pretty helpful here.![$[f(x)f(x)]^{(m)}$](http://latex.artofproblemsolving.com/5/4/c/54cd75085605e25a31511cb243fbbff62a84251e.png)
and the fact that![\[[f(x^2)]^{(m)} = (2x)^{m}f^{(m)}(x^2)+\sum_{j=0}^{m-1}P_{m,j}(x)f^{(j)}(x^2)\]](http://latex.artofproblemsolving.com/e/1/7/e1719e74c1e1c93eb39f7edcbadcb4df164423ff.png)
for some polynomials 
(both facts are easily proven by induction), we can show by induction on 
(base case is just 
)
)![\[2^m(f^{(m)}(1)-g^{(m)}(1)) = 2n[f^{(m)}(1)-g^{(m)}(1)],\]](http://latex.artofproblemsolving.com/f/0/8/f08ea9124c9dfc81fe869313dbb47988d8cf0505.png)
which implies 
for all 
.
for all integers 
,
.
.
to be actual polynomials (i.e. with integer exponents), so taking the induction from the previous paragraph up until 
for some polynomial 
.
.
(identically); then the sets of numbers corresponding to ![$f(x)=[(x+1)^{m+1}+(x-1)^{m+1}]/2$](http://latex.artofproblemsolving.com/c/2/8/c28cff6c1953fb9402a54167c82d8ad060940ca8.png)
and ![$g(x)=[(x+1)^{m+1}-(x-1)^{m+1}]/2$](http://latex.artofproblemsolving.com/e/f/7/ef76f8370adf9dc8f8ad90b26e0cf37cb91939d1.png)
suffice.
with multiplicity 
for some 
.
means that 
is a power of 2, as desired.
that intersects all hyperplanes is 
.
.
;
)![\[f(x)=\prod_{s\in S'=S\setminus0}(\langle{x,s}\rangle - 1)+C\prod_{i=1}^{d}\prod_{j=1}^{p-1}(x_i-j),\]](http://latex.artofproblemsolving.com/a/2/d/a2de23b2953566e0ae97d69b28880a4428fe1240.png)
where 
is taken so that 
.
,
.
in 
such that 
)
(obviously 
does not belong to it, and because 
,
and so the first cannot, whence 
does not intersect the plane either), contradiction.
with at least 
of the 
'
with 
,
works).
.
July 2014
June 2014