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
![$[2,n^3]$](//latex.artofproblemsolving.com/1/9/0/190b163fcdebd34730f1948a1c136e57d3fe3692.png)
), 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
by TheBlackPuzzle913, Mar 23, 2025, 8:10 PM 
be a sequence such that 
and 
.
and 
)
where 
denotes the Fibonacci sequence.**
defined on 
by![\[f(x, y) = x^4 + y^4 - 2(x - y)^2.\]](http://latex.artofproblemsolving.com/1/d/9/1d9e85722971f67e3ba2dee0e12d119ceabc671a.png)
(and determine them) such that![\[\forall (x, y) \in \mathbb{R}^2, f(x, y) \geq \alpha \| (x, y) \|^2 + \beta,\]](http://latex.artofproblemsolving.com/e/b/3/eb384916db4e019c7ba11f52fadf973f515891e2.png)
where 
denotes the Euclidean norm.
be holomorphic functions on 
, where 
. Suppose that the function 
given by 
takes a maximum value in 
be constant on 
and 
and there exists a positive integer 
such that 
. Let 
be minimal polynomial 
over 
. Prove that 
be a function that admits a primitive 
such that 
if 
such that 
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)
, show that ![$\sqrt[k_i]{a_i}\in\mathbb{Q}$](http://latex.artofproblemsolving.com/1/e/9/1e98b3af4db054d32f00d529032658c15875251a.png)
for all 
.
square board contains either 
or 
. Such an arrangement is deemed successful if each number is the product of its neighbors. Find the number of successful arrangements.
be a connected graph disconnected by the removal of (all of the edges of) any odd cycle. Prove that 
there exists a 
such that more than 
for some integer 
, where ![$f\in\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/1/1/9/119792ece753aa569a509d6f54a0a9f7f9ccc014.png)
is a nonconstant monic polynomial.
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 
.
of integers with 
, a subset 
is called a skipping set for 
if 
for any 
. Let 
be the maximum size of a skipping set for 
.
with the following property: for any real numbers 
, knowing the numbers 
, 
, determines the values 
that intersects all hyperplanes is 
.
is a derivable function with the property 
, for every 
, then f is a polynomial function of degree smaller or equal than 1
July 2014
June 2014
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 
,
,
,
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 
.
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 
that 
(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 
,
)
,
,
tiles. Reflecting over the horizontal axis we're left with horizontally symmetric tilings; now reflecting over the vertical axis we're left with tilings that are both horizontally and vertically symmetric.
where 
,
,
is Fibonacci, as all dominoes intersecting one of two axes must lie within the axes (by symmetry). By induction we get 
.
)
boards using the same recursive linear algebra ideas, but when both of 
are even it seems hard to reduce the problem.
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 number of positive 
for all 
.
;
is the set of primes, then
independent of 
.
gives the desired contradiction, since 
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.
.
,
.
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, 
.
,
,
.
,
,
,
and 
(with real but not necessarily integer exponents), then 
.![$[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.
.
;
)![\[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).
.