##### Document Text Contents

Page 1

MOP Homework 2015

The Graders

June 2015

1 Introduction

Welcome to MOP! Here are some problems the graders have picked out for you

to think about, and to help you get in gear for the summer. We’ll discuss these

on the first day. You’re welcome to work on as many of these as you wish,

regardless of your MOP group. A few suggestions:

• The “FUNDERMENTARS” section, geared towards the Red group, con-

tains some basic (well-known) results that are useful to know before you

get started at MOP. Look through these, and if there are any that you

haven’t seen or don’t know how to prove, prioritize working on these over

the rest of the problems. Feel free to skip anything you’ve seen before.

• The main section of problems are divided into four subjects: Algebra,

Combinatorics, Geometry, and Number Theory. If you’re limited on time,

try (approximately) the first half of each subsection if you’re in Red and

the second half if you’re in Blue/Black.

• If you think of the camp you’re attending as MOSP rather than MOP,

you are invited to try the problems in the “MOSP” homework section in

addition to the regular problems.

2 FUNDERMENTARS

2.1 Algebra

1. The image above is a proof of the AM-GM inequality in three variables.

Figure out how it works and extend it to n variables.

2. Prove Vieta’s formulas.

1

Page 2

2.2 GG Geometry

In this section, you will prove the existence of the incenter in several ways, and

discover other important results along the way.

0 a) Triangle ABC is inscribed in a circle with center O. Angle chase to

prove that ∠AOC = 2∠ABC.

b) Prove that a convex quadrilateralABCD is cyclic if and only if ∠ABD =

∠ACD.

1. a) Prove the extended law of sines: for a triangle ABC with circum-

radius R,

BC

sinA

=

CA

sinB

=

AB

sinC

= 2R.

b) Prove the angle bisector theorem: If the internal angle bisector of angle

BAC intersects side BC at X, then XB

XC

= AB

AC

.

c) Prove Ceva’s theorem: Given a triangle ABC with points D,E, F on

sides BC,CA,AB respectively, the lines AD,BE,CF concur if and only

if

BD

DC

CE

EA

AF

FB

= 1.

d) Conclude that the internal angle bisectors of a triangle ABC concur at

a point I, the incenter.

2. a) Use the law of sines and Ceva to prove trig Ceva: In the configuration

of Ceva’s theorem, lines AD,BE,CF concur if and only if

sinBAD

sinDAC

sinCBE

sinEBA

sinACF

sinFCB

= 1.

Conclude again that the incenter exists.

3. In triangle ABC, let BC = a,CA = b, AB = c, s = 1

2

(a+ b+ c). a) Prove

the following perpendicularity criterion: AB ? CD , AC2 + BD2 =

AD2 +BC2

b) Prove Carnot’s theorem: Given a triangle ABC with points D,E, F on

sides BC,CA,AB respectively, the perpendiculars to sides BC,CA,AB

at D,E, F respectively concur if and only if

(BD2 � DC2) + (CE2 � EA2) + (AF 2 � FB2) = 0.

c) Prove that the tangents to a circle from a point P outside the circle

have equal length.

d) Assuming there is a circle inside the triangle tangent to all three sides at

D,E, F respectively, compute the lengths BD,DC and analogous lengths

for other sides.

e) Constructing D,E, F to satisfy the length conditions above, prove that

the perpendiculars at these points intersect at a point that is indeed the

circumcenter of DEF , and show that this is the incenter of ABC.

2

Page 3

4. a) Prove that the internal bisector of angle A meets the perpendicular

bisector of BC at a point Ta on the circumcircle.

b) Prove that the circle wa with center Ta that goes through points B,C,

along with circles wb, wc defined analogously, all share a common point I,

and show that this is the incenter of ABC.

2.2.1 Things that are not the incenter

5. a) State and prove the Power of a Point theorem.

b) Use the perpendicularity criterion to prove that the locus of points with

the same power with respect to two circles w1, w2 is a line, their radical

axis.

c) Prove that the radical axes of three circles intersect at a point, their

radical center.

2.3 Numbers

In this problem, we will investigate integer linear combinations

1. Given non-zero integers A and B, let D be their gcd. Show that D is the

smallest positive integer which can be written as Ax+By for integers x, y.

2. Conclude that the set of values Ax+By is just the multiples of D.

3. Now, let A = p be a prime number, and use 1) to show that any B not

divisible by p has a multiplicative inverse modulo p, or equivalently that

for some C, p divides BC − 1. This means that every non-zero integer

mod p is invertible. The set of residues mod p is an example of a structure

called a field.

In this problem, you will prove Fermat’s little Theorem (FlT), which states that

ap ≡ a (mod p) for all primes p, in several ways.

1. Prove FlT by induction on a.

2. Consider the ways to color a necklace of p beads in a colors. Use shifting

symmetry to prove FlT.

3. Consider the set A of powers of a modulo p, 1, a, a2, . . .. Call bA =

b, ba, ba2, . . . a shift of A. Show that all shifts of A are either identical

as (unordered) sets or disjoint, and cover all non-zero elements modulo p.

Conclude FlT.

4. Extend part 3 to prove Euler’s totient theorem: let φ(n) be the num-

ber of integers in 1, 2, ...n which are relatively prime to n. Show that if

gcd(a, n) = 1, then aφ(n) − 1 is divisible by n.

2.4 Wombinatorics Combinatorics

1. Find a closed form for

P n

k=0 k

�

n

k

�

.

2. Show that any graph with at least as many edges as vertices has a cycle.

3

Page 4

3 Problems

3.1 Algebra

1. [South Africa 2014 #2] Given that

a− b

c− d

= 2 and

a− c

b− d

= 3

for certain real numbers a, b, c, d, and b 6= c, determine the value of

a− d

b− c

.

2. [ISL 2011 A2] Determine all sequences (x1, x2, . . . , x2011) of positive inte-

gers, such that for every positive integer n there exists an integer a with

2011∑

j=1

jxnj = a

n+1 + 1

3. [ISL 2010 A3] Let x1, . . . , x100 be nonnegative real numbers such that

xi + xi+1 + xi+2 ≤ 1 for all i = 1, . . . , 100 (we put x101 = x1, x102 = x2).

Find the maximal possible value of the sum S =

∑100

i=1 xixi+2.

4. [WOOT 2011-2012 Algebra Marathon #3] Solve the following equation

f : R→ R:

f(x+ f(y))[x− f(y)] = f(x2)− yf(y)

for all x, y ∈ R, and such that f(x) 6= 0 for all x 6= 0.

5. [Extension of Blue MOP 2011] A finite set A and another set B, both of

integers, have the property that any integer n may be written uniquely as

a sum n = a+ b for a in A, b in B.

(a) Prove that A is symmetric, that is, for some integer m, a is in A if

and only if m− a is in A.

(b) Classify the possible structures A can have.

6. [ELMO SL 2012 A8] Find all functions f : Q→ R such that f(x)f(y)f(x+

y) = f(xy)(f(x) + f(y)) for all x, y ∈ Q.

3.2 Combinatorics

1. [Classic] Prove that a graph is two-colorable if and only if it has no odd

cycles.

2. [Classic] When given an expression containing only +,−,×, constants,

variables, and parentheses, such as (x+ y)(z − 8w(x+ y(w+ z) + 7)− z),

we expand it by repeatedly using the distributive law. Must this process

always finish? Or if we choose which terms to expand badly, might we

have to keep expanding forever?

4

Page 5

3. [ISL 1998 C1] Hacker gives Matt, Jackie, and Inez a rectangular array

of numbers. In each row and each column, the sum of all numbers is

an integer. Prove that Inez can change each nonintegral number x in the

array into either dxe or bxc so that the row-sums and column-sums remain

unchanged. (Note that dxe is the least integer greater than or equal to x,

while bxc is the greatest integer less than or equal to x.)

4. [ISL 1988 #4] Let n ≥ 2. Bathspounge numbers an n×n chessboard with

the numbers 1, 2, . . . , n2. Every number occurs once. Prove that there

exist two orthogonally adjacent squares such that their numbers differ by

at least n.

5. [Brazil Olympic Revenge 2014] Let n be a positive integer. In a 2n × 2n

board, 1 × n and n × 1 pieces are arranged without overlap. Call an

arrangement maximal if it is impossible to put a new piece in the board

without overlapping the previous ones. Find the least k such that there

is a maximal arrangement that uses k pieces.

6. [SubredditControl] Snake shuffles a deck of playing cards. Salamander

guesses if the top card is red or black, then turns it over. If he’s right, he

wins a dollar. If not, he pays a dollar. Repeat for the rest of the deck,

one card at a time. What should be his strategy, and what is his expected

return?

7. [SubredditControl] Inez paints 1, 2, 3, . . . , N in red, blue and white, so that

each color has more than a quarter of the set in its colour. Can she paint

it such that all x+ y = z in the set has at least two of the same colour?

3.3 Geometry

1. [ISL 2006 G1] Let ABC be triangle with incenter I. A point P in the

interior of the triangle satisfies

\ PBA+ \ PCA = \ PBC + \ PCB.

Show that AP ≥ AI, and that equality holds if and only if P = I.

2. [USA TST 2004 #4] Let ABC be a triangle. Choose a point D in its

interior. Let ω1 be a circle passing through B and D and ω2 be a circle

passing through C and D so that the other point of intersection of the two

circles lies on AD. Let ω1 and ω2 intersect side BC at E and F , respec-

tively. Denote by X the intersection of DF , AB and Y the intersection

of DE,AC. Show that XY ‖ BC.

3. [ISL 2007 G3] The diagonals of a trapezoid ABCD intersect at point P .

Point Q lies between the parallel lines BC and AD such that \ AQD =

\ CQB, and line CD separates points P and Q. Prove that \ BQP =

\ DAQ.

4. [Linus 2015] A polygon of wrapping paper folds to cover a cube completely

with no overlap. Show that it has two equal angles.

5

Page 6

5. [Russia 2006] Consider an isosceles triangle ABC with AB = AC, and

a circle ω which is tangent to the sides AB and AC of this triangle and

intersects the side BC at the points K and L. The segment AK intersects

the circle ω at a point M (apart from K). Let P and Q be the reflec-

tions of the point K in the points B and C, respectively. Show that the

circumcircle of triangle PMQ is tangent to the circle ω.

6. [Iran 2010] Circles W1,W2 intersect at P,K. XY is common tangent of

two circles which is nearer to P and X is on W1 and Y is on W2. XP

intersects W2 for the second time in C and Y P intersects W1 in B. Let

A be intersection point of BX and CY . Prove that if Q is the second

intersection point of circumcircles of ABC and AXY

∠QXA = ∠QKP

7. [Tuymaada 2012] Quadrilateral ABCD is both cyclic and circumscribed.

Its incircle touches its sides AB and CD at points X and Y , respectively.

The perpendiculars to AB and CD drawn at A and D, respectively, meet

at point U ; those drawn at X and Y meet at point V , and finally, those

drawn at B and C meet at point W . Prove that points U , V and W are

collinear.

3.4 Number Theory

1. [South Africa 2004 #1] Let a = 1111 . . . 1111 and b = 1111 . . . 1111 where

a has forty ones and b has twelve ones. Determine the greatest common

divisor of a and b.

2. [Brazil Olympic Revenge 2010 #1] Fix a prime p and an integer a with

gcd(a, p) = 1. Prove that the number of ordered triples (x, y, z) of positive

integers such that 0 ≤ x, y, z < p and (x+y+z)2 ≡ axyz (mod p) is equal

to p2 + 1.

3. [ISL 2009 N3] Let f be a non-constant function from the set of positive

integers into the set of positive integer, such that a− b divides f(a)− f(b)

for all distinct positive integers a, b. Prove that there exist infinitely many

primes p such that p divides f(c) for some positive integer c.

4. [ISL 2001 N4] Let p ≥ 5 be a prime number. Prove that there exists an

integer a with 1 ≤ a ≤ p− 2 such that neither ap−1− 1 nor (a+ 1)p−1− 1

is divisible by p2.

5. [Linus’ Homework from UCL: Sarah Zerbes]

(a) Solve x3 = y2 + 1 in integers.

(b) Solve x3 = y2 + 5 in integers.

6. [ELMO SL 2011 N3] Let n > 1 be a fixed positive integer, and call

an n-tuple (a1, a2, . . . , an) of integers greater than 1 good if and only if

ai

∣∣∣ (a1a2···anai − 1) for i = 1, 2, . . . , n. Prove that there are finitely many

good n-tuples.

6

MOP Homework 2015

The Graders

June 2015

1 Introduction

Welcome to MOP! Here are some problems the graders have picked out for you

to think about, and to help you get in gear for the summer. We’ll discuss these

on the first day. You’re welcome to work on as many of these as you wish,

regardless of your MOP group. A few suggestions:

• The “FUNDERMENTARS” section, geared towards the Red group, con-

tains some basic (well-known) results that are useful to know before you

get started at MOP. Look through these, and if there are any that you

haven’t seen or don’t know how to prove, prioritize working on these over

the rest of the problems. Feel free to skip anything you’ve seen before.

• The main section of problems are divided into four subjects: Algebra,

Combinatorics, Geometry, and Number Theory. If you’re limited on time,

try (approximately) the first half of each subsection if you’re in Red and

the second half if you’re in Blue/Black.

• If you think of the camp you’re attending as MOSP rather than MOP,

you are invited to try the problems in the “MOSP” homework section in

addition to the regular problems.

2 FUNDERMENTARS

2.1 Algebra

1. The image above is a proof of the AM-GM inequality in three variables.

Figure out how it works and extend it to n variables.

2. Prove Vieta’s formulas.

1

Page 2

2.2 GG Geometry

In this section, you will prove the existence of the incenter in several ways, and

discover other important results along the way.

0 a) Triangle ABC is inscribed in a circle with center O. Angle chase to

prove that ∠AOC = 2∠ABC.

b) Prove that a convex quadrilateralABCD is cyclic if and only if ∠ABD =

∠ACD.

1. a) Prove the extended law of sines: for a triangle ABC with circum-

radius R,

BC

sinA

=

CA

sinB

=

AB

sinC

= 2R.

b) Prove the angle bisector theorem: If the internal angle bisector of angle

BAC intersects side BC at X, then XB

XC

= AB

AC

.

c) Prove Ceva’s theorem: Given a triangle ABC with points D,E, F on

sides BC,CA,AB respectively, the lines AD,BE,CF concur if and only

if

BD

DC

CE

EA

AF

FB

= 1.

d) Conclude that the internal angle bisectors of a triangle ABC concur at

a point I, the incenter.

2. a) Use the law of sines and Ceva to prove trig Ceva: In the configuration

of Ceva’s theorem, lines AD,BE,CF concur if and only if

sinBAD

sinDAC

sinCBE

sinEBA

sinACF

sinFCB

= 1.

Conclude again that the incenter exists.

3. In triangle ABC, let BC = a,CA = b, AB = c, s = 1

2

(a+ b+ c). a) Prove

the following perpendicularity criterion: AB ? CD , AC2 + BD2 =

AD2 +BC2

b) Prove Carnot’s theorem: Given a triangle ABC with points D,E, F on

sides BC,CA,AB respectively, the perpendiculars to sides BC,CA,AB

at D,E, F respectively concur if and only if

(BD2 � DC2) + (CE2 � EA2) + (AF 2 � FB2) = 0.

c) Prove that the tangents to a circle from a point P outside the circle

have equal length.

d) Assuming there is a circle inside the triangle tangent to all three sides at

D,E, F respectively, compute the lengths BD,DC and analogous lengths

for other sides.

e) Constructing D,E, F to satisfy the length conditions above, prove that

the perpendiculars at these points intersect at a point that is indeed the

circumcenter of DEF , and show that this is the incenter of ABC.

2

Page 3

4. a) Prove that the internal bisector of angle A meets the perpendicular

bisector of BC at a point Ta on the circumcircle.

b) Prove that the circle wa with center Ta that goes through points B,C,

along with circles wb, wc defined analogously, all share a common point I,

and show that this is the incenter of ABC.

2.2.1 Things that are not the incenter

5. a) State and prove the Power of a Point theorem.

b) Use the perpendicularity criterion to prove that the locus of points with

the same power with respect to two circles w1, w2 is a line, their radical

axis.

c) Prove that the radical axes of three circles intersect at a point, their

radical center.

2.3 Numbers

In this problem, we will investigate integer linear combinations

1. Given non-zero integers A and B, let D be their gcd. Show that D is the

smallest positive integer which can be written as Ax+By for integers x, y.

2. Conclude that the set of values Ax+By is just the multiples of D.

3. Now, let A = p be a prime number, and use 1) to show that any B not

divisible by p has a multiplicative inverse modulo p, or equivalently that

for some C, p divides BC − 1. This means that every non-zero integer

mod p is invertible. The set of residues mod p is an example of a structure

called a field.

In this problem, you will prove Fermat’s little Theorem (FlT), which states that

ap ≡ a (mod p) for all primes p, in several ways.

1. Prove FlT by induction on a.

2. Consider the ways to color a necklace of p beads in a colors. Use shifting

symmetry to prove FlT.

3. Consider the set A of powers of a modulo p, 1, a, a2, . . .. Call bA =

b, ba, ba2, . . . a shift of A. Show that all shifts of A are either identical

as (unordered) sets or disjoint, and cover all non-zero elements modulo p.

Conclude FlT.

4. Extend part 3 to prove Euler’s totient theorem: let φ(n) be the num-

ber of integers in 1, 2, ...n which are relatively prime to n. Show that if

gcd(a, n) = 1, then aφ(n) − 1 is divisible by n.

2.4 Wombinatorics Combinatorics

1. Find a closed form for

P n

k=0 k

�

n

k

�

.

2. Show that any graph with at least as many edges as vertices has a cycle.

3

Page 4

3 Problems

3.1 Algebra

1. [South Africa 2014 #2] Given that

a− b

c− d

= 2 and

a− c

b− d

= 3

for certain real numbers a, b, c, d, and b 6= c, determine the value of

a− d

b− c

.

2. [ISL 2011 A2] Determine all sequences (x1, x2, . . . , x2011) of positive inte-

gers, such that for every positive integer n there exists an integer a with

2011∑

j=1

jxnj = a

n+1 + 1

3. [ISL 2010 A3] Let x1, . . . , x100 be nonnegative real numbers such that

xi + xi+1 + xi+2 ≤ 1 for all i = 1, . . . , 100 (we put x101 = x1, x102 = x2).

Find the maximal possible value of the sum S =

∑100

i=1 xixi+2.

4. [WOOT 2011-2012 Algebra Marathon #3] Solve the following equation

f : R→ R:

f(x+ f(y))[x− f(y)] = f(x2)− yf(y)

for all x, y ∈ R, and such that f(x) 6= 0 for all x 6= 0.

5. [Extension of Blue MOP 2011] A finite set A and another set B, both of

integers, have the property that any integer n may be written uniquely as

a sum n = a+ b for a in A, b in B.

(a) Prove that A is symmetric, that is, for some integer m, a is in A if

and only if m− a is in A.

(b) Classify the possible structures A can have.

6. [ELMO SL 2012 A8] Find all functions f : Q→ R such that f(x)f(y)f(x+

y) = f(xy)(f(x) + f(y)) for all x, y ∈ Q.

3.2 Combinatorics

1. [Classic] Prove that a graph is two-colorable if and only if it has no odd

cycles.

2. [Classic] When given an expression containing only +,−,×, constants,

variables, and parentheses, such as (x+ y)(z − 8w(x+ y(w+ z) + 7)− z),

we expand it by repeatedly using the distributive law. Must this process

always finish? Or if we choose which terms to expand badly, might we

have to keep expanding forever?

4

Page 5

3. [ISL 1998 C1] Hacker gives Matt, Jackie, and Inez a rectangular array

of numbers. In each row and each column, the sum of all numbers is

an integer. Prove that Inez can change each nonintegral number x in the

array into either dxe or bxc so that the row-sums and column-sums remain

unchanged. (Note that dxe is the least integer greater than or equal to x,

while bxc is the greatest integer less than or equal to x.)

4. [ISL 1988 #4] Let n ≥ 2. Bathspounge numbers an n×n chessboard with

the numbers 1, 2, . . . , n2. Every number occurs once. Prove that there

exist two orthogonally adjacent squares such that their numbers differ by

at least n.

5. [Brazil Olympic Revenge 2014] Let n be a positive integer. In a 2n × 2n

board, 1 × n and n × 1 pieces are arranged without overlap. Call an

arrangement maximal if it is impossible to put a new piece in the board

without overlapping the previous ones. Find the least k such that there

is a maximal arrangement that uses k pieces.

6. [SubredditControl] Snake shuffles a deck of playing cards. Salamander

guesses if the top card is red or black, then turns it over. If he’s right, he

wins a dollar. If not, he pays a dollar. Repeat for the rest of the deck,

one card at a time. What should be his strategy, and what is his expected

return?

7. [SubredditControl] Inez paints 1, 2, 3, . . . , N in red, blue and white, so that

each color has more than a quarter of the set in its colour. Can she paint

it such that all x+ y = z in the set has at least two of the same colour?

3.3 Geometry

1. [ISL 2006 G1] Let ABC be triangle with incenter I. A point P in the

interior of the triangle satisfies

\ PBA+ \ PCA = \ PBC + \ PCB.

Show that AP ≥ AI, and that equality holds if and only if P = I.

2. [USA TST 2004 #4] Let ABC be a triangle. Choose a point D in its

interior. Let ω1 be a circle passing through B and D and ω2 be a circle

passing through C and D so that the other point of intersection of the two

circles lies on AD. Let ω1 and ω2 intersect side BC at E and F , respec-

tively. Denote by X the intersection of DF , AB and Y the intersection

of DE,AC. Show that XY ‖ BC.

3. [ISL 2007 G3] The diagonals of a trapezoid ABCD intersect at point P .

Point Q lies between the parallel lines BC and AD such that \ AQD =

\ CQB, and line CD separates points P and Q. Prove that \ BQP =

\ DAQ.

4. [Linus 2015] A polygon of wrapping paper folds to cover a cube completely

with no overlap. Show that it has two equal angles.

5

Page 6

5. [Russia 2006] Consider an isosceles triangle ABC with AB = AC, and

a circle ω which is tangent to the sides AB and AC of this triangle and

intersects the side BC at the points K and L. The segment AK intersects

the circle ω at a point M (apart from K). Let P and Q be the reflec-

tions of the point K in the points B and C, respectively. Show that the

circumcircle of triangle PMQ is tangent to the circle ω.

6. [Iran 2010] Circles W1,W2 intersect at P,K. XY is common tangent of

two circles which is nearer to P and X is on W1 and Y is on W2. XP

intersects W2 for the second time in C and Y P intersects W1 in B. Let

A be intersection point of BX and CY . Prove that if Q is the second

intersection point of circumcircles of ABC and AXY

∠QXA = ∠QKP

7. [Tuymaada 2012] Quadrilateral ABCD is both cyclic and circumscribed.

Its incircle touches its sides AB and CD at points X and Y , respectively.

The perpendiculars to AB and CD drawn at A and D, respectively, meet

at point U ; those drawn at X and Y meet at point V , and finally, those

drawn at B and C meet at point W . Prove that points U , V and W are

collinear.

3.4 Number Theory

1. [South Africa 2004 #1] Let a = 1111 . . . 1111 and b = 1111 . . . 1111 where

a has forty ones and b has twelve ones. Determine the greatest common

divisor of a and b.

2. [Brazil Olympic Revenge 2010 #1] Fix a prime p and an integer a with

gcd(a, p) = 1. Prove that the number of ordered triples (x, y, z) of positive

integers such that 0 ≤ x, y, z < p and (x+y+z)2 ≡ axyz (mod p) is equal

to p2 + 1.

3. [ISL 2009 N3] Let f be a non-constant function from the set of positive

integers into the set of positive integer, such that a− b divides f(a)− f(b)

for all distinct positive integers a, b. Prove that there exist infinitely many

primes p such that p divides f(c) for some positive integer c.

4. [ISL 2001 N4] Let p ≥ 5 be a prime number. Prove that there exists an

integer a with 1 ≤ a ≤ p− 2 such that neither ap−1− 1 nor (a+ 1)p−1− 1

is divisible by p2.

5. [Linus’ Homework from UCL: Sarah Zerbes]

(a) Solve x3 = y2 + 1 in integers.

(b) Solve x3 = y2 + 5 in integers.

6. [ELMO SL 2011 N3] Let n > 1 be a fixed positive integer, and call

an n-tuple (a1, a2, . . . , an) of integers greater than 1 good if and only if

ai

∣∣∣ (a1a2···anai − 1) for i = 1, 2, . . . , n. Prove that there are finitely many

good n-tuples.

6