Shortlisted Problems with Solutions
54th International Mathematical Olympiad
Santa Marta, Colombia 2013
,Note of Confidentiality
The Shortlisted Problems should be kept
strictly confidential until IMO 2014.
Contributing Countries
The Organizing Committee and the Problem Selection Committee of IMO 2013 thank the following
50 countries for contributing 149 problem proposals.
Argentina, Armenia, Australia, Austria, Belgium, Belarus, Brazil, Bulgaria,
Croatia, Cyprus, Czech Republic, Denmark, El Salvador, Estonia, Finland,
France, Georgia, Germany, Greece, Hungary, India, Indonesia, Iran, Ireland,
Israel, Italy, Japan, Latvia, Lithuania, Luxembourg, Malaysia, Mexico,
Netherlands, Nicaragua, Pakistan, Panama, Poland, Romania, Russia,
Saudi Arabia, Serbia, Slovenia, Sweden, Switzerland, Tajikistan, Thailand,
Turkey, U.S.A., Ukraine, United Kingdom
Problem Selection Committee
Federico Ardila (chairman)
Ilya I. Bogdanov
Géza Kós
Carlos Gustavo Tamm de Araújo Moreira (Gugu)
Christian Reiher
,Shortlisted problems 3
Problems
Algebra
A1. Let n be a positive integer and let a1 , . . . , an´1 be arbitrary real numbers. Define the
sequences u0 , . . . , un and v0 , . . . , vn inductively by u0 “ u1 “ v0 “ v1 “ 1, and
uk`1 “ uk ` ak uk´1 , vk`1 “ vk ` an´k vk´1 for k “ 1, . . . , n ´ 1.
Prove that un “ vn .
(France)
A2. Prove that in any set of 2000 distinct real numbers there exist two pairs a ą b and c ą d
with a ‰ c or b ‰ d, such that ˇ ˇ
ˇa ´ b ˇ 1
ˇ c ´ d ´ 1ˇ ă 100000 .
ˇ ˇ
(Lithuania)
A3. Let Qą0 be the set of positive rational numbers. Let f : Qą0 Ñ R be a function satisfying
the conditions
f pxqf pyq ě f pxyq and f px ` yq ě f pxq ` f pyq
for all x, y P Qą0 . Given that f paq “ a for some rational a ą 1, prove that f pxq “ x for all
x P Qą0 .
(Bulgaria)
A4. Let n be a positive integer, and consider a sequence a1 , a2 , . . . , an of positive integers.
Extend it periodically to an infinite sequence a1 , a2 , . . . by defining an`i “ ai for all i ě 1. If
a1 ď a2 ď ¨ ¨ ¨ ď an ď a1 ` n
and
aai ď n ` i ´ 1 for i “ 1, 2, . . . , n,
prove that
a1 ` ¨ ¨ ¨ ` an ď n2 .
(Germany)
A5. Let Zě0 be the set of all nonnegative integers. Find all the functions f : Zě0 Ñ Zě0
satisfying the relation
f pf pf pnqqq “ f pn ` 1q ` 1
for all n P Zě0 .
(Serbia)
A6. Let m ‰ 0 be an integer. Find all polynomials P pxq with real coefficients such that
px3 ´ mx2 ` 1qP px ` 1q ` px3 ` mx2 ` 1qP px ´ 1q “ 2px3 ´ mx ` 1qP pxq
for all real numbers x.
(Serbia)
, 4 IMO 2013 Colombia
Combinatorics
C1. Let n be a positive integer. Find the smallest integer k with the following property: Given
any real numbers a1 , . . . , ad such that a1 ` a2 ` ¨ ¨ ¨ ` ad “ n and 0 ď ai ď 1 for i “ 1, 2, . . . , d, it
is possible to partition these numbers into k groups (some of which may be empty) such that the
sum of the numbers in each group is at most 1.
(Poland)
C2. In the plane, 2013 red points and 2014 blue points are marked so that no three of the
marked points are collinear. One needs to draw k lines not passing through the marked points and
dividing the plane into several regions. The goal is to do it in such a way that no region contains
points of both colors.
Find the minimal value of k such that the goal is attainable for every possible configuration of
4027 points.
(Australia)
C3. A crazy physicist discovered a new kind of particle which he called an imon, after some of
them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each
imon can participate in many entanglement relations. The physicist has found a way to perform
the following two kinds of operations with these particles, one operation at a time.
piq If some imon is entangled with an odd number of other imons in the lab, then the physicist
can destroy it.
piiq At any moment, he may double the whole family of imons in his lab by creating a copy I 1
of each imon I. During this procedure, the two copies I 1 and J 1 become entangled if and only if
the original imons I and J are entangled, and each copy I 1 becomes entangled with its original
imon I; no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons,
no two of which are entangled.
(Japan)
C4. Let n be a positive integer, and let A be a subset of t1, . . . , nu. An A-partition of n into k
parts is a representation of n as a sum n “ a1 ` ¨ ¨ ¨ ` ak , where the parts a1 , . . . , ak belong to A
and are not necessarily distinct. The number of different parts in such a partition is the number
of (distinct) elements in the set ta1 , a2 , . . . , ak u.
We say that an A-partition of n into k parts is optimal if there is no A-partition
? of n into r
3
parts with r ă k. Prove that any optimal A-partition of n contains at most 6n different parts.
(Germany)
C5. Let r be a positive integer, and let a0 , a1 , . . . be an infinite sequence of real numbers.
Assume that for all nonnegative integers m and s there exists a positive integer n P rm ` 1, m ` rs
such that
am ` am`1 ` ¨ ¨ ¨ ` am`s “ an ` an`1 ` ¨ ¨ ¨ ` an`s .
Prove that the sequence is periodic, i. e. there exists some p ě 1 such that an`p “ an for all n ě 0.
(India)
54th International Mathematical Olympiad
Santa Marta, Colombia 2013
,Note of Confidentiality
The Shortlisted Problems should be kept
strictly confidential until IMO 2014.
Contributing Countries
The Organizing Committee and the Problem Selection Committee of IMO 2013 thank the following
50 countries for contributing 149 problem proposals.
Argentina, Armenia, Australia, Austria, Belgium, Belarus, Brazil, Bulgaria,
Croatia, Cyprus, Czech Republic, Denmark, El Salvador, Estonia, Finland,
France, Georgia, Germany, Greece, Hungary, India, Indonesia, Iran, Ireland,
Israel, Italy, Japan, Latvia, Lithuania, Luxembourg, Malaysia, Mexico,
Netherlands, Nicaragua, Pakistan, Panama, Poland, Romania, Russia,
Saudi Arabia, Serbia, Slovenia, Sweden, Switzerland, Tajikistan, Thailand,
Turkey, U.S.A., Ukraine, United Kingdom
Problem Selection Committee
Federico Ardila (chairman)
Ilya I. Bogdanov
Géza Kós
Carlos Gustavo Tamm de Araújo Moreira (Gugu)
Christian Reiher
,Shortlisted problems 3
Problems
Algebra
A1. Let n be a positive integer and let a1 , . . . , an´1 be arbitrary real numbers. Define the
sequences u0 , . . . , un and v0 , . . . , vn inductively by u0 “ u1 “ v0 “ v1 “ 1, and
uk`1 “ uk ` ak uk´1 , vk`1 “ vk ` an´k vk´1 for k “ 1, . . . , n ´ 1.
Prove that un “ vn .
(France)
A2. Prove that in any set of 2000 distinct real numbers there exist two pairs a ą b and c ą d
with a ‰ c or b ‰ d, such that ˇ ˇ
ˇa ´ b ˇ 1
ˇ c ´ d ´ 1ˇ ă 100000 .
ˇ ˇ
(Lithuania)
A3. Let Qą0 be the set of positive rational numbers. Let f : Qą0 Ñ R be a function satisfying
the conditions
f pxqf pyq ě f pxyq and f px ` yq ě f pxq ` f pyq
for all x, y P Qą0 . Given that f paq “ a for some rational a ą 1, prove that f pxq “ x for all
x P Qą0 .
(Bulgaria)
A4. Let n be a positive integer, and consider a sequence a1 , a2 , . . . , an of positive integers.
Extend it periodically to an infinite sequence a1 , a2 , . . . by defining an`i “ ai for all i ě 1. If
a1 ď a2 ď ¨ ¨ ¨ ď an ď a1 ` n
and
aai ď n ` i ´ 1 for i “ 1, 2, . . . , n,
prove that
a1 ` ¨ ¨ ¨ ` an ď n2 .
(Germany)
A5. Let Zě0 be the set of all nonnegative integers. Find all the functions f : Zě0 Ñ Zě0
satisfying the relation
f pf pf pnqqq “ f pn ` 1q ` 1
for all n P Zě0 .
(Serbia)
A6. Let m ‰ 0 be an integer. Find all polynomials P pxq with real coefficients such that
px3 ´ mx2 ` 1qP px ` 1q ` px3 ` mx2 ` 1qP px ´ 1q “ 2px3 ´ mx ` 1qP pxq
for all real numbers x.
(Serbia)
, 4 IMO 2013 Colombia
Combinatorics
C1. Let n be a positive integer. Find the smallest integer k with the following property: Given
any real numbers a1 , . . . , ad such that a1 ` a2 ` ¨ ¨ ¨ ` ad “ n and 0 ď ai ď 1 for i “ 1, 2, . . . , d, it
is possible to partition these numbers into k groups (some of which may be empty) such that the
sum of the numbers in each group is at most 1.
(Poland)
C2. In the plane, 2013 red points and 2014 blue points are marked so that no three of the
marked points are collinear. One needs to draw k lines not passing through the marked points and
dividing the plane into several regions. The goal is to do it in such a way that no region contains
points of both colors.
Find the minimal value of k such that the goal is attainable for every possible configuration of
4027 points.
(Australia)
C3. A crazy physicist discovered a new kind of particle which he called an imon, after some of
them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each
imon can participate in many entanglement relations. The physicist has found a way to perform
the following two kinds of operations with these particles, one operation at a time.
piq If some imon is entangled with an odd number of other imons in the lab, then the physicist
can destroy it.
piiq At any moment, he may double the whole family of imons in his lab by creating a copy I 1
of each imon I. During this procedure, the two copies I 1 and J 1 become entangled if and only if
the original imons I and J are entangled, and each copy I 1 becomes entangled with its original
imon I; no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons,
no two of which are entangled.
(Japan)
C4. Let n be a positive integer, and let A be a subset of t1, . . . , nu. An A-partition of n into k
parts is a representation of n as a sum n “ a1 ` ¨ ¨ ¨ ` ak , where the parts a1 , . . . , ak belong to A
and are not necessarily distinct. The number of different parts in such a partition is the number
of (distinct) elements in the set ta1 , a2 , . . . , ak u.
We say that an A-partition of n into k parts is optimal if there is no A-partition
? of n into r
3
parts with r ă k. Prove that any optimal A-partition of n contains at most 6n different parts.
(Germany)
C5. Let r be a positive integer, and let a0 , a1 , . . . be an infinite sequence of real numbers.
Assume that for all nonnegative integers m and s there exists a positive integer n P rm ` 1, m ` rs
such that
am ` am`1 ` ¨ ¨ ¨ ` am`s “ an ` an`1 ` ¨ ¨ ¨ ` an`s .
Prove that the sequence is periodic, i. e. there exists some p ě 1 such that an`p “ an for all n ě 0.
(India)
