More storage
by math154, Jan 3, 2012, 3:29 AM
1. (Sierpinski) Prove that for all 
there exists a 
such that more than prime numbers can be written in the form 
for some integer 
, where ![$f\in\mathbb{Z}[x]$](//latex.artofproblemsolving.com/1/1/9/119792ece753aa569a509d6f54a0a9f7f9ccc014.png)
is a nonconstant monic polynomial.
2. (ROM TST 1996) Let
and consider a set 
of 
pairwise distinct positive integers smaller than or equal to 
. Prove that one can find nine distinct numbers 
and three nonzero integers 
such that 
, 
, and 
.
3. (USA TST 2003) For a pair
of integers with 
, a subset of 
is called a skipping set for 
if 
for any 
. Let 
be the maximum size of a skipping set for . Determine the maximum and minimum values of 
.
4. (Erdős and Selfridge) Find all positive integers
with the following property: for any real numbers 
, knowing the numbers 
, 
, determines the values uniquely.
5. (Brouwer-Schrijver) Prove that the minimal cardinality of a subset of
that intersects all hyperplanes is 
.
there exists a 
such that more than prime numbers can be written in the form 
for some integer 
, where ![$f\in\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/1/1/9/119792ece753aa569a509d6f54a0a9f7f9ccc014.png)
is a nonconstant monic polynomial.
.
denote the number of positive 
for all 
.
;
is the set of primes, then
independent of 
.
gives the desired contradiction, since 2. (ROM TST 1996) Let
and consider a set 
of 
pairwise distinct positive integers smaller than or equal to 
. Prove that one can find nine distinct numbers 
and three nonzero integers 
such that 
, 
, and 
.
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 
and then choose two larger values in the range ![$[2,n^3]$](http://latex.artofproblemsolving.com/1/9/0/190b163fcdebd34730f1948a1c136e57d3fe3692.png)
)
times, as desired.3. (USA TST 2003) For a pair
of integers with 
, a subset of 
is called a skipping set for 
if 
for any 
. Let 
be the maximum size of a skipping set for . Determine the maximum and minimum values of 
.
.
,
.
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, 
.
,
,
.
,
,
,4. (Erdős and Selfridge) Find all positive integers
with the following property: for any real numbers 
, knowing the numbers 
, 
, determines the values uniquely.
and 
(with real but not necessarily integer exponents), then 
.
is good iff it's not a power of 2. To do this, we want to do some sort of bounding with values in ![$[0,1]$](http://latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
(maybe 
)
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.5. (Brouwer-Schrijver) Prove that the minimal cardinality of a subset of
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).
.This post has been edited 8 times. Last edited by math154, Dec 9, 2012, 11:06 PM
July 2014
June 2014