Title MOP Homework 2015 228.6 KB 7
##### Document Text Contents
Page 1

MOP Homework 2015

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-

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

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 =

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

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