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.
SolutionLet
. For fixed
, let

denote the number of positive

such that

is prime, and suppose for the sake of contradiction that there exists some

such that

for all
. Fix a real
; if

is the set of primes, then
\[\begin{align*}
N\sum_{k\ge1}\frac{1}{k^s} &\ge\sum_{k\ge1}\frac{g(k)}{k^s} \\
&=\sum_{p\in\mathbb{P}}\sum_{1\le f(T)for some
independent of
. Any
gives the desired contradiction, since the sum of the reciprocals of the primes diverges.
Edit: Thanks.
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
.
SolutionThe key is to realize that we probably want to use pigeonhole somehow (the

and

are rather ugly for an inductive argument). But this is not really related to the geometry of numbers since we have at least as many equations as variables, so we want to "fix" some sort of vector

and then find the
's from there (the three vectors
, etc. are orthogonal to
).
Now we want to get a feel of the most natural way to fix
. Note that we can parameterize all solutions to

by
![\[(x,y,z)=(sb-tc,rc-sa,ta-rb).\]](//latex.artofproblemsolving.com/a/6/1/a61a0691f211ac68254bd29c6f0536a29f57cd5e.png)
This gives us the idea of fixing

(all nonzero for pigeonhole to work out).
Intuitively, to get the best bounds for this simplest case, we want to take

(or all
). (Furthermore, if we had, say,
, then it would be hard to control the requirement that

are all nonzero.) Luckily, the rest works out easily: to make

as small as possible (for pigeonhole to work optimally, since we know all the

are less than or equal to
), let the elements of

be
, and for the
, choose from the first set of

indices, for
, choose from the second set of

indices, and for
, choose from the last set of

indices. We get a total of

(optimal by AM-GM)

(note that

and
), yet only

triples with

and

are possible in the first place (to count all possible triples, we can assume the smallest number chosen is

and then choose two larger values in the range
), so by pigeonhole, some

must occur at least

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
.
SolutionLet
.
For the minimum, note that we can keep doing the following: take
, which kills at most two others in
(
if they're in
), and repeat with the new set
. Each time we remove at most

elements, so we end up with at least

elements, which is realized for
.
For the maximum, we first analyze the one variable case to gain some intuition: of course, for fixed
, we can just consider each residue modulo

separately (and it's just alternating in
, out
, etc. for a fixed residue), where the best ratio is around
, achieved for

for
.
With the proof and construction for the one variable case in mind, we suspect that

for

will give the maximum (we know it can't be far). Indeed, we can get

with
.
It remains to show that

always. Assume for the sake of contradiction that

for some
.
First we get some crude estimations from

alone: letting

for

and
, we get
![\[1335\le f(a,b)\le f(a) = \lceil{(q+1)/2}\rceil r+\lceil{q/2}\rceil (a-r).\]](//latex.artofproblemsolving.com/d/1/d/d1d66c4771c0c5fb8ec65c5f1f5efa297a1613bd.png)
If

is odd, this becomes
, and if

is even, then
.
Hence
. If
, then
, so

and from the previous paragraph,
. Thus
, so because equality holds everywhere, we must have
, which contradicts
.
Otherwise, if
, then
, so
, contradiction.
4. (Erdős and Selfridge) Find all positive integers

with the following property: for any real numbers
, knowing the numbers
,
, determines the values

uniquely.
SolutionThe property (say,
goodness) holds iff for every two "polynomials"

and

(with real but not necessarily integer exponents), then
.
We'll show that

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]$](//latex.artofproblemsolving.com/e/8/6/e861e10e1c19918756b9c8b7717684593c63aeb8.png)
(maybe
), algebraic manipulation (especially either using

to telescope products some way or differentiation), or just special values. Screwing around, it turns out differentiation is pretty helpful here.
If

is not a power of 2, then by the
general Leibniz rule on
![$[f(x)f(x)]^{(m)}$](//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)\]](//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
) that (sorry for sloppiness, but this is assuming the strong inductive hypothesis for
)
![\[2^m(f^{(m)}(1)-g^{(m)}(1)) = 2n[f^{(m)}(1)-g^{(m)}(1)],\]](//latex.artofproblemsolving.com/f/0/8/f08ea9124c9dfc81fe869313dbb47988d8cf0505.png)
which implies

for all
. Thus (by induction/Stirling numbers)

for all integers
, so by easy bounding considerations
.
Otherwise, let
. For the construction, we take

to be actual polynomials (i.e. with integer exponents), so taking the induction from the previous paragraph up until
, we have that

for some polynomial
. Plugging this in, we have
. We can just take

(identically); then the sets of numbers corresponding to
![$f(x)=[(x+1)^{m+1}+(x-1)^{m+1}]/2$](//latex.artofproblemsolving.com/c/2/8/c28cff6c1953fb9402a54167c82d8ad060940ca8.png)
and
![$g(x)=[(x+1)^{m+1}-(x-1)^{m+1}]/2$](//latex.artofproblemsolving.com/e/f/7/ef76f8370adf9dc8f8ad90b26e0cf37cb91939d1.png)
suffice.
Edit: There's a cleaner way using rational approximation (assume all the guys are large integers). If

is a root of

with multiplicity
, then

for some
. But then

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
.
SolutionSuppose by way of contradiction that there's a set

intersecting all hyperplanes with
. WLOG
; now consider the polynomial (over
)
![\[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),\]](//latex.artofproblemsolving.com/a/2/d/a2de23b2953566e0ae97d69b28880a4428fe1240.png)
where

is taken so that
. Since
,
. Since the coefficient of

in

is nonzero, CNS guarantees

such that
(
), whence

does not intersect the plane

(obviously

does not belong to it, and because
, the second part of

vanishes at

and so the first cannot, whence

does not intersect the plane either), contradiction.
On the other hand, the construction for

is obvious: just take

the set of

with at least

of the
's zero (if a plane does not contain the origin, it's WLOG of the form

with
, and so

works).
Comment: This extends directly to any finite field
.
This post has been edited 8 times. Last edited by math154, Dec 9, 2012, 11:06 PM