MathDB

1

p^{2}+2q^{2}=r^{2}

p,

q,

r

satisfying

p^{2}+2q^{2}=r^{2}.

11

1

set S_{k} contains infinitely many multiples of m

Let

S_{1},

S_{2},

...,

S_{n}

be finitely many subsets of

\mathbb{N}

such that

S_{1}\cup S_{2}\cup...\cup S_{n}=\mathbb{N}.

Prove that there exists some

k\in\left\{ 1,2,...,n\right\}

such that for each positive integer

m,

the set

S_{k}

contains infinitely many multiples of

m.

2

1

Areas equation in a trapezoid

Let

ABCD

be a trapezoid with

BC\parallel AD

, and let

O

be the point of intersection of its diagonals

AC

and

BD

. Prove that \left\vert ABCD\right\vert \equal{}\left( \sqrt{\left\vert BOC\right\vert }\plus{}\sqrt{\left\vert DOA\right\vert }\right) ^{2}. [hide="Source of the problem"]Source of the problem: exercise 8 in: V. Alekseev, V. Galkin, V. Panferov, V. Tarasov, Zadachi o trapezijah, Kvant 6/2000, pages 37-4.

3

1

Removing divisors - who wins?

Let

n

be a positive integer, and let M\equal{}\left\{ 1,2,...,n\right\}. Two players take turns at the following game: Each player, at his turn, has to select an element of

M

and remove all divisors of this element (including this element itself) from the set

M

. a) Assume that the player who cannot move anymore (because the set

M

is empty when it's his move) wins. For which values of

n

does the first player have a winning strategy? b) Assume that the player who cannot move anymore (because the set

M

is empty when it's his move) loses. For which values of

n

does the first player have a winning strategy?

5

1

"Isotomic" triangles have equal areas

Let

ABC

be a triangle, and let

X

,

Y

,

Z

be three points on the segments

BC

,

CA

,

AB

, respectively. Denote by

X^{\prime}

,

Y^{\prime}

,

Z^{\prime}

the reflections of these points

X

,

Y

,

Z

in the midpoints of the segments

BC

,

CA

,

AB

, respectively. Prove that \left\vert XYZ\right\vert \equal{}\left\vert X^{\prime}Y^{\prime}Z^{\prime}\right\vert.

10

1

Not only X on A-altitude, but also AO_aA_aX parallelogram

Let

ABC

be a triangle. The

A

-excircle of triangle

ABC

has center

O_{a}

and touches the side

BC

at the point

A_{a}

. The

B

-excircle of triangle

ABC

touches its sidelines

AB

and

BC

at the points

C_{b}

and

A_{b}

. The

C

-excircle of triangle

ABC

touches its sidelines

BC

and

CA

at the points

A_{c}

and

B_{c}

. The lines

C_{b}A_{b}

and

A_{c}B_{c}

intersect each other at some point

X

. Prove that the quadrilateral

AO_{a}A_{a}X

is a parallelogram. Remark. The

A

-excircle of a triangle

ABC

is defined as the circle which touches the segment

BC

and the extensions of the segments

CA

and

AB

beyound the points

C

and

B

, respectively. The center of this circle is the point of intersection of the interior angle bisector of the angle

CAB

and the exterior angle bisectors of the angles

ABC

and

BCA

. Similarly, the

B

-excircle and the

C

-excircle of triangle

ABC

are defined. [hide="Source of the problem"]Source of the problem: Theorem (88) in: John Sturgeon Mackay, The Triangle and its Six Scribed Circles, Proceedings of the Edinburgh Mathematical Society 1 (1883), pages 4-128 and drawings at the end of the volume.

14

1

Greater than weighted mean ==> greater than mean

Let

\left(a_{1},\ a_{2},\ a_{3},\ ...\right)

be a sequence of reals such that

a_{n}\geq\frac{\left(n-1\right)a_{n-1}+\left(n-2\right)a_{n-2}+...+2a_{2}+1a_{1}}{\left(n-1\right)+\left(n-2\right)+...+2+1}

for every integer

n\geq 2

. Prove that

a_{n}\geq\frac{a_{n-1}+a_{n-2}+...+a_{2}+a_{1}}{n-1}

for every integer

n\geq 2

. Generalization. Let

\left(b_{1},\ b_{2},\ b_{3},\ ...\right)

be a monotonically increasing sequence of positive reals, and let

\left(a_{1},\ a_{2},\ a_{3},\ ...\right)

be a sequence of reals such that

a_{n}\geq\frac{b_{n-1}a_{n-1}+b_{n-2}a_{n-2}+...+b_{2}a_{2}+b_{1}a_{1}}{b_{n-1}+b_{n-2}+...+b_{2}+b_{1}}

for every integer

n\geq 2

. Prove that

a_{n}\geq\frac{a_{n-1}+a_{n-2}+...+a_{2}+a_{1}}{n-1}

for every integer

n\geq 2

. darij

7

1

|ca-ab| + ... <= |b^2-c^2| + ...

For any three nonnegative reals

a

,

b

,

c

, prove that

\left|ca-ab\right|+\left|ab-bc\right|+\left|bc-ca\right|\leq\left|b^{2}-c^{2}\right|+\left|c^{2}-a^{2}\right|+\left|a^{2}-b^{2}\right|

.
Generalization. For any

n

nonnegative reals

a_{1}

,

a_{2}

, ...,

a_{n}

, prove that

\sum_{i=1}^{n}\left|a_{i-1}a_{i}-a_{i}a_{i+1}\right|\leq\sum_{i=1}^{n}\left|a_{i}^{2}-a_{i+1}^{2}\right|

.
Here, the indices are cyclic modulo

n

; this means that we set

a_{0}=a_{n}

and

a_{n+1}=a_{1}

.
darij

6

1

diameter (graph) <= 3 or diameter (complementary graph) <= 2

Any two islands of the Chaos Archipelago are connected by a bridge - a red bridge or a blue bridge. Show that at least one of the following two assertions holds:

\mathcal{A}_{1}

: For any two islands

a

and

b

, we can reach

b

from

a

through at most

3

red bridges (and no blue bridges).

\mathcal{A}_{2}

: For any two islands

a

and

b

, we can reach

b

from

a

through at most

2

blue bridges (and no red bridges). Alternative formulation: Let

G

be a graph. Prove that the diameter of

G

is

\leq 3

or the diameter of the complement of

G

is

\leq 2

. Note. This problem is the main Theorem in Frank Harary, Robert W. Robinson, The Diameter of a Graph and its Complement, The American Mathematical Monthly, Vol. 92, No. 3. (Mar., 1985), pp. 211-212. darij

9

1

k-regular triangle-free graphs are halfways bipartite

A team contest between

n

participants is to be held. Each of these participants has exactly

k

enemies among the other participants. (If

A

is an enemy of

B

, then

B

is an enemy of

A

. Nobody is his own enemy.) Assume that there are no three participants such that every two of them are enemies of each other. A subversive enmity will mean an (un-ordered) pair of two participants which are enemies of each other and which belong to one and the same team. Show that one can divide the participants into two teams such that the number of subversive enmities is

\leq\frac{k\left(n-2k\right)}{2}

. (The teams need not be of equal size.) Note. The actual source of this problem is: Glenn Hopkins, William Staton, Maximal Bipartite Subgraphs, Ars Combinatoria 13 (1982), pp. 223-226. It should be noticed that

\frac{k\left(n-2k\right)}{2}\leq\frac{n^{2}}{16}

, so the bound in the problem can be replaced by

\frac{n^{2}}{16}

(which makes it weaker, but independent of

k

). darij

13

1

SUM_u (n+u-1 binom u) (n binom k-2u) = (n+k-1 binom k)

Let

n

and

k

be integers such that

0\leq k\leq n

. Prove that

\sum_{u=0}^{k}\binom{n+u-1}{u}\binom{n}{k-2u}=\binom{n+k-1}{k}

. Note that we use the following conventions:

\binom{r}{0}=1

for every integer

r

;

\binom{u}{v}=0

if

u

is a nonnegative integer and

v

is an integer satisfying

v<0

or

v>u

. Darij

12

1

Intersections with Incircle

Let

ABC

be a triangle, and let

D

,

E

,

F

be the points of contact of its incircle

\omega

with its sides

BC

,

CA

,

AB

, respectively. Let

K

be the point of intersection of the line

AD

with the incircle

\omega

different from

D

, and let

M

be the point of intersection of the line

EF

with the line perpendicular to

AD

passing through

K

. Prove that

AM

is parallel to

BC

.

2007 QEDMO 4th

Subcontests

p^{2}+2q^{2}=r^{2}

set S_{k} contains infinitely many multiples of m

Areas equation in a trapezoid

Removing divisors - who wins?

"Isotomic" triangles have equal areas

Not only X on A-altitude, but also AO_aA_aX parallelogram

Greater than weighted mean ==> greater than mean

|ca-ab| + ... <= |b^2-c^2| + ...

diameter (graph) <= 3 or diameter (complementary graph) <= 2

k-regular triangle-free graphs are halfways bipartite

SUM_u (n+u-1 binom u) (n binom k-2u) = (n+k-1 binom k)

Intersections with Incircle

2007 QEDMO 4th

Subcontests

p^{2}+2q^{2}=r^{2}

set S_{k} contains infinitely many multiples of m

Areas equation in a trapezoid

Removing divisors - who wins?

&quot;Isotomic&quot; triangles have equal areas

Not only X on A-altitude, but also AO_aA_aX parallelogram

Greater than weighted mean ==&gt; greater than mean

|ca-ab| + ... &lt;= |b^2-c^2| + ...

diameter (graph) &lt;= 3 or diameter (complementary graph) &lt;= 2

k-regular triangle-free graphs are halfways bipartite

SUM_u (n+u-1 binom u) (n binom k-2u) = (n+k-1 binom k)

Intersections with Incircle

"Isotomic" triangles have equal areas

Greater than weighted mean ==> greater than mean

|ca-ab| + ... <= |b^2-c^2| + ...

diameter (graph) <= 3 or diameter (complementary graph) <= 2